《数据结构（C语言版）第二版》第五章-树和二叉树（5.5.2 线索二叉树）

5.5.2 线索二叉树

该二叉树的先序序列为：-+a##*b##-c##d##/e##f##
该二叉树的中序序列为：a + b * c - d - e / f （需要增加括号说明）

#include <stdio.h>
#include <stdlib.h>typedef char TElemType;typedef struct BiThrNode
{TElemType data;struct BiThrNode* lchild;struct BiThrNode* rchild;int LTag;int RTag;
}BiThrNode,*BiThrTree;BiThrTree pre = NULL;  //全局变量void CreateBiTree(BiThrTree& T);
void InThreading(BiThrTree& p);
void InOrderThreading(BiThrTree& Thrt, BiThrTree T);
void InOrderTraverse_Thr(BiThrTree T);int main()
{BiThrTree Tree = NULL;BiThrTree Thrt = NULL;printf("请输入要用二叉链表表示的字符序列： ");CreateBiTree(Tree);InOrderThreading(Thrt, Tree);InOrderTraverse_Thr(Thrt);return 0;
}//按先序序列建立二叉树
void CreateBiTree(BiThrTree& T)
{TElemType ch = '\0';ch = getchar();if (ch == '#'){T = NULL;}else{T = (BiThrTree)malloc(sizeof(BiThrNode));T->data = ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}
}//算法 5.7  以结点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{pre->RTag = 0;   //在第一次循环时，pre指向头结点Thrt，此步会将Thrt->RTag值修改为0.//所以在执行完该函数之后，要在InOrderThreading函数中重新将Thrt->RTag赋为1}pre = p;InThreading(p->rchild);}
}//算法 5.8 带头结点的二叉树中序线索化
void InOrderThreading(BiThrTree& Thrt, BiThrTree T)
{Thrt = (BiThrTree)malloc(sizeof(BiThrNode));Thrt->LTag = 0; Thrt->RTag = 1;Thrt->rchild = Thrt; //Thrt->rchild被初始化为指向它本身，若上面thrt分配内存成功，则Thrt->rchild也不为空if (!T){Thrt->lchild = Thrt;}else{Thrt->lchild = T;pre = Thrt;InThreading(T); pre->rchild = Thrt;pre->RTag = 1;Thrt->RTag = 1; //InThreading函数会将Thrt->RTag改为0Thrt->rchild = pre;}	
}//算法 5.9 遍历中序线索二叉树
void InOrderTraverse_Thr(BiThrTree Thrt)
{ BiThrTree p =Thrt-> lchild; while (p != Thrt){while (p->LTag == 0){p = p->lchild;}printf(" %c", p->data);while (p->RTag == 1 && p->rchild != Thrt){p = p->rchild;printf(" %c", p->data);}p = p->rchild;}
}

按照上面的简易代码，利用先序序列对应的二叉树图，走一遍流程即可画出其对应的带头结点的中序线索二叉树链表。
下面的代码仅用于核对与矫正。

