鱼C论坛

 找回密码
 立即注册
查看: 1902|回复: 2

[已解决]知道二叉树前序遍历序列找后序遍历

[复制链接]
发表于 2022-5-5 13:28:22 | 显示全部楼层 |阅读模式
10鱼币
二叉搜索树的取值为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
最佳答案
2022-5-5 13:28:23

答案是 B

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

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

tree.jpg

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

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

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

Snipaste_2022-05-05_18-59-10.jpg

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

最佳答案

查看完整内容

答案是 B 前序遍历,即先根遍历,遇到一个节点就直接打印该节点,然后才进入左子树、后进入右子树 进入左右子树后的规则还是同样的先根遍历,又因为你这棵树是二叉搜索树,则通过前序遍历可以绘出此二叉树为: 然后可以得到后续遍历为:2-8-7-14-10-20-33-40-24-16 从图中有个小技巧,可以快速知道该树的后续遍历,将树各节点右边绘上一条横线 然后从根左边开始画线,沿着树节点边缘绘制曲线,遇到一个横杆, ...
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-5-5 13:28:23 | 显示全部楼层    本楼为最佳答案   

答案是 B

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

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

tree.jpg

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

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

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

Snipaste_2022-05-05_18-59-10.jpg

同理,先序在节点左边画横线,中序在中间画横线都可以用这种方法得到结果,当然这种方法肯定不如熟练掌握了三种遍历的速度
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-5-5 15:16:56 From FishC Mobile | 显示全部楼层
答案是B?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-23 21:31

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表