对应章节数据结构 → 树与二叉树 → 线索二叉树这两题真正考的是三个点二叉树为什么有n1个空指针线索化时空指针分别如何改造成“前驱线索”和“后继线索”“有线索”不等于“每个结点都能通过一根线索直接找到前驱和后继”。一、做题前先建立统一模型设结点结构为[lchild] [data] [rchild]在线索二叉树中通常再增加两个标志位ltag 0lchild 指向真正的左孩子 ltag 1lchild 是前驱线索 rtag 0rchild 指向真正的右孩子 rtag 1rchild 是后继线索也就是说原来为空的左指针 → 可以改成“前驱线索” 原来为空的右指针 → 可以改成“后继线索”注意只有原来为空的指针域才能拿来做线索。如果某个结点本来就有左孩子或右孩子那么对应的指针域仍然必须指向孩子不能同时拿来存线索。二、为什么 n 个结点的二叉树有 n1 个空指针每个结点有两个孩子指针因此共有2n 个指针域而一棵有n个结点的二叉树共有n - 1 条边每条边对应一个非空孩子指针因此非空指针有n-1个。所以空指针数为2n - (n - 1) n 1因此n 个结点的二叉树一共有 n1 个空链域。线索二叉树正是利用这些空链域来保存遍历序列中的前驱、后继信息。第 25 题题目一棵左子树为空的二叉树在先序线索化后其中空的链域的个数是 。选项A. 不确定 B. 0 个 C. 1 个 D. 2 个答案D2 个。1. 先抓住“先序遍历”的第一个结点先序遍历顺序根 → 左 → 右所以整棵树先序遍历的第一个结点一定是根结点。题目又告诉我们根的左子树为空因此根结点的左指针本来就是空的。画出来A / \ NULL 右子树由于 A 是先序遍历的第一个结点所以A 没有前驱而 A 的左指针又恰好是空指针本来应该用来存“前驱线索”但它没有前驱因此A.lchild NULL所以这里已经确定有1 个空链域。2. 再看先序遍历的最后一个结点设先序遍历序列为A → ... → X其中 X 是最后访问的结点。X 不可能还有孩子。因为如果 X 还有左孩子或右孩子那么按照先序遍历访问完 X 之后还必须继续访问它的孩子X 就不可能是最后一个结点。所以最后一个结点 X 一定是叶子结点也就是X / \ NULL NULLX 是整个先序序列的最后一个结点因此X 没有后继X 的右指针本来为空本应改造成“后继线索”但它没有后继所以X.rchild NULL这又产生1 个空链域。3. 所以一共是两个第一个结点根 左指针 → 没有前驱 → NULL 最后一个结点 右指针 → 没有后继 → NULL因此空链域总数 1 1 2答案D. 2 个4. 用具体例子看最直观假设原树是A / \ NULL B / \ C D先序遍历A → B → C → D线索化之后A 左边原本为空 A 又没有前驱 所以 A.left NULL C C 没有左右孩子 先序前驱是 B后继是 D C.left → B C.right → D D D 是先序最后一个结点 D 没有后继 所以 D.right NULL最终仍然为空的是A.left NULL D.right NULL正好2 个。5. 一个特殊情况也不影响答案如果整棵树只有一个根结点A / \ NULL NULL先序序列只有AA 同时没有前驱 没有后继于是A.left NULL A.right NULL仍然是2 个空链域。第 26 题题目在线索二叉树中下列说法不正确的是 。选项A. 在中序线索树中若某结点有右孩子 则其后继结点是它的右子树的最左下结点。 B. 在中序线索树中若某结点有左孩子 则其前驱结点是它的左子树的最右下结点。 C. 线索二叉树是利用二叉树的 n1 个空指针 来存放结点的前驱和后继信息的。 D. 每个结点通过线索都可以直接找到它的前驱和后继。答案D 错误。A 为什么正确中序遍历顺序左子树 → 根 → 右子树假设当前结点为 A而且 A 有右孩子A \ B / C / D访问完 A 之后下一步进入 A 的右子树。但右子树中第一个被中序访问的结点不是一定是 B而是右子树中最左边的结点在上图中A 的中序后继 D所以若某结点有右孩子它的中序后继是右子树中最左下的结点。因此 A 正确。B 为什么正确同理中序遍历中左子树 → 根 → 右子树如果 A 有左孩子那么在访问 A 之前必须先访问完整个左子树。左子树中最后被中序访问的结点就是左子树中最右边的结点例如A / B \ C \ D则A 的中序前驱 D所以若某结点有左孩子它的中序前驱是左子树中最右下的结点。因此 B 正确。C 为什么正确前面已经证明n 个结点 → 一共有 2n 个孩子指针域 实际边数 → n - 1 空指针数 → 2n - (n - 1) → n 1这些空指针正好可以利用起来存放遍历序列中的前驱和后继信息。因此 C 正确。D 为什么错误D 的说法是每个结点通过线索都可以直接找到前驱和后继问题出在两个字“每个” “直接”线索只存在于原本为空的孩子指针域中。如果某个结点本来有左孩子ltag 0那么lchild 指向左孩子它就不是前驱线索。此时想找这个结点的中序前驱不能直接顺着 lchild 就得到答案而是要先进入左子树 再不断向右 找到左子树中最右边的结点同理如果某结点本来有右孩子rtag 0那么 rchild 是真正的右孩子不是后继线索。要寻找中序后继需要先进入右子树 再不断向左 找到右子树中最左边的结点所以并不是每个结点都可以靠“一根线索”直接找到前驱和后继。第 26 题最关键的图对于中序线索树找前驱和后继可以这样记当前结点 P / \ / \ 有左孩子 有右孩子 | | v v 左子树一直向右 右子树一直向左 | | v v 中序前驱 中序后继如果本来没有左孩子ltag 1 lchild 直接就是前驱线索如果本来没有右孩子rtag 1 rchild 直接就是后继线索所以完整模型是找中序前驱 ① ltag 1 → lchild 就是前驱直接得到 ② ltag 0 → 有左子树 → 进入左子树 → 一直向右 → 最右结点是前驱找中序后继 ① rtag 1 → rchild 就是后继直接得到 ② rtag 0 → 有右子树 → 进入右子树 → 一直向左 → 最左结点是后继这正是 D 错误的原因。两题放在一起总结必须记住的 4 句话1. n 个结点的二叉树有 n1 个空指针。 2. 空左指针可改造成“前驱线索”。 3. 空右指针可改造成“后继线索”。 4. 有孩子时对应指针仍然是孩子指针 因此不一定能通过线索直接得到前驱/后继。中序前驱 / 后继口诀有左孩子 前驱 左子树最右 有右孩子 后继 右子树最左 无左孩子且已线索化 左线索 前驱 无右孩子且已线索化 右线索 后继第 25 题识别信号题目出现先序线索化 根的左子树为空立即想到根是先序第一个结点 → 没有前驱 → 左指针又正好为空 → 留下一个 NULL 最后一个先序结点 → 没有后继 → 右指针留下一个 NULL 总共 2 个复盘点复盘点 1线索只能占用“空指针”不要把线索理解成给每个结点额外增加两个前驱/后继指针。线索化本质是废物利用把原本为空的孩子指针拿来存前驱/后继。复盘点 2“有线索二叉树”不代表前驱后继都能 O(1) 直接顺指针得到如果对应方向本来有孩子那么那个指针就是孩子指针不是线索。因此中序线索树中有左孩子 → 找前驱要去左子树最右边 有右孩子 → 找后继要去右子树最左边复盘点 3第一个结点没有前驱最后一个结点没有后继任何遍历序列都可以先从这个角度判断第一个结点 前驱不存在 最后一个结点 后继不存在但“前驱/后继不存在”是否会形成一个真正的空链域还要看这个结点对应的孩子指针本来是不是空的。这就是第 25 题专门强调“左子树为空”的原因。