线索化二叉树的实现

目 录 11 课题描述 22 任务分析 33 逻辑设计及描述 33.1二叉树的存储 43.2 二叉树的遍历 43.3 二叉树的线索化 73.4 线索化二叉树的遍历 103.5 主函数 124 程序编码 21总结 22参考文献 1 课题描述 本程序重在设计二叉树的各种线索化实现，以C语言作为编程语言，实现对二叉树的先、中、后三种序列的线索化。旨在使用户在使用过程中能直接调用各种所需函数，以及了解二叉树的各种线索化过程。其中各函数分别为： BiThrTree CreateBiTree()；//创建二叉树; BiThrTree CopyBiTree(BiThrTree &rt)//复制一棵二叉树; void PreOrderTraverse(BiThrTree T)//先序遍历二叉树; void InOrderTraverse(BiThrTree T) //中序遍历二叉树; void PostOrderTraverse(BiThrTree T)//后序遍历二叉树; bool PreOrderThreading(BiThrTree &Thrt, BiThrTree T)//先序线索化二叉树; void PreThreading(BiThrTree p)//先序搜索结点的建立; bool InOrderThreading(BiThrTree &Thrt, BiThrTree T)//中序线索化二叉树; void InThreading(BiThrTree p)//中序搜索结点的建立; void backThreading(BiThrTree p)//后序搜索结点的建立; BiThrTree backorderThreading(BiThrTree &rt)//后序线索化二叉树; BiThrTree parent(BiThrTree &thrt,BiThrTree &p)//查找结点 void PreOrderTraverse_Thr(BiThrTree Thrt)//遍历先序线索化二叉树; void InOrderTraverse_Thr(BiThrTree Thrt)//遍历中序线索化二叉树; void backorderTraver(BiThrTree Thrt)//遍历后序线索化二叉树; void InOrder_Thr_T(BiThrTree Thrt,BiThrTree &T)//将线索化后的二叉树还原; 开发工具：C语言 运行环境：Visual c++6.0。 2 任务分析 这是一个能对二叉树线索化的程序，其中包括对二叉树的先序、中序、后序线索化，最后遍历线索化并输出遍历结果。其中线索化要实现对同一个树的线索化，即应具备还原线索化后二叉树的程序，并重新对二叉树线索化。主要的功能模块 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 图如图2.1所示。 图 2.1 模块流程图 3 逻辑设计及描述 3.1二叉树的存储 1.创建二叉树（ CreateBiTree(T)）设计思想：在用户需要创建二叉树时，屏幕提醒输入树的各个结点，包括空结点的输入，完成输入后，程序自动依次读入各个结点，以空结点作为判断结点位置的主要依据，对每个结点申请一定的存放空间，然后依次存放各结点。设计流程如图3.1所示。 图 3.1 CreateBiTree(T ) 创建二叉树 图 3.2 CopyBiTree(rt) 复制一棵二叉树 2.复制二叉树（CopyBiTree(rt)）设计思想：该函数的功能主要是为了避免前后两次的线索化混乱，其实质是重建二叉树以方便下一次的线索化。复制的方法无外乎将各个结点拷贝至另一棵树，因为是完全一样的二叉树,所以连左右标志域也要一起复制,结点位置不能发生任何变化。设计流程如图3.2所示，算法如算法3.1所示。 BiThrTree CopyBiTree(BiThrTree &rt){ BiThrTree tree;if(rt==NULL) tree=NULL; else{ if(!(tree=(BiThrTree)malloc(sizeof(BiThrNode)))) return 0; tree->data=rt->data;//复制结点 tree->LTag=rt->LTag;tree->RTag=rt->RTag;//复制左右标志域 tree->lchild=CopyBiTree(rt->lchild); tree->rchild=CopyBiTree(rt->rchild);//复制左右孩子} return tree;} 算法3.1 3.2 二叉树的遍历 1. 先、中、后遍历二叉树，因为三种遍历方法的区别只是将输出结点的位置调换一下就可以实现，所以在此只列举先序遍历方法的设计思想，该函数是用递归的方法依次遍历根结点、左子、右子，中序遍历则是左子、根结点、右子，后序遍历只需将根结点的访问放在最后面执行即可。设计流程如图3.3，主要算法如算法3.2所示。 void PreOrderTraverse(BiThrTree T){//前序遍历 if (T!=NULL){printf("%c ",T->data); /*访问根结点*/ PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild); }} 算法3.2 图 3.3 PreOrderTraverse(T) 先序遍历二叉树 图3.4 PreOrderThreading(Thrt,T) 先序线索化二叉树 3.3 二叉树的线索化 1. 先序线索化二叉树（PreOrderThreading(Thrt,T)）设计思想：由于线索化的实质是将二叉链 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 中的空指针改为指向遍历时得到的前驱或后继的线索，因此线索化的过程即为在遍历过程中修改空指针的过程，附设一个指针pre始终指向刚刚访问过的结点，若指针p指向当前结点，则pre指向他的前驱。由此可得先序遍历建立先序线索化的算法如算法3.3和3.4所示。 图 3.5 PreThreading(p) 先序搜索结点的建立 图3.6 InThreading(p) 中序搜索结点的建立 2．中序搜索结点的建立以及线索化如图3．6和3．7所示;后序搜索结点的建立和线索化如图3．8和3．9所示。流程图不再多作说明。 图 3.7 InOrderThreading(Thrt,T) 中序线索化二叉树 图3.8 backThreading(p) 后序搜索结点的建立 bool PreOrderThreading(BiThrTree &Thrt,BiThrTree T) {//前序线索化二叉树 void PreThreading(BiThrTree p);//先序遍历进行先序线索化 Thrt = (BiThrTree)malloc(sizeof(BiThrNode)); Thrt->LTag=0; Thrt->RTag=1; //创建头结点 Thrt->rchild=Thrt;//右指针回指 if (!T) Thrt->lchild=Thrt; //空二叉树 else { Thrt->lchild = T;pre = Thrt; //pre: 刚刚访问过的结点 PreThreading(T);pre->rchild=Thrt; pre->RTag=1;//最后一个结点线索化 Thrt->rchild=pre; } return 1;} 算法3.3 void PreThreading(BiThrTree p){ if (p) { if(!p->lchild){ p->lchild=pre; p->LTag=1;} //前驱线索 if(!pre->rchild){ pre->rchild=p;pre->RTag=1;}//后继线索 pre = p;//保持pre指向p的前驱 if(p->LTag==0)PreThreading(p->lchild); //左子树线索化 　if(p->RTag ==0)PreThreading(p->rchild); //右子树线索化} } //前序建立节点线索化 算法3.4 图3.9 backOrderThreading (Thrt,T) 后序线索化二叉树 图3.10 BiThrTree parent(thrt,p) 查找结点 3.4 线索化二叉树的遍历 在程序设计中,实现线索化二叉树的遍历,实质上就是在查找每个结点的前驱和后继,而结点是否有前驱和后继、他们分别是什么,就要分情况去讨论。 1.中序遍历线索化二叉树(InOrderTraverse_Thr(Thrt))时,结点的前驱应是遍历左子树时访问的第一个结点,既左子树最左下方的结点,结点的后继应是遍历右子树时访问的第 图 3.11 PreOrderTraverse_Thr(Thrt) 遍历先序线索化二叉树 图 3.12 InOrderTraverse_Thr(Thrt) 遍历中序线索化二叉树 一个结点,既右子树最左下方的结点。二叉树最左下方的结点没有前驱，最右下方的结点没有后继。设计该函数的流程如图3.12所示。 2.在后序线索树(PostOrderTraverse_Thr(Thrt))中找结点后继比较复杂，分三种情况（1）根结点没有后继；（2）若结点是其双亲的右孩子或是其双亲的左孩子且其双亲没有右子树，则后继为双亲；（3）若结点是其双亲的左孩子且其双亲有右子树，则后继为其 双亲的右子树上按后序遍历访问的第一个结点。设计该函数的流程如图3．13所示。 3.还原线索化二叉树(InOrder_Thr_T(Thrt,T)):涉及该函数的主要目的是在每次线索后 图 3.13 backOrderTraverse_Thr(Thrt) 遍历后序线索化二叉树 都能清除掉前一次线索化过程中所留下的指针,因为不通顺序的线索化,其修改的空指针也不同,因此,进行下一次线索化前,必须还原空指针。此函数的流程如图3.14所示。 图 3.14 InOrder_Thr_T (Thrt,T) 还原线索化后的二叉树 图3.15 menu_select() 控制选择菜单 3.5 主函数 1.主函数的设计流程如图3.17所示,在进行所需操作之前,屏幕会提示用户建立一棵二叉树,然后用空的for循环来控制不同操作之间的循环,用户选择序号1,程序会自动执行二叉树的三种遍历,并输出遍历结果;用户选择2,程序会自动执行二叉树的线索化操作,并打印出三种线索化后的结果。操作十分方便。 图3.17 main()主函数 4 程序编码 //----------------------------------有关定义---------------------------------- #include #include #include #include typedef struct BiThrNode{ //线索二叉树中结点的定义 char data; int LTag,RTag; struct BiThrNode *lchild,*rchild; }BiThrNode,*BiThrTree; //----------------------------------构建二叉树-------------------------------- BiThrTree CreateBiTree(){ char ch; BiThrTree T; scanf("%c",&ch); //从键盘输入ch； if(ch=='#') T=NULL; //如果ch='#',则T为空指针 else{ if(!(T=(BiThrTree)malloc(sizeof(BiThrNode)))) return 0; T->data=ch; T->LTag=0; T->RTag=0; //线索标志赋初值0 T->lchild=CreateBiTree();//先序建立T->lchild; T->rchild=CreateBiTree();//先序建立T->rchild; } return T; //返回树结点头指针 } BiThrTree CopyBiTree(BiThrTree &rt)//复制一棵二叉树{ BiThrTree tree; if(rt==NULL) tree=NULL; else{ if(!(tree=(BiThrTree)malloc(sizeof(BiThrNode)))) return 0; tree->data=rt->data; tree->LTag=rt->LTag; tree->RTag=rt->RTag; tree->lchild=CopyBiTree(rt->lchild); tree->rchild=CopyBiTree(rt->rchild); } return tree; } //-----------------------------递归遍历二叉树------------------------------- void PreOrderTraverse(BiThrTree T){//先序遍历 if (T!=NULL){ printf("%c ",T->data); /*访问根结点*/ PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild);}} void InOrderTraverse(BiThrTree T) {//中序遍历 if (T!=NULL){ InOrderTraverse(T->lchild); printf("%c ",T->data); /*访问根结点*/ InOrderTraverse(T->rchild);}} void PostOrderTraverse(BiThrTree T) {//后序遍历 if (T!=NULL) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c ",T->data); /*访问根结点*/} } //----------------------------线索化二叉树--------------------------------- BiThrTree pre; //全局变量,刚刚访问过的结点 bool PreOrderThreading(BiThrTree &Thrt,BiThrTree T){//先序线索二叉树 void PreThreading(BiThrTree p) ; Thrt = (BiThrTree)malloc(sizeof(BiThrNode)); //创建头结点 Thrt->LTag=0; Thrt->RTag=1; Thrt->rchild=Thrt; if (!T) Thrt->lchild=Thrt; //空二叉树 else { Thrt->lchild = T; pre = Thrt; //pre: 刚刚访问过的结点； PreThreading(T); pre->rchild=Thrt; pre->RTag=1; Thrt->rchild=pre; } return 1;} void PreThreading(BiThrTree p) { if (p) { if (!p->lchild) { p->lchild=pre;p->LTag=1; } //前驱线索 if (!pre->rchild){ pre->rchild=p;pre->RTag=1;} //后继线索 pre = p; if(p->LTag==0) PreThreading(p->lchild); //左子树线索化 if(p->RTag ==0) PreThreading(p->rchild); }//右子树线索化 } //先序建立节点的搜索化 bool InOrderThreading(BiThrTree &Thrt, BiThrTree T){//中序线索二叉树 void InThreading(BiThrTree p) ; Thrt = (BiThrTree)malloc(sizeof(BiThrNode)); //创建头结点 Thrt->LTag=0; Thrt->RTag=1; Thrt->rchild=Thrt; if (!T) Thrt->lchild=Thrt; //空二叉树 else { Thrt->lchild = T; pre = Thrt; //pre: 刚刚访问过的结点； InThreading(T); pre->rchild=Thrt; pre->RTag=1; Thrt->rchild=pre; } return 1;} void InThreading(BiThrTree p) { if (p) { InThreading(p->lchild); //左子树线索化 if (!p->lchild){//前驱线索 p->lchild=pre; p->LTag=1; } if (!pre->rchild){//后继线索 pre->rchild=p;pre->RTag=1; } pre = p; InThreading(p->rchild); }}//右子树线索化 void backThreading(BiThrTree p){ if(p){ backThreading(p->lchild); backThreading(p->rchild); if(!p->lchild){ p->LTag=1;p->lchild=pre; }//前驱线索 if(!pre->rchild){ pre->RTag=1;pre->rchild=p;//后继线索} pre=p; }}//后序搜索化节点的建立 BiThrTree backorderThreading(BiThrTree &rt){ BiThrTree thrt; if(!(thrt = (BiThrTree) malloc (sizeof(BiThrNode)))) exit(1); thrt->LTag= 0;thrt->RTag=1;//建头结点 thrt->rchild=thrt;//右指针回指 if(!rt) thrt->lchild=thrt; //若二叉树空，则左指针回指 else{ thrt->lchild=rt; pre=thrt; backThreading(rt); //后序遍历进行后序线索化 thrt->rchild=pre; } //最后一个节点处理 return thrt;} BiThrTree parent(BiThrTree &thrt,BiThrTree &p){ BiThrTree temp; temp=thrt; if(temp->lchild==p) return temp;//父节点是头结点 else{ temp=temp->lchild; while( temp->lchild!=p && temp->rchild!=p ){ if(0==temp->RTag) temp=temp->rchild;//结点有右结点，往右 else temp=temp->lchild; } //如果结点没有右孩子，去左孩子，没有左孩子，去前驱 return temp;} } //---------------------------遍历线索化二叉树------------------------------- void PreOrderTraverse_Thr(BiThrTree Thrt)//Thrt:头结点{//遍历先序线索化二叉树 BiThrTree p; p=Thrt->lchild; while(p!=Thrt){ printf("%c→",p->data);//此树不空 while(p->LTag == 0){ p=p->lchild; printf("%c→",p->data); } while((p->RTag==1)&&(p->rchild!=Thrt)){ p = p->rchild; printf("%c→",p->data);} if(p->LTag==0) p=p->lchild; else p=p->rchild;} }// void InOrderTraverse_Thr(BiThrTree Thrt)//Thrt:头结点 {//遍历中序线索化二叉树 BiThrTree p; p=Thrt->lchild; while(p!=Thrt){ while(p->LTag == 0) p=p->lchild; printf("%c→",p->data); while((p->RTag==1)&&(p->rchild!=Thrt)){ p = p->rchild; printf("%c\n%c→",p->data,p->data); } p = p->rchild; }}// void backorderTraver(BiThrTree Thrt) { BiThrTree p; BiThrTree par; p=Thrt->lchild; while(1) { while(0==p->LTag) p=p->lchild; if(0==p->RTag) p=p->rchild; //p指向第一个被访问的结点 else break; } while(p!=Thrt) { printf("%c→",p->data); par=parent(Thrt,p);//parent是p的双亲: if(Thrt==par) p=Thrt;//若parent是thrt，即p是根结点，则无后继 else if(p==par->rchild||1==par->RTag) p=par; //若p是双亲的右孩子，或者是独生左孩子，则后继为双亲 else{ while(par->RTag==0) { //若p是有兄弟的左孩子，则后继为双亲的右子树上后序遍历访问的第一个节点。 par=par->rchild; while(par->LTag==0) { par=par->lchild; }} p=par; } printf("%c\n",p->data); }} //---------------------------将线索化后二叉树还原---------------------------- void InOrder_Thr_T(BiThrTree Thrt,BiThrTree &T){ BiThrTree p,post; p=Thrt->lchild; while(p!=Thrt){ while(p->LTag == 0) p=p->lchild; p->LTag=0; p->lchild=NULL; while((p->RTag==1)&&(p->rchild!=Thrt)){ p->RTag=0; post=p->rchild; p->rchild=NULL; p=post; } p = p->rchild; } p=Thrt->rchild; p->RTag=0; p->rchild=NULL; T=Thrt->lchild; free(Thrt);} //--------------------------------选择菜单----------------------------------- int menu_select(){ int c; do{ printf("\n请选择需要执行的操作序列号:"); scanf("%d",&c); }while(c<1||c>3); return c; } //-----------------------------------主函数----------------------------------- void main(){ int choice; BiThrTree T,Thrt,t; //定义树 printf("请输入树的结点(#表示结点为空):\n"); T=CreateBiTree(); //先序算法建立二叉树 t=CopyBiTree(T); printf("\n"); //复制一颗二叉树 printf(" ┏━━━━━ 操作菜单 ━━━━┓\n"); printf(" ┣━━━━━━━━━━━━━━┫\n"); printf(" ┃ 1.遍历操作二叉树 ┃\n"); printf(" ┣━━━━━━━━━━━━━━┫\n"); printf(" ┃ 2.线索化二叉树 ┃\n"); printf(" ┣━━━━━━━━━━━━━━┫\n"); printf(" ┃ 3.退出所有操作 ┃\n"); printf(" ┗━━━━━━━━━━━━━━┛\n"); for(;;){ choice=menu_select(); switch(choice){ case 1:{ printf("\n ━━━━━*遍历二叉树*━━━━━\n"); printf("\n <先序> 遍历二叉树结果:\n"); PreOrderTraverse(T); printf("\n"); printf("\n <中序> 遍历二叉树结果:\n"); InOrderTraverse(T); printf("\n"); printf("\n <后序> 遍历二叉树结果:\n"); PostOrderTraverse(T); printf("\n\n");} break; case 2:{ printf("\n ━━━━━*线索二叉树*━━━━\n"); InOrderThreading(Thrt,T);//中序线索化 printf("\n <中序> 线索化后的内容:\n"); InOrderTraverse_Thr(Thrt); //遍历中序线索化二叉树 printf("\n"); InOrder_Thr_T(Thrt,T);//还原 PreOrderThreading(Thrt,T);//前序线索化 printf("\n <先序> 线索化后的内容:\n"); PreOrderTraverse_Thr(Thrt);//遍历先序线索化二叉树 printf("\n"); printf("\n <后序> 线索化后的内容:\n");//后线索化 BiThrTree thrt; thrt=backorderThreading(t); //建立后序线索二叉树 backorderTraver(thrt); } //遍历后序线索化二叉树 break; case 3: printf("\n 已结束!谢谢使用!\n"); exit(0); } } } 5 程序调试与测试 1.在程序调试正确后执行程序，会出现运行框显示“请输入树的结点(#表示结点为空)”的提示语，当准确输入二叉树后(空节点包括在内)，选择菜单分别执行用户所需要的操作, 输入abc##d##ef##g##表示一棵如图5.1所示的二叉树 图 5．1　二叉树结构图 图 5．2　中序线索二叉树 2.程序实际运行结果如图5.3所示: 图5.3 创建二叉树 3 .图5.4为整个程序的操作界面: 图5.4 操作菜单界面 4.遍历二叉树理论的输出结果应为： 先序遍历：a b c d e f g； 中序遍历：c b d a f e g； 后序遍历：c d b f g e a； 程序实际执行的结果如图5.5所示，显而易见，实际与结果相符。 图5.5 遍历二叉树 5.遍历线索化二叉树的理论输出结果为： 先序线索化后内容为： a→b→c→d→e→f→g； 中序线索化后内容为： c→b b→d→a a→f→e e→g→； 后序线索化后内容为： c→d d→b b→f f→g g→e 二叉树的中序线索化链表示意图如图5.6所示,其中,LTag=0时,lchild域指向结点的左孩子,Ltag=1时,lchild域指向结点的前驱；RTag=0时,rchild域指向结点的左孩子,RTag=1时,rchild域指向结点的后继。 实际输出结果如图5.7所示，与理论没有出入。 图5.6 中序线索化链表 图5.7 线索二叉树的遍历 6.结束操作，如图5.8所示。 图5.8 结束界面 总结 参考文献 [1] 严蔚敏，吴伟民.数据结构(C语言版)[M].北京：清华大学出版社,2007 [2] 罗建军,朱丹君,顾刚,刘路放.C++程序设计教程(第二版).北京：清华大学出版社,2007 [3] 何钦铭,严晖.C语言程序设计.北京: 高等教育出版,2008 [4] 谭浩强.C程序设计(第三版).北京:清华大学出版社,2005