线索二叉树的建立和遍历

为充分利用二叉树节点，引入线索二叉树，将左孩子指针为空时指向前驱，将右孩子指针为空时指向后继。

输入：ABC``D``E`F``(`用空格替代)

中序遍历结果：CBDAEF

代码实现中的部分挺巧妙的，偶尔可以翻出来看看，琢磨琢磨。

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 // 线索存储标志位
  5 // Link(0) 左右孩子
  6 // Thread(1) 前驱后继
  7 typedef enum{Link,Thread}   TAG;
  8 
  9 // 线索二叉树节点结构
 10 typedef struct BiThrNode
 11 {
 12     char data;                  // 节点存储的数据
 13     TAG ltag,rtag;              // 左右孩子 or 前驱后继 标志
 14     struct BiThrNode *lchild;   // 左孩子
 15     struct BiThrNode *rchild;   // 右孩子
 16 }BiThrNode,*BiThrTree;
 17 
 18 // 前序建立线索二叉树
 19 void CreateBiThrTree(BiThrTree &t)
 20 {
 21     t = (BiThrTree)malloc(sizeof(BiThrNode));
 22     if(t == NULL){
 23         return ;
 24     }
 25     char c;
 26     scanf("%c",&c);
 27     if(c == ' '){               // 空格表示叶子
 28         t = NULL;
 29     }
 30     else{
 31         t->data = c;
 32         t->ltag = Link;
 33         t->rtag = Link;
 34         
 35         CreateBiThrTree(t->lchild);
 36         CreateBiThrTree(t->rchild);
 37     }
 38     return ;
 39 }
 40 
 41 // 全局，始终指向刚访问过的节点
 42 BiThrTree pre;
 43 
 44 // 中序遍历线索化
 45 void MidSequenceThr(BiThrTree t)
 46 {
 47     if(t == NULL){
 48         return;
 49     }
 50     MidSequenceThr(t->lchild);  // 递归左孩子线索化
 51     
 52     if (t->lchild == NULL){
 53         t->ltag = Thread;
 54         t->lchild = pre;
 55     }
 56     if (pre->rchild == NULL){
 57         pre->rtag = Thread;
 58         pre->rchild = t;
 59     }
 60     pre = t;
 61     MidSequenceThr(t->rchild);  // 递归右孩子线索化
 62 }
 63 
 64 void InOrderThr(BiThrTree &p,BiThrTree t)
 65 {
 66     p = (BiThrTree)malloc(sizeof(BiThrNode));
 67     p->ltag = Link;
 68     p->rtag = Thread;
 69     if (t == NULL){
 70         p->lchild = p;
 71     }
 72     else{
 73         p->lchild = t;
 74         pre = p;
 75         MidSequenceThr(t);
 76         pre->rchild = p;
 77         pre->rtag = Thread;
 78         p->rchild = pre;
 79     }
 80 }
 81 
 82 // 非递归中序遍历二叉树
 83 void MidTraverse(BiThrTree pr)    // 传参为p
 84 {
 85     BiThrTree q;
 86     q = pr->lchild;
 87 
 88     while (q != pr){
 89         while (q->ltag == Link){
 90             q = q->lchild;
 91         }    
 92         printf("%c",q->data);
 93         while (q->rtag == Thread && q->rchild != pr){
 94             q = q->rchild;
 95             printf("%c",q->data);
 96         }
 97         q = q->rchild;
 98     }
 99 }
100 
101 int main()
102 {
103     BiThrTree p,t;    // p是头指针 t是根节点指针
104     
105     // 前序建树
106     CreateBiThrTree(t);
107     
108     // 线索化
109     InOrderThr(p,t);
110     
111     // 根据线索 中序遍历输出
112     printf("MidSequence:");
113     MidTraverse(p);
114     printf("
");
115 
116     return 0;
117 }