class Node( object ): def __init__ ( self , data = None , left = None , right = None ): self .data = data self .left = left self .right = right class BTree( object ): def __init__ ( self , root = None ): self .root = root def is_empty( self ): if self .root is None : return True else : return False # 先序遍历（递归，recursion） def pre_order( self , node): if node is None : return print (node.data) self .pre_order(node.left) self .pre_order(node.right) # 中序遍历（递归） def in_order( self , node): if node is None : return self .in_order(node.left) print (node.data) self .in_order(node.right) # 后序遍历（递归） def post_order( self , node): if node is None : return self .post_order(node.left) self .post_order(node.right) print (node.data) # 先序遍历（非递归） def preorder( self , node): stack = [] while node or stack: if node is not None : print (node.data) stack.append(node) node = node.left else : node = stack.pop() node = node.right # 中序遍历（非递归） def inorder( self , node): stack = [] while node or stack: if node: stack.append(node) node = node.left else : node = stack.pop() print (node.data) node = node.right # 后序遍历（非递归） def postorder( self , node): stack = [] queue = [] queue.append(node) while queue: node = queue.pop() if node.left: queue.append(node.left) if node.right: queue.append(node.right) stack.append(node) while stack: print (stack.pop().data) # 水平遍历 def levelorder( self , node): if node is None : return queue = [node] while queue: node = queue.pop( 0 ) print (node.data) if node.left: queue.append(node.left) if node.right: queue.append(node.right) # 根据前序遍历和中序遍历，求后序遍历 def findTree( self , preList, midList, afterList): ''' preList = list('DBACEGF') midList = list('ABCDEFG') afterList = ['A', 'C', 'B', 'F', 'G', 'E', 'D'] ''' if len (preList) == 0 : return if len (preList) == 1 : afterList.append(preList[ 0 ]) return root = preList[ 0 ] n = midList.index(root) self .findTree(preList[ 1 :n +1 ], midList[:n], afterList) self .findTree(preList[n +1 :], midList[n +1 :], afterList) afterList.append(root) #return afterList ''' n1 = Node(data=1) n2 = Node(2,n1,None) n3 = Node(3) n4 = Node(4) n5 = Node(5,n3,n4) n6 = Node(6,n2,n5) n7 = Node(7,n6,None) n8 = Node(8) root = Node(0,n7,n8) ''' root = Node( 0 , Node( 7 , Node( 6 , Node( 2 , Node( 1 )), Node( 5 , Node( 3 ), Node( 4 )))), Node( 8 )) bt = BTree(root) print ( 'pre_order......' ) print (bt.pre_order(bt.root)) print ( 'in_order......' ) print (bt.in_order(bt.root)) print ( 'post_order.....' ) print (bt.post_order(bt.root)) preList = list ( 'DBACEGF' ) midList = list ( 'ABCDEFG' ) afterList = [] bt.findTree(preList, midList, afterList)

print(afterList)

本文转自罗兵博客园博客，原文链接：http://www.cnblogs.com/hhh5460/p/5887332.html，如需转载请自行联系原作者