树和森林的遍历
标签: 数据结构
学习人数: 6180


全屏播放
赞赏支持

树的遍历的定义:以某种方式访问树中的每一个结点,且仅访问一次。
树的遍历主要有先根遍历后根遍历

这里写图片描述

根据这幅图:
树的先根遍历:A-B-E-F-G-C-H-D-I-J
对应的二叉树的先序遍历:A-B-E-F-G-C-H-D-I-J

二者是一致的。

树的后根遍历:E-F-G-B-H-C-I-J-D-A
对应的二叉树的后序遍历:G-F-E-H-J-I-D-C-B-A
对应的二叉树的中序遍历:E-F-G-B-H-C-I-J-D-A(与树的后根遍历相一致)

注意到我们并没有定义一般树的中根遍历,因为子结点该怎么分两部分并没有定义,所以只定义先、后根。

以上只是模拟证实。

 

森林的遍历:需要澄清的是,只有二叉树森林才有中序遍历与完整二叉...

登录查看完整内容


课后作业

课后习题

 

【2019年真题】若将一棵树T转化为对应的二又树BT,则下列对BT的遍历中,其遍历序列与T的后根遍历序列相同的是
A. 先序遍历      B. 中序遍历      C. 后序遍历      D. 按层遍历

参考答案:B


登录后发布评论

暂无评论,来抢沙发