上回（半年前）我们讲了二叉树，如果我们要找到二叉树某序遍历下的前驱和后继，我们需要对其作动态遍历求得，比较费时；或者给每个结点增加两个指针域prior和next，但比较费空间。
有没有既能省时间，又能省空间的呢？有！
今天我们浅涉一下线索二叉树。【断更，开续】
复习：某序遍历
对于下图中的二叉树，我们采用3种遍历方式，得出的结果分别如下：
1.先序遍历
ABDEGCFH
2.中序遍历
在我显示出当前结点前，先查看它有没有未经遍历的左子树，如有则左子树先显示。该结点显示后，才能显示其右子树的所有内容。
DBGEACHF
3.后序遍历
DGEBHFCA
和你想的一样吗，如果不一样，那么请打开我主页的【数据结构】五分钟自测主干知识（十）
二叉树
https://blog.csdn.net/2301_79853895/article/details/136993369?fromshare=blogdetail&sharetype=blogdetail&sharerId=136993369&sharerefer=PC&sharesource=2301_79853895&sharefrom=from_link
去复习一下
线索二叉树
n个结点的二叉链表中有n+1个空指针，可以利用这些空指针来指向结点某序遍历下的前驱和后继。
也就是说，结点无左子树时，lchild不再指向NULL，而被利用去指示该结点的某序前驱；
结点无右子树时，rchild不再指向NULL，而被利用去指示该结点的某序后继；
称指示前驱和后继的指针为线索(Thread)。
为区别指针和线索，引入两个标志域，左标志ltag和右标志rtag
tag为0时，指向左（右）孩子；为1时，指向左（右）线索。
这种增加了线索的二叉树称为线索二叉树（Threaded Binary Tree），相应地链式存储结构称为线索链表。结点类型定义如下：
typedef struct BiThrNode{TElemType data;struct BiThrNode *lchild,*rchild;unsigned char ltag,rtag;
}BiThrNode,*BiThrTree;线索化
不同的遍历次序，会形成不同的线索二叉树。对二叉树做某种次序的遍历，使其变为线索二叉树的操作，称为线索化
如下图：
结合上面某序遍历的方式，自己推导一下某序线索二叉树。
作为最常见好用的线索化，我们来讨论一下中序线索化算法：
BiThrTree pre = NULL;//pre为全局变量
void InThreading (BiThrTree T){//已先设T中每个结点的ltag和rtag的初值为0if(!T) return;InThreading(T->lchild);if(pre && pre->lchild){pre->rtag=1;pre->rchild=T;}//线索rchild指向后继if(!T->lchild){T->ltag=1;T->lchild=pre;}//线索lchild指向前驱pre=T;//保持pre指向T的中序前驱InThreading(T->rchild);
}查找某结点p后继的算法（由于对称性，找前驱类同）
BiThrTree GetNext(BiThrTree p){if(p->rtag==1) return p->rchild;else{BiThrTree q;q=p->rchild;while (q->ltag==0) q=q->lchild;return q;}
}时间复杂度为 ，无需用栈，无递归算法，速度很快
使用GetNext，可以写出进行中序遍历的方法：
void InOrder(BiThrTree T){if(!T) return;BiThrTree p=T;while(p->ltag==0)p=p->lchild;do{visite(p->data);p=GetNext(p);}while (p!=NULL);
}
线索二叉树的内容就到此为止，它给我们提供了查找前驱和后继上的方便。
下一讲我们将来讲解“树和森林” 。
链接如下（暂未更新）