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

admin2009-07-15 74

问题 (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://kaotiyun.com/show/1RNZ777K

最新回复(0)

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

笔试

原NCRE全国计算机四级

NCRE全国计算机四级

图像文件格式分为静态图像文件格式和动态图像文件格式。__________________属于静态图像文件格式。

以下关于SSD固态硬盘和普通HDD硬盘的叙述中，错误的是__________。

寄存器寻址方式中的操作数放在__________________中。

有以下HTML代码，在浏览器中显示正确的是__________。＜html＞＜framesetrows="25％，50％，25％"＞＜framesrc="／html／frame_A．html"＞＜framesrc="／html／fra

以下关于服务器端脚本的说法中，正确的是()。

设X、Y为逻辑变量，与逻辑表达式Y等价的是_________。

阅读以下说明和Java代码，将解答写入对应栏内。【说明】下面的程序是从命令行输入3个数传递到publicstaticvoidmain(Stringargs[])方法中(如javaIsTriangle345)，并判断这3个数能否构

计算机的总线包含地址总线，数据总线和控制总线。某计算机CPU有16条地址总线，则该计算机最大的寻址空间为(2)字节，若该CPU寻址外部的数据存储器时，第16条地址线始终为高电平，则此数据存储器的地址空间为(3)字节。

一般情况下，操作数左移3位的结果是原操作数

根据课堂纪律形成的途径，刚入学儿童的课堂纪律主要是由其特定的任务促成的。()

A．伤寒第一次菌血症B．伤寒第二次菌血症C．伤寒肠道并发症D．伤寒后再燃E．伤寒后复发伤寒缓解期

对个体工商户、农村承包经营户发放的贷款，应当以转账方式支付。()

()是指市场参与者在计量日发生的有序交易中，出售一项资产所能收到或者转移一项负债所需支付的价格。

中华民族精神是中华民族生生不息、发展壮大的强大精神动力。以下关于培育和弘扬民族精神的表述正确的有

有64个结点的完全二叉树的深度【】(根的层次为1)。

AccordingtoBrickland,parentsnowadayshavechangedtheir______.TheNetherlandshasplacedtherightsofpedestriansbefore