问答题
假设一棵二叉树的先序序列为EBADCFHGIIKJ,中序序列为ABCDEFGHIJK。请写出该二又树的后序遍历序列。
【正确答案】求解此题有两种方法,第一种方法是先根据二叉树的先序序列和中序序列画出这棵二叉树,再写出该二叉树的后序遍历序列;第二种方法是对一棵二叉树的各结点在给出的先序序列和中序序列中的序列分布位置进行分析,从而写出该二叉树的后序遍历序列。
如按题目给出的一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK进行分析,在先序序列中结点E就是树根结点,那么,在中序序列中,结点E将中序序列分成两部分,E的左边ABcD是E的左子树,E的右边FGHUK是E的右子树。那么,E在后序遍历序列中一定处于最后位置,而E的左子树和E的右子树都在E的前面,且E的左子树结点又都在E的右子树结点前面。然后再依此方法,分析E的左子树和E的右子树。
如此可得该二叉树的后序遍历序列为:ACDBGJKIHFE。
【答案解析】