python模拟二叉树及各种遍历

收获在二叉树添加元素构造的完全二叉树和广度优先遍历的时候采用队列的思想在深度优先遍历中采用递归突然意识到递归就很像栈的思想。测试代码构造的二叉树# 二叉树 # 结点类 class Node(): def __init__(self,item): self.item item self.left None self.right None # 二叉树类 class BinaryTree(): def __init__(self,nodeNone): self.root node # 添加结点 def add(self,item): new_node Node(item) if self.root is None: self.root new_node else: queue [] queue.append(self.root) while len(queue) ! 0: cur queue.pop(0) if cur.left is None: cur.left new_node break else: queue.append(cur.left) if cur.right is None: cur.right new_node break else: queue.append(cur.right) # 广度优先遍历 def breadth(self): if self.root is None: return queue [] queue.append(self.root) while len(queue): cur queue.pop(0) print(cur.item,end ) if cur.left is not None: queue.append(cur.left) #print(queue[0].item) if cur.right is not None: queue.append(cur.right) #深度优先遍历之 先序遍历 def preOrder(self,root): if root is None: return cur root print(cur.item,end ) if cur.left is not None: self.preOrder(cur.left) if cur.right is not None: self.preOrder(cur.right) #深度优先遍历之 中序遍历 def midOrder(self,root): if root is None: return cur root if cur.left is not None: self.midOrder(cur.left) print(cur.item,end ) if cur.right is not None: self.midOrder(cur.right) #深度优先遍历之 后序遍历 def postOrder(self,root): if root is None: return cur root if cur.left is not None: self.postOrder(cur.left) if cur.right is not None: self.postOrder(cur.right) print(cur.item, end ) # 测试 if __name__ __main__: bt BinaryTree() bt.add(A) bt.add(B) bt.add(C) bt.add(D) bt.add(E) bt.add(F) bt.add(G) bt.add(H) print(广度优先遍历, end ) bt.breadth() print(\n深度优先遍历--先序,end ) bt.preOrder(bt.root) print(\n深度优先遍历--中序, end ) bt.midOrder(bt.root) print(\n深度优先遍历--后序, end ) bt.postOrder(bt.root)运行结果