试题-若一颗二叉树的前序遍历为a,e,b,d,c,后序遍历为b,c,d,e,a，则根节点的孩子节点（）

题目

若一颗二叉树的前序遍历为a,e,b,d,c,后序遍历为b,c,d,e,a，则根节点的孩子节点（）

A.只有e

B.有e，b

C.有e，c

D.不确定

上一题 下一题

解答

正确答案是 A

选A

解题思路：由先序遍历第一个结点为a,则可知道树的根节点为a。后序遍历序列中根节点会把序列分为左右两段，左段为左子树上结点，右段为右子树上结点，所以由后序遍历序列可知b,c,d,e均为a结点的左子树上的点，a不存在右子树。再由先序遍历序列知道e为根结点a的左孩子结点。即根节点的孩子结点只有e，且为左孩子。

C 7条回复评论

海边的卡夫卡

感谢，这种刷题式的学习方式真的很方便！

发表于 2022-06-13 23:00:00

0 0

云散兮

技多不压身

发表于 2022-06-12 23:00:00

0 0

秒秒

java感觉有点难，前端咋样，好学么

发表于 2022-04-21 21:00:00

0 0

海边的卡夫卡

正在研究redis，感谢,太赞了！！！！！

发表于 2022-01-26 22:00:00

0 0

雨声敲敲

有前序和后续可以看出根节点为a,但不能区分出左子树，右子树二叉树去掉a之后，变为前序e,b,d,c 后续 b,c,d,e 此时根节点是 e

因此二叉树根节点的孩子节点只有e

发表于 2018-11-01 15:25:21

0 0

小洁癖

根据树的前序和后序序列不能唯一确定二叉树，所以这里只能假设。而且节点比较少容易观察，对比这两个序列，可以将其分为两组，前序：(a,e)(b,d,c)后续：(b,c,d)(a,e)这两组，可以看出e为a的孩子节点，但是不能确定是左孩子还是右孩子；b,c为d的孩子节点。

发表于 2018-11-01 15:24:49

0 0

雨声敲敲

答案：A
前序遍历第一个是根节点，所以a是根节点
假设a有两个孩子节点，则前序遍历a后面为e,所以e必定属于a的左子树中的节点
后续遍历中a的前面挨着是e，所以e必定是a的右子树中的节点，相互矛盾。
因此a只有一个孩子节点。
在a只有一个孩子节点，也就是只有左子树或者只有右子树的情况下，前序遍历首先是根节点a,然后紧接着就是子树的跟节点，也就是a的唯一的孩子节点，所以e是a的子节点。

发表于 2018-11-01 15:24:39

0 0