九妖小说网

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

第327章 半（第1页）

设一棵二叉树有 n 个结点，则有 n-1 条边(指针连线) ， 而 n 个结点共有 2n 个指针域

(Lchild 和 Rchild) ，显然有 n+1 个空闲指针域未用。则可以利用这些空闲的指针域来存放结

点的直接前驱和直接后继信息。

为避免混淆,对结点结构加以改进，增加两个标志域，如图所示。用这种结点结构构成

的二叉树的存储结构；叫做线索链表；指向结点前驱和后继的指针叫做线索；

2、线索二叉树的构建

按照某种次序遍历，加上线索的二叉树称之为线索二叉树。线索化二叉树: 二叉树的线

索化指的是依照某种遍历次序使二叉树成为线索二叉树的过程。

线索化的过程就是在遍历过程中修改空指针使其指向直接前驱或直接后继的过程。

【2013 年】若 x 是后序线索二叉树中的叶结点，且 x 存在左兄弟结点 Y，则 x 的右

线索指向的是______。

A. x 的父结点 b. 以 Y 为根的子树的最左下结点

c. x 的左兄弟结点 Y d. 以 Y 为根的子树的最右下结点

【2014 年】若对如下的二叉树进行中序线索化，则结点 x 的左、右线索指向的结点分

别是______。

A．e、c b．e、a c．d、c d．b、a 考点 14：树和二叉树（★★★）

1、树转化为二叉树

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

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