什么是线索二叉树

对一棵二叉树中所有节点的空指针域按照某种遍历方式加线索的过程叫作线索化，被线索化了的二叉树称为线索二叉树。因此三种不同的遍历方式衍生出三种线索二叉树。

数据结构-线索二叉树 - 图1
原本中序遍历是 C B D A 顺序，从 D 到 A 的过程中就原本只需要一个指向即可，但是采用递归的方法就需要提前将 B 压入栈，D 到 A 实际上是 D B A。但是我们线索化之后就不需要递归了，有了 D 指向 A 的直接引用，用迭代的方法来遍历。

递归遍历 O(n) O(n)，线索化后的遍历空间复杂度为 O(1)，时间复杂度由于仍需要遍历每个结点所以无法减少。

线索化

image.png

  1. 如果ltag=0，表示指向节点的左孩子。如果ltag=1，则表示lchild为线索，指向节点的直接前驱
  2. 如果rtag=0，表示指向节点的右孩子。如果rtag=1，则表示rchild为线索，指向节点的直接后继


  1. typedef struct TBNode
  2. {
  3.     char data;
  4.     int ltag,rtag;
  5.     struct TBNode *lchild;
  6.     struct TBNode *rchild;
  8. }TBNode;
  10. BiThrTree pre = NULL;
  12. typedef enum {
  13.     Link,
  14.     Thread
  15. }PointerTag;

全局变量来记录状态，也可以多传一个参数来记录前驱。

  1. void InThreading(BiThrTree p, BiThrTree* pre) {
  2.     //如果当前结点存在
  3.     if (p) {
  4.         InThreading(p->lchild, pre);
  5.         if (!p->lchild) {
  6.             p->Ltag = Thread;
  7.             p->lchild = pre;
  8.         }
  9.         if (pre && !pre->rchild) {
  10.             pre->Rtag = Thread;
  11.             pre->rchild = p;
  12.         }
  13.         pre = p;
  14.         InThreading(p->rchild, pre);
  15.     }
  16. }

将中序遍历的代码变成线索化的代码，由于后继比较难找，所以我们在一个结点的后继中来判断该节点是否需要后继。这样就导致中序遍历的最后一个结点没有办法将它的右标识位设置为 1 。因为最后一个结点的两边都是空，没有办法通过 pre 对 尾结点进行判断，直接结束掉了函数。但是 pre 此时已经是尾结点了。

  1. if(pre->rchild==NULL){
  2.     pre-Rtag=1;//处理最后一个结点
  3. }

一定要在线索化函数 InThreading 后写上上面这个代码。这样整体就完整了，第一个结点没有前驱，最后一个结点没有后继，对于标识位都是 1。

参考文章

线索二叉树的遍历

  1. void InOrderThraverse_Thr(BiThrTree p) {
  2.     while (p) {
  3.         if (p->Ltag == Link) {
  4.             p = p->lchild;
  5.         }
  6.         printf("%c", p->data);
  7.         while (p->Rtag == Thread && p->rchild != NULL) {
  8.             p = p->rchild;
  9.             printf("%c ", p->data);
  10.         }
  11.         p = p->rchild;
  12.     }
  13. }

  • 3~5 先找到中序遍历的第一个结点

  • 找到之后开始进行中序遍历

  • 由于已经是第一个结点，所以判断结点右侧即可，有后继遍历后继，无后继正常入树

  • 每次大循环开始都是视为一颗新树，重新执行上面步骤