目录
一、线索二叉树的定义
将传统的二叉列表的空指针指向其前驱或者后继的指针，这样就可以像遍历单链表那样方便地遍历二叉树，以这种结点构成的二叉列表称为线索链表。加上线索的二叉树称为线索二叉树。
线索二叉树的结点结构如图：
ltag
data
rtag
规定：
若无左子树，令 指向其前驱节点；若无右子树，令 指向其后继结点。
线索二叉树的存储结构描述如下：
typedef struct ThreadNode
{
ElemType data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag; //左右线索标志
二、中序线索二叉树的构造
二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到数据结构 二叉树实验报告，因此线索化的实质就是遍历一次二叉树。
以中序线索二叉树的建立为例。
附设指针pre指向刚刚访问过的结点，指针p指向正在访问的结点数据结构 二叉树实验报告，即pre指向p的前驱。在中序遍历的过程中，检查p的左指针是否为空，若为空就将它指向pre；检查pre的右指针是否为空，若为空就将它指向p，如图所示。
通过中序遍历建立中序线索二叉树的主过程算法如下：
void CreateInThread(ThreadTree T)
{
ThreadTree pre = NULL;
if (T != NULL) //非空二叉树，进行线索化
{
<p>![数据结构 二叉树实验报告_树与二叉树的转换课程设计_有序树和二叉树的区别][4]
InThread(T, pre); //线索化二叉树
pre->rchild = NULL; //处理遍历的最后一个节点
pre->rtag = 1;
}</p>
其中，递归函数 函数为：
void InThread(ThreadTree& p, ThreadTree& pre)
{
if (p != NULL)
{
InThread(p->lchild, pre); //递归，线索化左子树
if (p->lchild == NULL) // 左子树为空，建立前驱线索
{
p->lchild = pre;
p->ltag = 1;
}
if (pre != NULL && pre->rchild == NULL)
{
pre->rchild = p; //建立前驱结点的后继线索
pre->rtag = 1;
}
pre = p; //标记当前结点成为刚刚访问过的结点
InThread(p->rchild, pre); //递归，线索化右子树
}
三、中序线索二叉树的遍历
在对其进行遍历时，只要先找到序列中的第一个结点，然后依次找结点的后继，直至其后继为空。
在中序线索二叉树中找结点后继的规律是：若其右标志为“1”，则右链为线索，指示其后继，否则遍历右子树中第一个访问的结点（右子树中最左下的结点）为其后继。不含头结点的线索二叉树的遍历算法如下：
求中序线索二叉树中中序序列下的第一个结点：
ThreadNode Firstnode(ThreadNode p)
{
while (p->ltag == 0) p = p->lchild; //最左下结点（不一定是叶结点）
return p;
求中序线索二叉树中结点p在中序序列下的后继：
ThreadNode Nextnode(ThreadNode p)
{
if (p->rtag == 0) return Firstnode(p->rchild);
else return p->rchild; //rtag==1,直接返回后继线索
利用上面两个算法，可以写出不含头结点的中序线索二叉树的中序遍历的算法：
<p><pre>void InOrder(ThreadTree T)
{
for (ThreadNode* p = Firstnode(T); p != NULL; p = Nextnode(p))
cout data > d;
if (d == '#')
T = NULL;
else
{
T = (ThreadTree)malloc(sizeof(ThreadNode));
T->data = d;
T->ltag = 0;
T->rtag = 0;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}}
void InThread(ThreadTree& p, ThreadTree& pre)
{
if (p != NULL)
{
InThread(p->lchild, pre); //递归，线索化左子树
if (p->lchild == NULL) // 左子树为空，建立前驱线索
{
p->lchild = pre;
p->ltag = 1;
}
if (pre != NULL && pre->rchild == NULL)
{
pre->rchild = p; //建立前驱结点的后继线索
pre->rtag = 1;
}
pre = p; //标记当前结点成为刚刚访问过的结点
InThread(p->rchild, pre); //递归，线索化右子树
}}
void CreateInThread(ThreadTree T)
{
ThreadTree pre = NULL;
if (T != NULL) //非空二叉树，进行线索化
{
InThread(T, pre); //线索化二叉树
pre->rchild = NULL; //处理遍历的最后一个节点
pre->rtag = 1;
}}
ThreadNode Firstnode(ThreadNode p)
{
while (p->ltag == 0) p = p->lchild; //最左下结点（不一定是叶结点）
return p;
}
ThreadNode Nextnode(ThreadNode p)
{
if (p->rtag == 0) return Firstnode(p->rchild);
else return p->rchild; //rtag==1,直接返回后继线索}
void InOrder(ThreadTree T)
{
for (ThreadNode* p = Firstnode(T); p != NULL; p = Nextnode(p))
cout data