本文共 3070 字，大约阅读时间需要 10 分钟。
最近在学习二叉树，遇到了这样一题，在这里给大家提供一种方法，可能不是最好的，仅供大家参考和相互交流学习。 已知一个二叉树前序遍历、中序遍历的结果，请确定该二叉树并输出其后序遍历的结果。例如: 先序遍历结果为：A B D E G C F H； 中序遍历结果为：D B G E A C H F；则应该能够得出后序遍历结果为：D G E B H F C A。分析这个问题，我们可以从先序、中序、后序遍历的特点和结果，结合题目中给出的典型例子，得出相关的规律；我的思路是：先由先序和中序遍历结果计算得到二叉树，之后用递归方法对二叉树进行后序遍历得出结果。（1）首先，由先序和中序遍历，我们是完全可以得到二叉树的构成的，这由两者的区别和联系所共同决定；我们以上面的例子来说明思路：① A B D E G C F H 可以被分成两个部分来看 A B D E G and C F H② D B G E A C H F D B G E A C H F 以先序遍历为基础，我们知道先序遍历一定先遍历根节点，由①可知 A 一定是根节点，则在先序和中序遍历过程中，两者都要先遍历完 A 的左子树，再去遍历 A 的右子树；所以，很明显地，在中序遍历中，A 将会列表分为两半：D,B,G,E 以及 C,H,F。其中 D,B,G,E 均为 A 的左子树节点，而 C,H,F 均为 A 的右子树的节点。 我们将视线转回先序遍历，由于遍历根节点 A 之后，紧接着按照先序遍历一定会去遍历A的左子树的根节点，即节点B；又因为 B,D,E,G 均为 A 的左子树节点，根据先序遍历的特点，在 A 的左子树遍历完成之后，立刻就会去遍历 A 的右子树的根节点，也就是第二个部分中①的第一个节点 C（应注意②中的第二部分第一个节点也为C仅仅是这一题的情况，不能由此断言A的右子树根节点为C，而应根据先序遍历的首位C来判断）。 这样，我们就可以将原有的整个二叉树，在除去根节点 A 之后，得到它的两个子树及其各自的根节点 B 和 C，而下面的思路就很明了，使用递归方法，分别对B、C两个子树进行左右分解，注意判断递归条件和不断建立新节点，这样就可以获取整个二叉树了。再递归函数中，分情况讨论可以分为以下几种：1）A B D E G C F H D B G E A C H F （完整类型）2）A C F H A C H F （A不含有左子树）3）A B D E G D B G E A （A不含有右子树）4）A A （A不含有左右子树，即A为叶节点）（2）在获取整个二叉树后，使用递归方法写后序遍历函数，对二叉树进行后序遍历，即可得到正确结果。示例代码如下：
def tree_establish(Node, Preorder, Inorder, n): # 建立二叉树(Node为根节点,n为节点数量) i = Inorder.index(Preorder[0]) if i == 0: # 根节点 A 不存在左子树 if i + 1 <= n - 1: # 根节点 A 存在右子树(C为根节点) Node.rchild = node(Preorder[i+1]) tree_establish(Node.rchild, Preorder[i+1:n:1], Inorder[i+1:n:1], n-1) else: # 根节点A不存在左右节点（子树） return 1 else: # 根节点 A 存在左子树(B为根节点) if i + 1 <= n - 1: # 根节点 A 含有左右子树 Node.lchild = node(Preorder[1]) Node.rchild = node(Preorder[i+1]) tree_establish(Node.lchild, Preorder[1:i+1:1], Inorder[0:i:1], i) tree_establish(Node.rchild, Preorder[i+1:n:1], Inorder[i+1:n:1], n-i-1) else: # 根节点 A 不含有右子树 Node.lchild = node(Preorder[1]) tree_establish(Node.lchild, Preorder[1:i+1:1], Inorder[0:i:1], i)def post_order_probing(Node): # 后序遍历函数（递归实现） if Node is None: return 0 else: if Node.lchild: post_order_probing(Node.lchild) if Node.rchild: post_order_probing(Node.rchild) print(Node.elem, end=' ')class node(object): # 定义节点类 def __init__(self, elem=None, lchild=None, rchild=None, par=None): self.elem = elem self.lchild = lchild self.rchild = rchild self.par = parclass tree(object): # 定义树类 def __init__(self, root=node()): self.root = rootpreorder = [i for i in input().split()] # 输入先序遍历结果inorder = [i for i in input().split()] # 输入中序遍历结果N = len(preorder)MyTree = tree(node(preorder[0])) # 初始化二叉树tree_establish(MyTree.root, preorder, inorder, N) # 建立二叉树post_order_probing(MyTree.root) # 打印后序遍历结果（最后有个空格）
转载地址：http://ahvrj.baihongyu.com/