二叉树的建立与遍历及二叉树的线索化及线索化遍历.doc

精选文档精选文档精选文档昆明理工大学信息工程与自动化学院学生实验报告（2011—2012学年第1学期）课程名称：数据结构开课实验室：信自楼4422011年11月06日年级、专业、班学号姓名成绩实验项目名称二叉树的建立与遍历及二叉树的线索化及线索化遍历指导教师教师评语教师签名：年月日程序功能：（1）.线索二叉树的主要函数设置如下：1.树的存储的类型为：typedefstructbithrnode{chardata;structbithrnode*lchild,*rchild;intltag,rtag;}bithrnode,*bithrtree;2.主程序：bithrtreeT,p,T1;intk;Do{switch(k){case1:creat(T);--------建立二叉树T1=copy(T);---------复制建立后的二叉树case2:T=copy(T1);---------复制建立后的二叉树PreOrderThreading(p,T);---------先序线索化first(p);--------------先序遍历case3:T=copy(T1);---------复制建立后的二叉树InOrderThreading(p,T);----------中序线索化mid(p);---------------中序遍历case4:T=copy(T1);---------复制建立后的二叉树backorderThreading(p,T);-------------后序线索化last(p);--------------后序遍历}}while(k!=0);3.子程序：bithrtreecreat(bithrtree&T)--------建立二叉树StatusPreOrderThreading(bithrtree&thrt,bithrtreeT)---------先序线索化{voidPreThreading(bithrtreep)}---------先序线索化子函数StatusInOrderThreading(bithrtree&thrt,bithrtreeT)----------中序线索化{voidinthreading(bithrtree&p)}----------中序线索化子函数StatusbackorderThreading(bithrtree&thrt,bithrtreeT)-------------后序线索化{voidbackthreading(bithrtreep)}-------------后序线索化子函数voidfirst(bithrtreethrt)--------------先序遍历voidmid(bithrtreethrt)---------------中序遍历voidlast(bithrtreet)--------------后序遍历bithrtreecopy(bithrtree&r)---------复制建立后的二叉树bithrtreecreat(bithrtree&T)（2）.程序代码如下：#include<stdio.h>#include<string.h>#include<malloc.h>#include<stdlib.h>#defineOVERFLOW-2#defineOK1#defineerror0typedefintStatus;typedefenumpointertag{link=0,thread=1};//link==0;指针thread==1；线索typedefstructbithrnode{chardata;structbithrnode*lchild,*rchild;//左右孩子指针intltag,rtag;}bithrnode,*bithrtree;bithrtreepre;bithrtreecreat(bithrtree&T)//构造二叉树{charch;fflush(stdin);scanf("%c",&ch);if(ch==''||ch=='#')T=NULL;else{if(!(T=(bithrnode*)malloc(sizeof(bithrnode))))returnerror;T->data=ch;T->ltag=0;T->rtag=0;printf("输入父结点%c的左孩子：",ch);T->lchild=creat(T->lchild);printf("输入父结点%c的右孩子：",ch);T->rchild=creat(T->rchild);}returnT;}voidPreThreading(bithrtreep)//先序线索化{if(p){if(!p->lchild){p->ltag=thread;p->lchild=pre;}//前驱线索if(!pre->rc