早教吧作业答案频道 -->数学-->
前、中、后序,知道其中哪两个就可以还原二叉树?请予以证明,或者随便举个反例说明
题目详情
前、中、后序,知道其中哪两个就可以还原二叉树?
请予以证明,或者随便举个反例说明
请予以证明,或者随便举个反例说明
▼优质解答
答案和解析
1. 知道一棵二叉树（二叉树的子树也是二叉树）的前序和后序序列,就可以知道这棵二叉树的根.因为前序的第一个结点是当前这棵二叉树的根,后序序列的最后一个结点是根
2. 知道一棵二叉树的根,同时知道其中序序列,就可以知道根的左子树序列和右子树序列.因为中序序列中的根前的结点属于左子树,根后的结点属于右子树（这个由中序序列的遍历性质可知）
3. 所以只要知道前序和中序,或者中序和后序即可还原二叉树
4. 而只知道前序和后序无法保证还原二叉树,例如二叉树
A 与 A
B B
C C
的前序序列都是ABC,而后序序列都是CBA
2. 知道一棵二叉树的根,同时知道其中序序列,就可以知道根的左子树序列和右子树序列.因为中序序列中的根前的结点属于左子树,根后的结点属于右子树（这个由中序序列的遍历性质可知）
3. 所以只要知道前序和中序,或者中序和后序即可还原二叉树
4. 而只知道前序和后序无法保证还原二叉树,例如二叉树
A 与 A
B B
C C
的前序序列都是ABC,而后序序列都是CBA
看了 前、中、后序,知道其中哪两个...的网友还看了以下：
如图所示,在装有适量水的盘子如图所示,在装有适量水的盘子中央,固定一支点燃的蜡烛,然后将一个透明的 2020-05-16 …
明明一分钟打70个字丽丽一分钟打85个字明明每分钟打字的速度比莉莉百分之几明明一分钟打70个字丽丽 2020-05-20 …
一个标明220V,100W,另一个标明220v,40W将他们并接到220V的市电上,求总电流一个标 2020-05-23 …
如图（1），在△ABC中，AB=AC，∠A=36°．（1）直接写出∠ABC的度数；（2）如图（2） 2020-06-02 …
共有31个数字1－31,每期选出8个.任选一个,中的概率是多少?任先4个,不中一个的概率是多少?将 2020-06-04 …
来源于历史故事的成语3个写几个含有近义词的成语3个含有修辞的成语比喻3来源于历史故事的成语3个写几 2020-06-10 …
姚明NBA2008赛季常规赛的一场比赛中29投18中,拿下28分,其中9个球罚球全中,(罚球投中一 2020-06-24 …
单缝衍射中条纹间距不等,这个我明白.可是又说其它各级明纹宽度是中央明纹的一半,那岂不是等距的意思? 2020-07-01 …
5个可重复的随机数，抽中某个数的概率是多少？在1.2.3.4.5.........5个可重复出现的情 2020-11-03 …
一堆苹果，2个2个地数剩1个，3个3个地数剩2个，4个4个地数剩3个，5个5个地数剩4个，6个6个地 2020-11-19 …