数据结构实验6：二叉树的线索化.docx

《数据结构实验6：二叉树的线索化.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验6：二叉树的线索化一、实验目的1．掌握线索二叉树的存储结构。2．掌握将一棵二叉树线索化算法。3．掌握线索二叉树的遍历算法，理解算法在效率上的改进。4.将算法用C语言编写完整程序并上机运行，记录实验过程与数据。二、实验仪器：1.硬件：Lenovo通用PC机，2.软件：WINDOWS7，WORD，GCC编译器三、实验原理：1.线索化算法四、实验步骤：1.设计一个实验样本，取二叉树为：2.定义一个线索二叉树的结点；此处填写具体代码3.按先序的方式建立一棵普通的二叉树；此处填写具体代码4.将普通二叉树

2、线索化此处填写具体代码5.按线性方式遍历线索二叉树此处填写具体代码五、数据处理及结论1.输入：A↙B↙D↙#↙#↙E↙#↙#↙C↙F↙#↙#↙G↙#↙#注:每个↙符号代表输入确定，即回车2.输出：CBEAFCGCBEAFCG七、思考题：1.为什么要将一棵二叉树线索化？2.为什么在线索化的过程中preNode要使用全局变量？附：#include#include#include#defineNULLFLAG'#'typedefcharelemT

3、ype;typedefenum{FALSE,TRUE}status;typedefenum{link,thread}pointerTag;typedefstructNODE{elemTypedata;structNODE*lchild,*rchild;intlTag,rTag;}biThreadTreeNode;//定义一个全局变量指针preNode,在线索化时记录每个结点的直接前驱结点biThreadTreeNode*preNode;statusbiThreadTreeNodeInit(biTh

4、readTreeNode*t,elemTypee){if(t){t->data=e;t->lchild=NULL;t->rchild=NULL;t->lTag=link;t->rTag=link;returnTRUE;}elsereturnFALSE;}//按先序遍历的方法建立一棵二叉树，空位用空格号代替statusbiThreadTreeCreate(biThreadTreeNode**t){elemTypech;//fflush(stdin);//如果使用清空缓存的这句，则每输入一个字符要回车

5、一次ch=getchar();if(ch==NULLFLAG){*t=NULL;returnFALSE;}else{*t=(biThreadTreeNode*)malloc(sizeof(biThreadTreeNode));if(*t){biThreadTreeNodeInit(*t,ch);biThreadTreeCreate(&((*t)->lchild));biThreadTreeCreate(&((*t)->rchild));}}returnTRUE;}//按中序遍历的方式输出一棵二叉树

6、voidbiThreadTreePrint(biThreadTreeNode*t){if(t){biThreadTreePrint(t->lchild);printf("%4c",t->data);biThreadTreePrint(t->rchild);}}//按中序遍历的方式将二叉树线索化statusbiTreeThreading(biThreadTreeNode*t){if(!t)returnFALSE;else{biTreeThreading(t->lchild);if(t->lchild

7、==NULL){t->lchild=preNode;t->lTag=thread;}if(preNode->rchild==NULL){preNode->rchild=t;preNode->rTag=thread;}preNode=t;biTreeThreading(t->rchild);}returnTRUE;}//完整的线索化过程statusinOrderThreading(biThreadTreeNode*head,biThreadTreeNode*t){head->rchild=head;

8、head->rTag=thread;if(t==NULL){head->lchild=head;head->lTag=thread;returnFALSE;}else{head->lTag=link;head->lchild=t;preNode=head;biTreeThreading(t);head->rchild=preNode;preNode->rchild=head;preNode->rTag=thread;}returnTRUE;}statusthreadTraversa