早教吧 育儿知识 作业答案 考试题库 百科 知识分享

前、中、后序,知道其中哪两个就可以还原二叉树?请予以证明,或者随便举个反例说明

题目详情
前、中、后序,知道其中哪两个就可以还原二叉树?
请予以证明,或者随便举个反例说明
▼优质解答
答案和解析
1. 知道一棵二叉树(二叉树的子树也是二叉树)的前序和后序序列,就可以知道这棵二叉树的根.因为前序的第一个结点是当前这棵二叉树的根,后序序列的最后一个结点是根
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 …