第九中文网

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

第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的后根遍历序列是：

不当舔狗后，校花哭问为什么！  快穿：病美人仙君又拿白月光剧本  神奇宝贝：羁绊的旅途  这个影帝只想考证  玄学大佬种田算命捉鬼  红楼之剑天外来  棒打鸳鸯的恶人主母，重生摆烂了  我在无限流游戏里为所欲为  建立超级家族：从52年隐居开始  我有个死要钱的系统  末世：战姬指挥官  带着原神祈愿系统穿越到诡异世界  除了我，全家都穿越了  四合院之罪恶克星  异界：魔王降临  苟在修仙世界当反派  综影视：祖龙杀疯了，我负责躺赢  江与溪同归麒麟美人骨  凡人神算  归零：云海梦境，山海有灵