首页 > 代码库 > 线索树的建立与遍历
线索树的建立与遍历
在建立二叉树的时候发现,那些叶节点的左孩子和右孩子的指针域都是空的,浪费空间,这时候就可以将这些空间利用起来,让遍历更加方便,这就是线索树存在的原因,线索树实现完了之后其实会发现就是一个双向链表,那种遍历就容易的多了。
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); //创建二叉树 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\n"); 29 pre_order_traverse(T,level); //前序遍历输出二叉树 30 printf("\nin-order-traverse\n"); 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=http://www.mamicode.com/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 else113 {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("%c ",T->data);153 }
线索树的建立与遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。