利用二叉链表中的空指针域：
- 如果某个节点的左孩子为空，则将空的左孩子的指针域改为指向其前驱；
- 如果某个节点的右孩子为空，则将空的右孩子的指针域改为指向其后继；
- 这种改变指向的指针称为“线索”，加上了线索的二叉树称为线索二叉树，对二叉树按某种遍历次序使其变为线索二叉树的过程叫做线索化。
为区分lchild和rchild指针到底是指向孩子的指针还是指向前驱后继的指针，对二叉链表的每个结点增设两个标识域ltag和rtag，并约定：
- ltag = 0 lchild指向该节点的左孩子
- ltag = 1 lchild指向该节点的前驱
- rtag = 0 rchild指向该节点的右孩子
- rtag = 1 rchild指向该节点的后继
增加头结点
增加一个头结点
- ltag = 0，lchild指向根节点
- rtag = 1，rchild指向遍历序列中最后一个结点
- 遍历序列中第一个节点的lc域和最后一个结点的rc域都指向头结点，如图所示。
- 找到了前驱，就可以找到头结点，通过头结点又可以访问到其他的节点；
- 而当我们找到了最后的一个节点，有可以顺着指针找到头结点再找到其他的节点。
线索二叉树的数据结构
typedef enum{ link, //表示指向左右孩子的指针 thread, //表示指向前驱后继的线索 }TreePointTag; typedef struct TbinaryTree{ char data; struct TbinaryTree *lchild; struct TbinaryTree *rchild; TreePointTag ltag; TreePointTag rtag; }TbinaryTree;
代码：
//线索二叉树的数据结构 typedef enum{link,thread}PointTag; typedef struct BiThrNode{ char data; struct BiThrNode *lchild; struct BiThrNode *rchild; PointTag ltag; PointTag rtag; }BiThrNode,*BiThrTree; //线索二叉树的创建 BiThrNode* CreateBiThrTree() { BiThrNode* T; char c; scanf("%c",&c); if(' ' == c) T = NULL; else { T = (BiThrNode *)malloc(sizeof(BiThrNode)); T->data; T->data = c; T->ltag = link; T->rtag = link; T->lchild = CreateBiThrTree(); T->rchild = CreateBiThrTree(); } return T; } //全局变量，始终指向刚刚访问过的节点 BiThrTree pre; //中序遍历线索化 InThreading(BiThrTree T) { if(T) { InThreading(T->lchild); //递归左孩子线索化 //节点处理，中序和之前遍历树的操作不同，但是结构相同 if( !T->lchild) //如果该节点没有左孩子 { T->ltag = thread; //设置为线索 T->lchild = pre; //指向前驱节点，也就是上一个访问的节点 } if( !pre->rchild ) //右子树为空的情况才可以设置线索 { pre->rtag = thread; //设置为线索 pre->rchild = T; //指向后继节点，也就是当前访问的节点 } pre = T; //处理完当前节点之后，T就成为前一个节点，然后接着往下 InThreading(T->rchild); //递归右孩子线索化 } } //增加头结点并对pre进程初始化 InOrderThreading(BiThrTree head,BiThrTree T) { head = (BiThrTree)malloc(sizeof(BiThrTree)); head->ltag = link; head->rtag = thread; head->rchild = head; //指向本身 if( !T ) //如果为空树 head->lchild = head; else //如果不是空树 { head->lchild = T; pre = head; //对pre进行初始化 InThreading(T); //中序遍历线索化 //收尾处理 pre->rchild = head; pre->rtag = thread; head->rchild = pre; } } //中序遍历二叉树，非递规 void InOrderTraverse(BiThrTree T) { BiThrTree p; p = T->lchild; while( p != T ) { while( p->ltag == link ) p = p->lchild; printf("%c",p->data); while(p->rtag == thread && p->rchild != T) { P = P->rchild; printf("%c",p->data); } p = p->rchild; //指回头结点 } }