#include <stdio.h>
#include <stdlib.h>typedef char TElemType;typedef struct BiThrNode
{TElemType data;struct BiThrNode* lchild;struct BiThrNode* rchild;int LTag;int RTag;
}BiThrNode, * BiThrTree;BiThrTree pre = NULL;  //全局变量/*
-+a##*b##-c##d##/e##f##
ABC##DE#G##F###
-*a##b##c##
ABD##E##C##
*/void CreateBiTree(BiThrTree& T);
void InThreading(BiThrTree& p);
void InOrderThreading(BiThrTree& Thrt, BiThrTree T);
void InOrderTraverse_Thr(BiThrTree T);int main()
{BiThrTree Tree = NULL;BiThrTree Thrt = NULL;printf("请输入要用二叉链表表示的字符序列： ");CreateBiTree(Tree);InOrderThreading(Thrt, Tree);InOrderTraverse_Thr(Thrt);return 0;
}//按先序序列建立二叉树（先不用管线索）
void CreateBiTree(BiThrTree& T)
{TElemType ch = '\0';ch = getchar();if (ch == '#'){T = NULL;}else{T = (BiThrTree)malloc(sizeof(BiThrNode));T->data = ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}
}//算法 5.7  以结点p为根的子树中序线索化
// （先线索化左子树，再线索化根结点，最后线索化右子树）
/* 指针pre始终指向刚刚访问过的结点指针p指向当前访问的结点   */
void InThreading(BiThrTree& p)
{if (p){printf("\n\np = %c", p->data);}else{printf("\n\np = %c", '#');}if (p){if (pre){printf("\n当p不为空时：pre = %c", pre->data);}else{printf("\n当p不为空时：pre = %c", '#');}printf("\n当p不为空时：p = %c", p->data);if (p->lchild){printf("\n进行p的左子树线索化前：p->lchild = %c", p->lchild->data);}else{printf("\n进行p的左子树线索化前：p->lchild = %c", '#');}InThreading(p->lchild);//会一直往下找，找到最左下的结点，即二叉树中序序列的第一个结点。其一定是叶子结点，所以其左子树一定为空，从而跳出InThreading(p->lchild)这个函数//此时p指向的就是二叉树中序序列的第一个结点if (!p->lchild){if (p){printf("\n当p的左子树为空时：p = %c", p->data);}else{printf("\n当p的左子树为空时：p = %c", '#');}if (pre){printf("\n当p的左子树为空时：pre = %c", pre->data);}else{printf("\n当p的左子树为空时：pre = %c", '#');}if (p->rchild){printf("\n当p的左子树为空时：p->rchild = %c", p->rchild->data);}else{printf("\n当p的左子树为空时：p->rchild = %c", '#');}p->LTag = 1;p->lchild = pre;  //如果此处p指向二叉树中序序列的第一个结点，那么pre指向的就是其线索二叉树的头结点Thrt}else{p->LTag = 0;}if (!pre->rchild) //当pre指向线索二叉树的头结点Thrt时，其右子树被初始化了为它本身Thrt，不为空{if (pre){printf("\n当pre的右子树为空时：pre = %c", pre->data);}else{printf("\n当pre的右子树为空时：pre = %c", '#');}if (p){printf("\n当pre的右子树为空时：p = %c", p->data);}else{printf("\n当pre的右子树为空时：p = %c", '#');}if (pre->lchild){printf("\n当pre的右子树为空时：pre->lchild = %c", pre->lchild->data);}else{printf("\n当pre的右子树为空时：pre->lchild = %c", '#');}pre->RTag = 1;pre->rchild = p;}else{pre->RTag = 0;}pre = p;if (pre){printf("\n赋值后的pre为：pre = %c", pre->data);}else{printf("\n赋值后的pre为：pre = %c", '#');}if (p->rchild){printf("\n进行p的右子树线索化前：p->rchild = %c", p->rchild->data);}else{printf("\n进行p的右子树线索化前：p->rchild = %c", '#');}InThreading(p->rchild);}
}//算法 5.8 带头结点的二叉树中序线索化
void InOrderThreading(BiThrTree& Thrt, BiThrTree T)
{Thrt = (BiThrTree)malloc(sizeof(BiThrNode));Thrt->LTag = 0;Thrt->RTag = 1;Thrt->rchild = Thrt; //初始化if (T){printf("\n\n\n将二叉树T中序线索化为带头结点的线索二叉树Thrt时：T = %c", T->data);}else{printf("\n\n\n将二叉树T中序线索化为带头结点的线索二叉树Thrt时：T = %c", '#');}if (!T){Thrt->lchild = Thrt;}else{if (Thrt){printf("\n二叉树T不为空时：Thrt = %c", Thrt->data);}else{printf("\n二叉树T不为空时：Thrt = %c", '#');}Thrt->lchild = T;if (Thrt->lchild){printf("\nThrt->lchild = %c", Thrt->lchild->data);}else{printf("\nThrt->lchild = %c", '#');}pre = Thrt;if (pre){printf("\n进入单个结点线索化前，pre = %c", pre->data);}else{printf("\n进入单个结点线索化前，pre = %c", '#');}if (T){printf("\n进入单个结点线索化前，根结点T为：T = %c", T->data);}else{printf("\n进入单个结点线索化前，根结点T为：T = %c", '#');}InThreading(T);if (T){printf("\n单个结点线索化后，根结点T为：T = %c", T->data);}else{printf("\n单个结点线索化后，根结点T为：T = %c", '#');}if (pre){printf("\n单个结点线索化后，pre = %c", pre->data);printf("\n单个结点线索化后，pre->lchild = %c", pre->lchild->data);}else{printf("\n单个结点线索化后，pre = %c", '#');printf("\n单个结点线索化后，pre->lchild = %c", '#');}pre->rchild = Thrt;if (pre->rchild){printf("\n单个结点线索化后，pre->rchild = %c", pre->rchild->data);}else{printf("\n单个结点线索化后，pre->rchild = %c", '#');}pre->RTag = 1;Thrt->RTag = 1;Thrt->rchild = pre;if (Thrt->rchild){printf("\nThrt->rchild = %c", Thrt->rchild->data);}else{printf("\nThrt->rchild = %c", '#');}}
}//算法 5.9 遍历中序线索二叉树
void InOrderTraverse_Thr(BiThrTree T)
{BiThrTree p = T->lchild;if (T->lchild){printf("\n\n遍历时：T->lchild = %c", T->lchild->data);}else{printf("\n\n遍历时：T->lchild = %c", '#');}while (p != T){if (p){printf("\n当p不等于T时，p = %c", p->data);}else{printf("\n当p不等于T时，p = %c", '#');}if (T){printf("\n当p不等于T时，T = %c", T->data);}else{printf("\n当p不等于T时，T = %c", '#');}while (p->LTag == 0){p = p->lchild;if (p){printf("\n当p->LTag等于0时：新p = %c", p->data);}else{printf("\n当p->LTag等于0时：新p = %c", '#');}}printf("\n第一种情况输出的元素为： %c", p->data);while (p->RTag == 1 && p->rchild != T){p = p->rchild;printf("\n第二种情况输出的元素为： %c", p->data);}p = p->rchild;if (p){printf("\n新p = %c", p->data);}else{printf("\n新p = %c", '#');}}
}