python模拟二叉树及各种遍历

收获：

在二叉树添加元素（构造的完全二叉树）和广度优先遍历的时候采用队列的思想；

在深度优先遍历中采用递归，突然意识到递归就很像栈的思想。

测试代码构造的二叉树：

# 二叉树 # 结点类 class Node(): def __init__(self,item): self.item = item self.left = None self.right = None # 二叉树类 class BinaryTree(): def __init__(self,node=None): 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)

运行结果：