二叉树遍历

  1 #定义二叉树的节点
  2 class Node(object):
  3     def __init__(self,elem):
  4         """
  5         param: self.elem 是节点的数据域
  6                 self.lchild 是节点的左孩子
  7                 self.rchild 是节点的右孩子
  8         """
  9         self.elem = elem
 10         self.lchild = None
 11         self.rchild = None
 12 
 13 class Tree(object):
 14     def __init__(self):
 15         self.root = None
 16     #添加节点
 17     def add(self,elem):
 18         """
 19         param: elem 是传进来的数据，我们要实例化一个节点接收它，
 20                 queue: 创建一个队列来接收和弹出节点       
 21         """
 22         #创建节点
 23         node = Node(elem)    
 24         if self.root == None:
 25             """如果根节点是None,则表示一颗空树，直接把该节点赋给root节点"""
 26             self.root = node
 27             return
 28         queue = []
 29         queue.append(self.root)
 30         while queue:
 31             """队列的弹出要加0，与栈相仿"""
 32             curNode = queue.pop(0)
 33             if curNode.lchild == None:
 34                 curNode.lchild = node
 35                 return
 36             else:
 37                 queue.append(curNode.lchild)
 38             if curNode.rchild == None:
 39                 curNode.rchild = node
 40                 return
 41             else: 
 42                 queue.append(curNode.rchild)
 43 
 44     #广度优先遍历
 45     def travel(self):
 46         queue = []
 47         #判断根节点是否存在
 48         if self.root is None:
 49             return
 50         else:
 51             queue.append(self.root)
 52         while queue:
 53             curNode = queue.pop(0)
 54             print(curNode.elem,end=‘\t‘)
 55             if curNode.lchild is not None:
 56                 queue.append(curNode.lchild)
 57             if curNode.rchild is not None:
 58                 queue.append(curNode.rchild)
 59         print()
 60     #先序遍历 根 左 右
 61     def preOrder(self,root):
 62         if root is None:
 63             return
 64         else:
 65             print(root.elem,end=‘\t‘)
 66             self.preOrder(root.lchild)
 67             self.preOrder(root.rchild)
 68 
 69     #中序遍历 左 根 右
 70     def inOrder(self,root):
 71         if root is None:
 72             return
 73         else:
 74             self.inOrder(root.lchild)
 75             print(root.elem,end=‘\t‘)
 76             self.inOrder(root.rchild)
 77     
 78     #后序遍历 左 右 根
 79     def postOrder(self,root):
 80         if root is None:
 81             return
 82         self.postOrder(root.lchild)
 83         self.postOrder(root.rchild)
 84         print(root.elem,end=‘\t‘)
 85 
 86             
 87 if __name__ == ‘__main__‘:
 88     tree = Tree()
 89     tree.add(‘A‘)
 90     tree.add(‘B‘)
 91     tree.add(‘C‘)
 92     tree.add(‘D‘)
 93     tree.add(‘E‘)
 94     print(‘广度优先遍历‘)
 95     tree.travel()
 96     print(‘先序遍历‘)
 97     tree.preOrder(tree.root)
 98     print()
 99     print(‘中序遍历‘)
100     tree.inOrder(tree.root)
101     print()
102     print(‘后序遍历‘)
103     tree.postOrder(tree.root)

1 广度优先遍历
2 A       B       C       D       E
3 先序遍历
4 A       B       D       E       C
5 中序遍历
6 D       B       E       A       C
7 后序遍历
8 D       E       B       C       A