齐林书院

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

第386章 裙子（第3页）

去连线。

除最左的第一个子结点外，父结点与所有其它子结点的连线都去掉。

3

旋转。

将树顺时针旋转

450，原有的实线左斜。

4

整型。

将旋转后树中的所有虚线改为实线，并向右斜。

这样转换后的二叉树的特点是：

◆

二叉树的根结点没有右子树，只有左子树；

◆

左子结点仍然是原来树中相应结点的左子结点，而所有沿右链往下的右子结点均是原来

树中该结点的兄弟结点。

由于二叉树和树都可用二叉链表作为存储结构，对比各自的结点结构可以看出，以二叉

链表作为媒介可以导出树和二叉树之间的一个对应关系。

◆

从物理结构来看，树和二叉树的二叉链表是相同的，只是对指针的逻辑解释不同而已。

◆

从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树一定为空。

2、二叉树转换成树

对于一棵转换后的二叉树，如何还原成原来的树?

其步骤是：

（1）加虚线。

若某结点

i

是其父结点的左子树的根结点，则将该结点

i

的右子结点以及沿右

子链不断地搜索所有的右子结点，将所有这些右子结点与

i

结点的父结点之间加虚线相连，

如图（a）所示。

（2）去连线。

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

（3）规整化。