千秋若离 发表于 2022-5-5 13:28:22

知道二叉树前序遍历序列找后序遍历

二叉搜索树的取值为2、7、8、10、14、16、20、24、33和40。
对树的前序遍历产生的序列是:16、10、7、2、8、14、24、20、40、33。对同一棵树进行有效的后序遍历会产生什么序列解释一下
A        2, 7, 8, 14, 10, 20, 33, 40, 24, 16
B        2, 8, 7, 14, 10, 20, 33, 40, 24, 16
C        2, 7, 8, 14, 10, 20, 33, 24, 40, 16
D        2, 7, 8, 10, 14, 20, 24, 33, 40, 16

Twilight6 发表于 2022-5-5 13:28:23


答案是 B

前序遍历，即先根遍历，遇到一个节点就直接打印该节点，然后才进入左子树、后进入右子树

进入左右子树后的规则还是同样的先根遍历，又因为你这棵树是二叉搜索树，则通过前序遍历可以绘出此二叉树为：



然后可以得到后续遍历为：2-8-7-14-10-20-33-40-24-16

从图中有个小技巧，可以快速知道该树的后续遍历，将树各节点右边绘上一条横线

然后从根左边开始画线，沿着树节点边缘绘制曲线，遇到一个横杆，就填下一个节点即可，如图：



同理，先序在节点左边画横线，中序在中间画横线都可以用这种方法得到结果，当然这种方法肯定不如熟练掌握了三种遍历的速度

傻眼貓咪 发表于 2022-5-5 15:16:56

答案是B？
页: [1]
查看完整版本: 知道二叉树前序遍历序列找后序遍历