本文共 3352 字，大约阅读时间需要 11 分钟。
class Node(object): def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right = rightclass 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://vxegx.baihongyu.com/