第327章 半 (2/7)

的左兄弟结点

y

d.

以

y

为根的子树的最右下结点

【2014

年】若对如下的二叉树进行中序线索化，则结点

x

的左、右线索指向的结点分

别是______。

a.e、c

b.e、a

c.d、c

d.b、a

考点

14：树和二叉树（★★★）

1、树转化为二叉树

对于一般的树，可以方便地转换成一棵唯一的二叉树与之对应。将树转换成二叉树在“孩

子兄弟表示法”中已给出，其详细步骤是：

1

加虚线。在树的每层按从“左至右”的顺序在兄弟结点之间加虚线相连。

2

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

3

旋转。将树顺时针旋转

450，原有的实线左斜。

4

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

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

◆

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

◆

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

树中该结点的兄弟结点。

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

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

◆

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

◆

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

2、二叉树转换成树

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

其步骤是：