荨默小说网

手机浏览器扫描二维码访问

第327章 半（第2页）

2、二叉树转换成树

对于一棵转换后的二叉树，如何还原成原来的树?其步骤是：

（1）加虚线。若某结点i是其父结点的左子树的根结点，则将该结点i的右子结点以及沿右

子链不断地搜索所有的右子结点，将所有这些右子结点与i结点的父结点之间加虚线相连，

如图（a）所示。

（2）去连线。去掉二叉树中所有父结点与其右子结点之间的连线，如图（b）所示。

（3）规整化。将图中各结点按层次排列且将所有的虚线变成实线，如图（c）所示。

3、森林转换成二叉树

转换步骤：

①将F={T1，T2，?，Tn}中的每棵树转换成二叉树。

②按给出的森林中树的次序，从最后一棵二叉树开始，每棵二叉树作为前一棵二叉树的

根结点的右子树，依次类推，则第一棵树的根结点就是转换后生成的二叉树的根结点，如图

所示。

4、二叉树转换成森林

上述转换规则是递归的，可以写出其递归算法。以下给出具体的还原步骤。

①去连线。将二叉树B的根结点与其右子结点以及沿右子结点链方向的所有右子结点的连

线全部去掉，得到若干棵孤立的二叉树，每一棵就是原来森林F中的树依次对应的二叉树。②二叉树的还原。将各棵孤立的二叉树按二叉树还原为树的方法还原成一般的树。

5、树的遍历

由树结构的定义可知，树的遍历有二种方法。

（1）先序遍历：先访问根结点，然后依次先序遍历完每棵子树。如图，先序遍历的次序是：

ABCDEFGIJHK

（2）后序遍历：先依次后序遍历完每棵子树，然后访问根结点。如图，后序遍历的次序是：

CDBFIJGHEKA

树的先序遍历实质上与将树转换成二叉树后对二叉树的先序遍历相同。

树的后序遍历实质上与将树转换成二叉树后对二叉树的中序遍历相同

【2019年】若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列

本小章还未完，请点击下一页继续阅读后面精彩内容！

与T的后根遍历序列相同的是（）

A.先序遍历B.中序遍历C.后序遍历D.按层遍历

【2020年】已知森林F及与之对应的二叉树T，若F的先根遍历序列是a，b，c，d，e，f，中

根遍历序列是b，a，d，f，e，c则T的后根遍历序列是：

毛绒小兔饲养指南  领主：我的蚁族无限进化  洪荒：抛弃系统！我认鸿钧为义父  重生三次后，可怜崽被团宠啦  被迫照顾主角后走不掉了[穿书]  元始天尊传  奇世界  开局我有神技能  重生之都市丹帝：我已活了十万载  穿越王朝当咸鱼，日刷三宝  全员好人，只有宿主是变态  综穿之我只想过享福生活  疯狗总裁和他的美人助理  全民领主：我的爆率百分百  求生：魔法灾变世界  秦时：开局鬼谷饭桌多了一双筷子  八岁开始模拟的我觉醒重瞳  黑塔利亚：生存游戏  军婚三年未见，离婚他急红眼  大佬他怀了野狗崽[重生]