.5 有关数据结构线索二叉树

第五章树
的代码（原文：http://blog.csdn.net/jiajiayouba/article/details/9224403）
  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef char ElemType; //数据类型
  5 typedef enum {Link,Thread} childTag; //Link表示结点，Thread表示线索
  6 typedef struct bitNode
  7 {
  8   ElemType data;
  9   struct bitNode *lchild,*rchild;
 10   int ltag,rtag;
 11 } bitNode ,*bitTree;
 12 
 13 void create_tree(bitTree *T,char **arr); //创建二叉树，这里的arr必须是指向指针的指针，因为用它可以改变arr的值 而只是用指针的话不能改变
 14 void pre_order_traverse(bitTree T,int level); //前序遍历二叉树
 15 void in_order_threading(bitTree T); //中序遍历线索化
 16 void in_thread(bitTree *P,bitTree T); //新加入一个头结点，让二叉树成一个封闭环
 17 void in_order_traverse(bitTree T); //中序遍历二叉树(带有头结点)
 18 void visit(bitTree T); //访问结点信息
 19 
 20 bitTree pre; //表示上次刚刚访问的结点
 21 
 22 int main()
 23 {
 24   bitTree P,T;
 25   int level =1; //表示该结点的深度
 26   char *arr="ab d  ce   "; //构造二叉树所需结点(按前序遍历方式输入)
 27   create_tree(&T,&arr); //构造二叉树
 28   printf("pre-order-traverse
");
 29   pre_order_traverse(T,level); //前序遍历输出二叉树
 30   printf("in-order-traverse
");
 31   in_thread(&P,T); //二叉树线索化
 32   in_order_traverse(P); //输出线索化后的二叉树
 33   return 0;
 34 }
 35 
 36 /*
 37 创建二叉树，其输入必须按照前序遍历的次序。
 38 T：二叉树根节点
 39 arr：按照前序遍历次序排列的各节点的值。无孩子结点时用空格代替
 40 */
 41 void create_tree(bitTree *T,char **arr)
 42 {
 43   char c;
 44   sscanf(*arr,"%c",&c); //读入一个结点值
 45   (*arr)++;
 46   if(' '==c) //如果是空格，表示空结点
 47     {
 48       *T=NULL;
 49     }
 50   else 
 51     {
 52       *T=(bitTree)malloc(sizeof(bitNode)); //构造新结点
 53       (*T)->data=c;
 54       (*T)->ltag=Link;
 55       (*T)->rtag=Link;
 56       create_tree(&(*T)->lchild,arr);//构造新结点的左孩子
 57       create_tree(&(*T)->rchild,arr);//构造新结点的右孩子
 58     }
 59 }
 60 
 61 /*
 62 前序遍历访问二叉树
 63 */
 64 void pre_order_traverse(bitTree T,int level)
 65 {
 66   if(T)
 67     {
 68       visit(T);
 69       pre_order_traverse(T->lchild,level+1);
 70       pre_order_traverse(T->rchild,level+1);
 71     }
 72 }
 73 
 74 /*
 75 中序遍历二叉树，对其进行线索化
 76 */
 77 void in_order_threading(bitTree T)
 78 {
 79   if(T)
 80     {
 81       in_order_threading(T->lchild); //左孩子线索化
 82       if(!T->lchild) //如果左孩子为空，则将其指向直接前驱
 83     {
 84       T->lchild=pre;
 85       T->ltag=Thread;
 86     }
 87       if(!pre->rchild) //如果上一个结点的右孩子为空，则将其指向直接后继。（注意：只有访问到下一个结点时，才会知道本结点的后继是谁）
 88     {
 89       pre->rchild=T;
 90       pre->rtag=Thread;
 91     }
 92       pre=T;
 93       in_order_threading(T->rchild); //右孩子线索化
 94     }
 95 }
 96 
 97 /*
 98 加入一个头结点，使二叉线索树成一个封闭环
 99 P：带有头结点的二叉树。头结点的左孩子指向二叉树T；右孩子指向T树中的最后一个叶子结点
100 T：不带有头结点的二叉树。
101 */
102 void in_thread(bitTree *P,bitTree T)
103 {
104   (*P)=(bitTree)malloc(sizeof(bitNode)); //构造新加入的头结点
105   (*P)->ltag=Link;
106   (*P)->rtag=Thread;
107   (*P)->rchild=*P;
108   if(!T) //如果二叉树为空，则P的孩子指向自己。
109     {
110       (*P)->lchild=*P;
111     }
112   else
113     {
114       (*P)->lchild=T;
115       pre=*P;
116       in_order_threading(T); //对二叉树进行线索化
117       (*P)->rchild=pre; //将头结点右孩子指向最后一个叶子结点
118       pre->rtag=Thread; //将最后一个叶子结点的右孩子指向头结点。这样，环就形成了。
119       pre->rchild=*P;
120     }
121 }
122 
123 /*
124 非递归方式：中序遍历二叉树(树必须带有头结点，且已经线索化)
125 P:带有头结点的二叉树
126 */
127 void in_order_traverse(bitTree P)
128 {
129   bitTree T;
130   T=P->lchild;
131   while(T!=P) //判断是否空树
132     {
133       while(T->ltag==Link) //从左孩子开始，直到叶子结点
134         {
135           T=T->lchild;
136         }
137       visit(T);
138       while(T->rtag==Thread && T->rchild!=P) //根据线索，访问后继结点。并且后继结点不是指向头结点的
139         {
140           T=T->rchild;
141           visit(T);
142         }
143       T=T->rchild;
144     }
145 }
146 
147 /*
148 访问结点信息
149 */
150 void visit(bitTree T)
151 {
152     printf("%d-%c-%d
",T->ltag,T->data,T->rtag);
153 }
.5 有关数据结构 线索二叉树

.5 有关数据结构线索二叉树
