中序线索化二叉树[C语言实现及注释]
根据我自己的理解给代码加了注释。
/* 中序线索二叉树 2014/11/14 */ #include<stdio.h> #include<stdlib.h> typedef struct BiTrNoDe{ char data; struct BiTrNoDe *lchild; struct BiTrNoDe *rchild; unsigned ltag : 1; //LINK是1 此处也可以用枚举类型或者宏定义去写 unsigned rtag : 1; //threading是0 }BiTrNode,*BiThre; //----------------------------------------------------------- BiThre pre; //声明这个指向前驱的pre ,给予其全局变量。 //比如 DBAECF这个中序表示法 B的前驱就是D,同理A便是B的后继 //----------------------------------------------------------- void InitBiTree(BiThre *T); //创建一个二叉树 void InorderThread(BiThre *p,BiThre T); //为了弄出一个头指针 void Inthreading(BiThre T); //中序线索后二叉树 void InorderTraverse(BiThre T); //遍历二叉树 int main(void) { BiThre T = NULL,P = NULL;//创建2个结构体的指针,分别是T和P InitBiTree(&T); //取指针的指针是为了操作这个指针。 InorderThread( &P,T); //操作完毕后的指针可以直接拿来用 InorderTraverse(P); return 0; } //用前序递归创建一颗树 void InitBiTree(BiThre *T) { char c; scanf("%c",&c); if(‘ ‘ == c) { *T = NULL; } else{ *T = (BiTrNode*)malloc(sizeof(BiTrNode)); (*T)->data = c; (*T)->ltag = 1; (*T)->rtag = 1; InitBiTree(&(*T)->lchild); InitBiTree(&(*T)->rchild); } } void InorderThread(BiThre *p,BiThre T) { *p = (BiTrNode*)malloc(sizeof(BiTrNode)); if(!*p)exit(-1); //生成失败就退出 (*p)->ltag = 1; //------------------------------------------ (*p)->rtag = 0; //设置它的左tag为LINK,右为thread //------------------------------------------ (*p)->rchild = (*p); if( T ) //这个T是创建的那棵树的根.如果它不是空树 { (*p)->lchild = T; pre = (*p ); //这个pre是指向的p,在下面执行的过程中使最左边的那个结点指向p Inthreading(T); pre->rchild=*p; // ------------------------------------------------------------------- pre->rtag= 0; // 这3步表示结束后把p指向最右边那个结点,然后把最后边的节点指给pre。 (*p)->rchild= pre; //--------------------------------------------------------------------- } else{ (*p)->rchild = (*p); } } //递归遍历并线索化。 void Inthreading(BiThre T) { if( T ) //如果不为空的就执行,当他空的的时候递归也就结束开始返回了。 { Inthreading(T->lchild); //搜索到左边的最后一个节点 if(!T->lchild){ //指向前驱 T->ltag = 0; T->lchild = pre; } if(!pre->rchild){ //指向后继 pre->rtag = 0; pre->rchild = T; } pre = T; Inthreading(T->rchild); //和上面的同理 } } void InorderTraverse(BiThre T) //这里形参写的不好应该写P ,这个函数里出现的T全是P的意思。。 { BiThre p; p = T->lchild; while(p != T) { while(p->ltag == 1) { p = p->lchild; } printf("%c",p->data); while(p->rtag == 0 && p->rchild!=T)//搜索他的后继,直到没有后继 { p = p->rchild; printf("%c",p->data); } p = p->rchild; //指到"根"的右子树 } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。