线索二叉树学习笔记

学点东西，记点东西。

引入

为什么要学习这个*东西呢？先来想想二叉树的那三个遍历方法吧。

二叉树的遍历是很多人比较熟悉的，实际上，二叉树的遍历操作就是一个把非线性结构变成线性结构的过程。在线性序列中，每个结点有一个唯一的前驱和唯一的后继（头和尾这种就是有一个没有的）。在这个过程中，我们通过降维打击把树变成了线性表，这破坏了树的结构。有没有一种方法可以做到不进行降维打击也能存储前驱和后继的信息？

其实前驱和后继的信息只需要遍历就能得到的，还是那句话，查询次数多了总有你T的时候。所以还得想个靠谱的办法。

这看起来也许很简单，我在每个结点都保存一个前驱和后继的信息不就可以了？

~~嗯这确实可以，本题结束。~~

此时恰巧一位强迫症的路人经过，他会发现这个结构存储密度特别低，然后感觉非常不适。这是因为什么呢？有结论表明，有n个结点的二叉链表必然存在n+1个空链域。那么问题来了，这n+1个空链域能不能利用起来呢？

~~啊当然这么问的话肯定是能利用的起来是吧~~

实际上，考虑利用这些空链域来存放遍历后结点的前驱和后继信息，这就是线索二叉树构成的思想。采用既可以指示其前驱又可以指示后继的双向链接结构的二叉树被称为线索二叉树。

等等，双向链接结构？二叉链表一般是单向的，这意味着只能通过祖先访问子孙。既然要能够查找前驱，这肯定是不足够的。既然链表可以双向，那二叉链表为什么不可以？这是完全没问题的嘛。

假如这样规定：若结点有左子树，则其lchild表示左孩子，否则令其指示其前驱，若结点有右子树，则其rchild表示右孩子，否则令其指示其后继。同时为了避免混淆（lchild，rchild虽然指示了区域，但是并不知道到底指示的是什么），还需要增加ltag和rtag这两个字段，其中值为0时表示指示孩子，值为1时表示指示前驱或后继。

typedef struct BiThrNode {
    TElemType data; // TElemType是抽象数据类型啦，它是什么都可以的
    BiThrNode *lchild, *rchild;
    int ltag, rtag;
}BiThrNode, *BiThrTree;

以这种结点结构构成的二叉链表作为二叉树的存储结构，称为线索链表。其中指向结点前驱和后继的指针称为线索。使用此结点构筑的二叉链表（二叉树）就叫做线索二叉树。对二叉树以某种次序使其变为线索二叉树的过程叫做二叉树的线索化。

线索二叉树的构造

由于线索二叉树构造的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。显然，对二叉树按照不同的遍历次序进行线索化得到的线索二叉树是不同的。

为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，指针p指向当前访问的结点，由此记录下遍历过程中的访问先后关系。

以结点p为根的子树中序线索化

如果p非空，左子树递归线索化。
如果p的lchild为空，则给p加上左线索，ltag置为1，p的左孩子指针指向pre（前驱），否则将p的ltag置为0.
如果pre的rchild为空，则给pre加上右线索，rtag置为1，pre的右孩子指针指向p（后继），否则将pre的rtag置为0.
将pre指向刚访问过的结点p，即pre = p;

void InThreading(BiThrTree p) {
	if (p) {
		InThreading(p->lchild);
		if (!p->lchild) {
			p->ltag = 1;
			p->lchild = pre;
		}
	}
	else {
		p->ltag = 0;
	}
    if (!pre->rchild) {
        pre->rtag = 1;
        pre->rchild = p;
    }
    else {
        p->rtag = 0;
    }
    pre = p;
    InThreading(p->rchild);
}
/*
pre是全局变量，初始化时其右孩子指针为空，便于在树的最左点开始建立线索
*/

带头结点的二叉树中序线索化

void InOrderThreading(BiThrTree &thrt, BiThrTree T) {
    thrt = new BiThrNode;
    thrt->ltag = 0;
    thrt->rtag = 1;
    thrt->rchild = thrt;
    if (!T)
        thrt->lchild = thrt;
    else {
        thrt->lchild = T;
        pre = thrt;
        InThreading(T);
        pre->rchild=Thrt;
        pre->rtag = 1;
        thrt->rchild=pre;
    }
}
/*
pre仍然是全局变量。首先建立头结点，头结点有左孩子，若树非空，则其左孩子为树根，头结点的右孩子指针为右线索。初始化时右指针指向自己，若树为空，则左指针也指向自己。
头结点的左孩子指向根，pre初值指向头结点。然后调用中序线索化的算法，算法结束后，pre为最右结点，pre的右线索指向头结点。
*/

线索二叉树的遍历

现在我们已经构造好了线索二叉树。好了，现在好像是可以不通过降维打击也能方便查到某个结点的前驱和后继了。

在中序线索二叉树中查找

查找前驱的方法：
- 若p->ltag == 1，则p的左链指示其前驱
- 若p->ltag == 0，则说明p有左子树，结点的前驱是遍历左子树时最后访问的一个结点（左子树中最右下的结点）。
查找后继的方法：
- 若p->rtag == 1，则p的右链指示其后继
- 若p->rtag == 0，则说明p有右子树。根据中序遍历的规律可知，结点的后继应该是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。

遍历中序线索二叉树

首先指针p指向根结点，p为非空树或遍历未结束时，循环执行下面的操作：沿左孩子向下，到达最左下结点*p，它是中序的第一个结点；访问*p；沿右线索反复查找当前结点*p的后继结点并访问后继结点，直至右线索为0或者遍历结束；转向p的右子树。

void InOrderTraverse_Thr(BiThrTree T) {
    p = T->rchild;
    while (p != T) {
        while (p->ltag == 0)
            p = p->lchild;
        cout << p->data;
        while (p->rtag == 1 && p->rchild != T) {
            p = p->rchild;
            cout << p->data;
        }
        p = p->rchild;
    }
}

遍历线索二叉树的时间复杂度为O(n)，空间复杂度为O(1)，这是因为线索二叉树的遍历不需要使用栈来递归操作。