线索二叉树

线索二叉树就是让一些浪费的空间利用起来，并且获得效率。

总体思路就是：中序遍历线索化，这样可以让空间利用率最大，建立一个指针p始终指向头结点，还有一个指针pre(全局变量)指向当前结点的上一个结点，因为要线索化，所以我们得让整棵树串联起来，例如图中的这棵树，中序遍历就是CBDAEF,加红的部分就是该结点有空间可以利用的，因为加红的结点都是左右两边指针都是NULL，或者一边是NULL，所以我们可以让左右两边分别设置两个指针，ltag，rtag(这两个指针都是枚举类型)表示左右两边是指向孩子，还是线索，有孩子就设为Link即为0，没有孩子就设为Thread即为1，同时根据中序遍历来使得结点线索化，就是让c的左指针指向头指针，右指针指向B，D的左指针指向B，右指针指向A，以此类推，实现线索化，最后不要忘了收尾工作，即图的最右边那两条线，在代码中有注释，最后当我们遍历打印的时候就可以根据，ltag，rtag的值进行判断，然后用迭代的方式打印即可。

代码+注释：

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 
  4 typedef char ElemType;
  5 
  6 //线索存储标志位
  7 //Link(0)表示指向左右孩子的指针
  8 //Thread(1)表示指向前驱后继的线索
  9 typedef enum{Link,Thread} PointerTag;
 10 
 11 typedef struct BiThrNode
 12 {
 13     char data;
 14     struct BiThrNode* lchild, * rchild;
 15     PointerTag ltag;
 16     PointerTag rtag;
 17 }BiThrNode, * BiThrTree;
 18 
 19 //全局变量，始终指向刚刚访问过的结点
 20 BiThrTree pre;
 21 
 22 //前序遍历创建一颗二叉树
 23 void CreatBiThrTree(BiThrTree *T)
 24 {
 25     char c;
 26 
 27     scanf("%c", &c);
 28     if (' ' == c)
 29     {
 30         *T = NULL;
 31     }
 32     else
 33     {
 34         *T = (BiThrNode *)malloc(sizeof(BiThrNode));
 35         (*T)->data = c;
 36         (*T)->ltag = Link;
 37         (*T)->rtag = Link;
 38 
 39         CreatBiThrTree(&(*T)->lchild);
 40         CreatBiThrTree(&(*T)->rchild);
 41     }
 42 }
 43 
 44 //中序遍历线索化
 45 void InThreading(BiThrTree T) //pre是一个跟踪结点 不断地指向当前结点的前一个结点
 46 {
 47     if (T)
 48     {
 49         InThreading(T->lchild);  //递归左孩子线索化
 50 
 51         if (!T->lchild)  //如果该结点没有左孩子，设置ltag为Thread，并把lchild指向前驱
 52         {
 53             T->ltag = Thread;
 54             T->lchild = pre;
 55         }
 56 
 57         if (!pre->rchild)  //前驱结点没有有孩子，就把rtag = Thread，有孩子指向当前结点
 58         {
 59             pre->rtag = Thread;
 60             pre->rchild = T;
 61         }
 62 
 63         pre = T;
 64 
 65         InThreading(T->rchild); //递归右孩子线索化
 66     }
 67 }
 68 
 69 void InOrderThreading(BiThrTree *p,BiThrTree T)  //建立一个头指针
 70 {
 71     *p = (BiThrTree)malloc(sizeof(BiThrNode));
 72     (*p)->ltag = Link;
 73     (*p)->rtag = Thread;
 74     (*p)->rchild = *p;
 75     if (!T) //如果是空树
 76     {
 77         (*p)->lchild = *p;
 78     }
 79     else
 80     {
 81         (*p)->lchild = T;  //指向树的头结点
 82         pre = *p;
 83 
 84         InThreading(T);//线索化
 85         pre->rchild = *p; //收尾工作
 86         pre->rtag = Thread;
 87         (*p)->rchild = pre;
 88     }
 89 }
 90 
 91 void visit(char c)
 92 {
 93     printf("%c", c);
 94 }
 95 
 96 //中序遍历二叉树，非递归
 97 void InOrderTraverse(BiThrTree T)  
 98 {
 99     BiThrTree p; //p表示当前结点 T表示头指针
100     p = T->lchild;
101 
102     while (p != T)
103     {
104         while (p->ltag == Link)
105         {
106             p = p->lchild;
107         }
108 
109         visit(p->data);
110 
111         while (p->rtag == Thread && p->rchild != T)
112         {
113             p = p->rchild;
114             visit(p->data);
115         }
116         p = p->rchild;
117     }
118 }
119 
120 int main()
121 {
122     BiThrTree P,T = NULL;  //P是指向头结点的头指针
123 
124     CreatBiThrTree(&T);
125 
126     InOrderThreading(&P,T);
127 
128     printf("中序遍历输出结果为： ");
129     InOrderTraverse(P);
130     return 0;
131 }