二叉树实验报告
姓名：张桂阳 学号：201011232023
一：需求分析
（1本程序需要用户自行输入二叉树（二叉树的数据可以是任何字符），用”#”表示空格，按回车键结束！
（2）程序功能：递归遍历二叉树，线索化二叉树，遍历线索化二叉树，二叉树去线索化。
（3）测试数据：ab##c##
二、概要设计
为实现本程序功能，应以二叉树结构存储二叉树，而为了实现非递归遍历二叉树的功能，应以带头节点的栈存储二叉树。
1、 二叉树的抽象数据类型定义
ADT BinaryTree{
数据对象D：D是具有相同特性的数据元素集合。
数据关系R：如D=Ф，则R=Ф，称BinaryTree为空二叉树；
如D≠Ф，则R={H}，H是如下二元关系：
（1）在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；
（2）如D-{root}≠Ф,则存在D-{root}={D1,Dr},且D1∩Dr=Ф;
（3）如D1≠Ф,则D1中存在唯一元素x1,<ROOT,X< SPAN>1>∈H,且存在D1上的关系H1∈H；如Dr≠Ф，则Dr中存在唯一的元素xr，<ROOT,X< SPAN>r>∈H,且存在Dr上的关系Hr包含于H；H={<ROOT,X< SPAN>1>,<ROOT,X< SPAN>r>,H1,Hr}；
（4）(D1,{H1})是一棵符合本定义的二叉树，称为根的右子树。
基本操作：
InitBiTree(&T);
操作结果：构造空二叉树T.
DestroyBiTree(&T);
初始条件：二叉树T存在。
操作结果：销毁二叉树T.
CreateBiThrTree(&T);
操作结果：先序构造二叉树T,Ltag和RTag初始置为Link.
PreOrderTraverse(T );
初始条件：二叉树T存在。
操作结果：先序递归遍历T。
InOrderTraverse(T);
初始条件：二叉树T存在。
操作结果：中序递归遍历T。
PostOrderTraverse(T);
初始条件：二叉树T存在。
操作结果：后序递归遍历T。
InOrderThreading(&ThrT, T);
初始条件：二叉树T存在。
操作结果：建立头结点ThrT,并调用InThreading(T);函数。
InThreading(T);
初始条件：二叉树T存在。
操作结果：中序线索化二叉树T;
InOrderTrasverse_Thr(T);
初始条件：二叉树T存在。
操作结果：中序扫描线索化的二叉树。
}ADT BinaryTree
2、 栈的抽象数据类型定义
ADT Stack{
数据对象：d={ ai |ai∈elemset,i=1,2,3,……，n，n≥0}
数据关系：r={<ai-1,ai,)>| ai-1,ai ∈d, i=2,3,……，n}
约定a1为栈底，an 为栈顶。
基本操作：
（1）InitStack(&S)
操作结果：构造一个空栈S。
（2）DestroyStack(&S)
初始条件：栈S已存在。
操作结果：销毁栈S。
（3）ClearStack（&S）
初始条件：栈S已存在。。
操作结果：将栈清空为空栈。
（4）StackEmpty(&S)
初始条件：栈S已存在。
操作结果：若栈S为空栈，则返回TRUE，否则FALSE。
（5）StackLength（&S）
初始条件：栈S已存在。
操作结果：返回栈的长度（或者说深度）。
（6）GetTop（S，&e）
初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
（7）Push（&S,e）
初始条件：栈S已存在。
操作结果：在栈顶插入新的元素e。
（8）Pop（&S,&e）
初始条件：栈S已存在且非空。
操作结果：删除栈S的栈顶元素，并且用e返回它的值。
（9）StackTraverse（S，visit（））
初始条件：栈S已存在。
操作结果：遍历访问栈，一次对S的每个元素调用函
}ADT Stack
3、 程序包括6个模块
1） 主程序模块：
2） 创建二叉树；
3） 计算树的高度；
4） 递归遍历二叉树（先、中、后序）；
5） 非递归遍历二叉树（先、中、后序）；
6） 线索化二叉树（先、中序）；
7） 二叉树去线索化（后序）
三、详细设计
1、 元素类型、结点类型
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild ,*rchild;
PointerTag LTag , RTag;
}BiTNode , *BiTree , BiThrNode , *BiThrTree; //二叉树存储结构
typedef struct{
BiTNode *base;
BiTNode *top;
int stacksize;
}SqStack; //栈存储结构
2、 栈的实现
typedef struct{
char *base;
char *top;
int stacksize;
}SqStack; //栈类型
栈的基本操作设置如下：
void InitStack(Stack &S)
//初始化，设S为空栈（S.top=NULL）
void DestroyStack(Stack &S)
//销毁栈S，并释放所占空间
void ClearStack(Stack &S)
//将S清为空栈
int StackLength(Stack S)
//返回栈S的长度S.size
Status StackEmpty(Stack S)
//若S为空栈（S.top==NULL），则返回TRUE；否则返回FALSE
Status GetTop(Stack S,ElemType e)
//若栈S不空，则以e带回栈顶元素并返回TRUE，否则返回FALSE
Status Push(Stack&S,ElemType e)
//若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE，
//否则返回FALSE
void StackTraverse(Stack S,Status (*visit)(ElemType e))
//从栈底到栈顶依次对S中的每个结点调用函数visit
栈的基本操作设置如下：
void InitStack(Stack &S)
//初始化，设S为空栈（S.top=NULL）
void DestroyStack(Stack &S)
//销毁栈S，并释放所占空间
void ClearStack(Stack &S)
//将S清为空栈
int StackLength(Stack S)
//返回栈S的长度S.size
Status StackEmpty(Stack S)
//若S为空栈（S.top==NULL），则返回TRUE；否则返回FALSE
Status GetTop(Stack S,ElemType e)
//若栈S不空，则以e带回栈顶元素并返回TRUE，否则返回FALSE
Status Push(Stack&S,ElemType e)
//若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE，
//否则返回FALSE
void StackTraverse(Stack S,Status (*visit)(ElemType e))
//从栈底到栈顶依次对S中的每个结点调用函数visit
3、 主函数和其他函数的代码
int main() //主函数
{
printf("\t************\n\t*二叉树演示*\n\t************\n");
BiTree T;
BiThrTree Thrt;
printf("\n创建二叉树(用#表示空格):\n");
CreatBiTree(T);
printf("树的高度为:%d",treedepth(T));
printf("\n递归先序遍历:");
PreOrderTraverse(T , Visit);
printf("\n递归中序遍历:");
InOrderTraverse(T , Visit);
printf("\n递归后序遍历:");
PostOrderTraverse(T , Visit);
/*
printf("\n非递归先序遍历:");
UnPreOrderTraverse(T , Visit);
printf("\n非递归中序遍历:");
UnInOrderTraverse(T , Visit);*/
printf("\n中序遍历线索化二叉树:");
InOrderThreading(Thrt , T);
InOrderTraverse_Thr(Thrt , Visit);
printf("\n后序递归去线索化并输出:");
UnThreading(Thrt);
printf("\n先序遍历线索化二叉树:");
PreOrderThreading(Thrt , T);
printf("\n");
}
status PreOrderTraverse(BiTree T,status(*Visit)(TElemType e)) //递归先序遍历
{
if(T)
{
if(Visit(T->data))
if(PreOrderTraverse(T->lchild,Visit))
if(PreOrderTraverse(T->rchild,Visit))
return OK;
return ERROR;
}
else
return OK;
}//PreOrderTraverse
status InOrderTraverse(BiTree T,status(*Visit)(TElemType e)) //递归中序遍历
{
if(T)
{
if(InOrderTraverse(T->lchild,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->rchild,Visit))
return OK;
return ERROR;
}
else return OK;
}//InOrderTraverse
status PostOrderTraverse(BiTree T,status(*Visit)(TElemType e)) //递归后序遍历
{
if(T)
{
if(PostOrderTraverse(T->lchild,Visit))
if(PostOrderTraverse(T->rchild,Visit))
if(Visit(T->data))
return OK;
return ERROR;
}
else return OK;
}//PostOrderTraverse
status UnPreOrderTraverse(BiTree T,status(*Visit)(TElemType e)) //非递归先序遍历
{
BiTree p;
SqStack S;
InitStack(S);
p=T;
while(p||!StackEmpty(S))
{
if(p)
{
Push(S,p);
p=p->lchild;
}
else
{
Pop(S,p);
p=p->rchild;
}//else
}//while
return OK;
}//UnPreOrderTraverse
status UnInOrderTraverse(BiTree T,status(*Visit)(TElemType e)) //非递归中序遍历
{
BiTree p;
p=T;
SqStack S;
InitStack(S);
while(p||!StackEmpty(S))
{
if(p)
{
Push(S,p);
p=p->lchild;
}
else
{
Pop(S,p);
if(!Visit(p->data)) return ERROR;
p=p->rchild;
}//else
}//while
return OK;
}//UnInOrderTraverse
/*
status UnPostOrderTraverse(BiTree T,status(*Visit)(TElemType e))
//非递归后序遍历
{
BiTree p;
p=T;
SqStack S;
InitStack(S);
int Tag[20];//栈，用于标识从左(0)或右(1)返回
while(p||!StackEmpty(S))
{
while(p)
{
Push(S,p);
Tag[S]=0;
p=p->lchild;
}
while(!StackEmpty(S)&&Tag[S->top]==1)
{ Pop(S,p);
Visit(p->data);
}
if(!StackEmpty(S))
{ Tag[S->top]=1;
p=
} p=p->rchild;
if(!Visit(p->data)) return ERROR;
}//elseVisit(p->data);
}//while
return OK;
}//UnPostOrderTraverse*/
status InOrderThreading(BiThrTree &Thrt,BiThrTree T)
//中序遍厉二叉树T，并将其中序线索化，Thrt指向头结点
{
if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
Thrt->LTag=Link;//建头结点
Thrt->RTag=Thread;
Thrt->rchild=Thrt;//右指针回指
if(!T)
Thrt->lchild=Thrt;
else
{
Thrt->lchild=T;
pre=Thrt;
InThreading(T);//中序遍历进行中序线索化
pre->rchild=Thrt;
pre->RTag=Thread;//最后一个结点线索化
Thrt->rchild=pre;
}
i=Thrt;
}//InOrderThreading
void InThreading(BiThrTree p) //中序遍历线索化
{
if(p)
{
InThreading(p->lchild);
if(!p->lchild)
{
p->LTag = Thread;
p->lchild = pre;
}
if(!pre->rchild)
{
pre->RTag = Thread;
pre->rchild = p;
}
pre = p;
InThreading(p->rchild);
}
}//InThreading
void UnThreading(BiThrTree &Thrt) //后序去线索化
{
BiThrTree p=Thrt;
if(p)
{
if(p->LTag == Thread)
{
p->lchild = NULL;
p->LTag = Link;
}
if(p->LTag == Link && p->lchild) UnThreading(p->lchild);
if(p->RTag == Link && p->rchild)UnThreading(p->rchild);
if(p != i) Visit(p->data);
}
}
status InOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType e))
//中序遍历线索化后的二叉树
{
BiThrTree p;
p=T->lchild;
while(p!=T)
{
while(p->LTag==Link)
p=p->lchild;
if(!Visit(p->data))
return ERROR;
while(p->RTag==Thread && p->rchild!=T)
{
p=p->rchild;
Visit(p->data);
}
p=p->rchild;
}
return OK;
}
void PreOrderThreading(BiThrTree &Thrt,BiThrTree T)
//先序遍厉二叉树T，并将其先序线索化，Thrt指向头结点
{
if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
Thrt->LTag=Link;
Thrt->RTag=Thread;//建头结点
Thrt->rchild=Thrt;//右指针回指
if(!T)
Thrt->lchild=Thrt;
else
{
Thrt->lchild=T;
pre=Thrt;
PreThreading(T);//先序遍历进行先序线索化
pre->rchild=Thrt;pre->RTag=Thread;//最后一个结点线索化
Thrt->rchild=pre;
}
i=Thrt;
}
status PreOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType e))
//先序遍历线索化后的二叉树
{
BiThrTree p;
p=T->lchild;
while(p!=T)
{
while(p->LTag==Link)
p=p->lchild;
if(!Visit(p->data))
return ERROR;
while(p->RTag==Thread && p->rchild!=T)
{
p=p->rchild; Visit(p->data);
}
p=p->rchild;
}
return OK;
}//PreOrderTraverse_Thr
void PreThreading(BiThrTree p) //先序线索化
{
if(p)
{
if(!p->lchild)
{
p->LTag = Thread;
p->lchild = pre;
}
if(!pre->rchild)
{
pre->RTag = Thread;
pre->rchild = p;
}
pre = p;
Visit(p->data);
if(p->LTag==Link)
PreThreading(p->lchild);
if(p->RTag == Link)
PreThreading(p->rchild);
}
}//PreThreading
四、调试分析
1、在线索化二叉树时，如果像书上把二叉树和线索二叉树的存储结构分开，则二叉树中的数据域不能传递到线索二叉树中（两个类型的指针不能互相赋值）。比较两种存储结构发现，线索二叉树比二叉树多了两个标志域LTag,Rtag。于是把两种存储结构合并为BiThrNode,并在建立二叉树时把LTag,Rtag均置为Link。程序正常运行。
2、本次实验报告所用的算法，书中均有具体算法演示，且易实现。
五、用户手册
1、本程序开发环境为c-free 5.0，运行环境为dos操作系统，执行文件为：二叉树.exe
2、运行该程序的二叉树.exe文件,产生如下图所示的界面：
3、按照提示输入二叉树（以”#”表示空格），如可以输入ab##c##。
4、输入完成后，按回车键。
5、屏幕上打印出对应于该二叉树的的各种遍历结果。
