2. 计算机
  3. (1)试说明给定一棵二叉树结点的后序序列和中序序列，则此二叉树可构造出来。 (2)一棵二叉树的中序序列为BFDGAEHC，后序序列为FGDBHECA，构造出此二叉树。

(1)试说明给定一棵二叉树结点的后序序列和中序序列，则此二叉树可构造出来。 (2)一棵二叉树的中序序列为BFDGAEHC，后序序列为FGDBHECA，构造出此二叉树。

admin2009-07-15  104
问题 (1)试说明给定一棵二叉树结点的后序序列和中序序列，则此二叉树可构造出来。
(2)一棵二叉树的中序序列为BFDGAEHC，后序序列为FGDBHECA，构造出此二叉树。
选项
答案根据二叉树的定义，一棵二叉树通常由一棵左子树和一棵右子树及一个根结点组成，假设二叉树T，它的左子树和右子树分别为T1和T2，已知-X树T的后序序列和中序序列，根据后序序列定义，可知二叉树T的根结点必定为其后序序列的最后一个结点，由此我们得到二叉树T的根结点；而根据中序序列的定义，二叉树T必定具有这样的性质，即其根结点左端的结点序列必为其左子树T1所包含的所有结点的中序序列，根结点右端的结点序列必为其右子树T2所包含的所有结点的中序序列。这样二叉树T左右子树所包含的结点及中序序列也知道了。接下来，我们只要证明二叉树T的左子树T1可构造出来，其右子树T2也可构造出来。同理，对于二叉树T1，已知它的中序序列，从二叉树T的后序序列中也可得出它的后序序列，因此，可得出了I的根结点及T1的左子树T11和右子树T12的中序序列，很明显，就这样一直下去，直到把左子树T1的所有结点分析完，此时必可构造出二叉树T1。同理，右子树T2也可构造出来。因此，知道二叉树T的根结点和它的左右子树，二叉树T也就构造出来了。 [*]
解析
转载请注明原文地址:https://www.kaotiyun.com/show/1RNZ777K
0

笔试

原NCRE全国计算机四级

NCRE全国计算机四级

相关试题推荐
随机试题
最新回复(0)