早教吧作业答案频道 -->数学-->
前、中、后序,知道其中哪两个就可以还原二叉树?请予以证明,或者随便举个反例说明
题目详情
前、中、后序,知道其中哪两个就可以还原二叉树?
请予以证明,或者随便举个反例说明
请予以证明,或者随便举个反例说明
▼优质解答
答案和解析
1. 知道一棵二叉树(二叉树的子树也是二叉树)的前序和后序序列,就可以知道这棵二叉树的根.因为前序的第一个结点是当前这棵二叉树的根,后序序列的最后一个结点是根
2. 知道一棵二叉树的根,同时知道其中序序列,就可以知道根的左子树序列和右子树序列.因为中序序列中的根前的结点属于左子树,根后的结点属于右子树(这个由中序序列的遍历性质可知)
3. 所以只要知道前序和中序,或者中序和后序即可还原二叉树
4. 而只知道前序和后序无法保证还原二叉树,例如二叉树
A 与 A
B B
C C
的前序序列都是ABC,而后序序列都是CBA
2. 知道一棵二叉树的根,同时知道其中序序列,就可以知道根的左子树序列和右子树序列.因为中序序列中的根前的结点属于左子树,根后的结点属于右子树(这个由中序序列的遍历性质可知)
3. 所以只要知道前序和中序,或者中序和后序即可还原二叉树
4. 而只知道前序和后序无法保证还原二叉树,例如二叉树
A 与 A
B B
C C
的前序序列都是ABC,而后序序列都是CBA
看了 前、中、后序,知道其中哪两个...的网友还看了以下:
已知:如图,圆内四边形ABCD的对角线AC、BD交于点N,点M在BD上,且满足∠1=∠2,∠3=∠ 2020-05-13 …
(读写译2)英语作文以Mr.Baxter的名义写一封请求信.内容如下:1.今年10月1日买的电子词 2020-06-12 …
如图,AD是∠CAB的角平分线,DE∥AB,DF∥AC,EF交AD于点O.请问:(1)DO是∠ED 2020-06-15 …
英语翻译一下!法律英语内容摘要中国行政诉讼举证责任的分担规则,是谁主张、谁举证.美国奉行的举证责任 2020-06-21 …
阅读下面文段,完成后面题。(10分)予观弈于友人所。一客数败,嗤其失算,辄欲易置之,以为不逮己也。 2020-06-29 …
下面的比喻运用得不够贴切,请给予修改。修改后要以“歌声”为本体。她那婉转的歌声,如同燃烧的火焰一般 2020-06-29 …
魏格纳在病房观察地图.魏格纳在病房观察地图,脑海里逐渐形成了一个崭新的奇想,后来经过考察、寻找证据 2020-07-08 …
英语翻译介绍信德意志联邦共和国大使馆签证处兹有中国南京市**工程有限公司员工赵国先生应德国**公司 2020-07-13 …
阅读下列材料回答问题:材料一(1624年英国专利法)第六条规定,今后对任何新产品的真正第一发明可以授 2020-11-05 …
阅读下面文段,完成后面题。(10分)予观弈于友人所。一客数败,嗤其失算,辄欲易置之,以为不逮己也。顷 2020-12-24 …