二叉树结点的计算?
题目
二叉树结点的计算?
某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则后序遍历的结点访问顺序是(gdbehfca)
这个答案是怎么算出来的?
答案
首先我们知道,前序遍历的规则是:根结点→左子结点→右子结点
中序遍历是:左子结点→根结点→右子结点
后序遍历是:左子结点→右子结点→根结点
那么,对于一棵二叉树,前序遍历的第一个结点一定是这棵树的根结点,即根结点是a.
在中序遍历的顺序dgbaechf中,以a分成左、右两边,左边是dgb,右边是echf.
所以,这棵树现在可以确定如下:
a
/
dgb echf
接下来再分别对左子树和右子树进行类似的操作.
对于左子树dgb来说,在前序遍历abdgcefh中找到bdg,证明这子树的根是b,那么现在可以确定的树结构如下:
a
/
b echf
/
dg
再看dg,前序遍历中的顺序为dg,所以d是dg这部分子树的根,那么又因为中序遍历的dg顺序也是dg,所以g是右子结点.
即:
a
/
b echf
/
d
g
现在看echf这部分子树,前序中顺序是cefh,所以子树根结点是c,那么左子结点是e,右子树是hf:
得到:
a
/
b c
/ /
d e hf
g
最后只剩下hf部分了,前序遍历中是fh,所以根是f,那么h就是左子结点.
现在得到了整棵树:
a
/
b c
/ /
d e f
/
g h
对这棵树再进行后序遍历就行了,结果就是:gdbehfca
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
热门考点
- 放线菌和细菌结构上有什么不同 细胞器有哪些差异
- 已知三角形三顶点的坐标是A(-1,2,3)B(1,1,1)C(0,0,5)试证明三角形ABC是直角三角形,并求角B 是向量的数量积
- many的用法
- 已知:2+7分之2的立方根 第2011
- 将一定量的镁粉和铝粉混合物分成两等分,一份与足量稀盐酸反应,一份与足量烧碱溶液反应,生成气体体积之比4:3,原混合物中镁和铝物质的量之比为( )
- 一个数的小数点,向左移一位,所得的数比原数小162,原数是多少?3Q
- (0.75×121-3/4×20-1/5)÷0.75怎么简算
- ‘永不言弃’用英语怎么说
- 树木长得茂盛的词语
- 克隆英文写法