声明

本节内容来源于 BiliBili视频数据结构与算法基础（青岛大学-王卓） 的 P94，本博客仅作笔记整理和学习记录，部分图片来自视频截图。

线索二叉树

Q：为什么要研究线索二叉树？

当用二叉链表作为二叉树的存储结构时，可以很方便地找到某个结点的左右孩子；但一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点。

Q：如何寻找特定遍历序列中二叉树结点的前驱和后继？

  1. 通过遍历寻找————费时间。
  2. 再增设前驱、后继指针域————增加了存储负担。
  3. 利用二叉链表中的空指针域。

二叉链表中空指针域的数量

利用二叉链表中的空指针域：
如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某结点的右孩子为空，则将空的右孩子指针域改为指向其后继
————这种改变指向的指针称为“线索”
加上了线索的二叉树称为线索二叉树(Threaded Binary Tree) 对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化。

线索化过程

为区分 lrchid 和 rchild 指针到底是指向孩子的指针，还是指向前驱或有后继的指针，对二叉链表中每个结点增设两个标志域 ltag 和 rtag ，并约定：

标志域 含义
Itag = 0 Ichild 指向该结点的左孩子
ltag = 1 Ichild 指向该结点的前驱
rtag = 0 rchild 指向该结点的右孩子
rtag = 1 rchild 指向该结点的后继 
1
2
3
4
5
typedef struct BiThrNode{
  int data;
  int ltag, rtag;
  struct BiThrNode *lchild, rchild;
}BiThrNode, *BiThrTree;

⭐为了方便数据的处理，我们要额外增加一个头节点：

增设头节点