数据结构-二叉树遍历实验报告

《数据结构-二叉树遍历实验报告》由会员分享，可在线阅读，更多相关《数据结构-二叉树遍历实验报告（21页珍藏版）》请在装配图网上搜索。

1、数据结构之二叉树实 验 报 告 题目:二叉树的遍历和子树交换 指导老师:杨政宇 班级：通信1202 姓名:徐江 学号：0909121127需求分析1. 演示程序分别用多种遍历算法遍历二叉树并把数据输出。2. 输入字符序列，递归方式建立二叉树。3.在演示过程序中，用户敲击键盘，输入数据，即可看到数据的输出。4.实现链式存储的二叉树的多种遍历算法。遍历算法包括：a) 中序递归遍历算法、前序递归遍历算法【选】b) 中序遍历非递归算法c) 先序或后序遍历非递归算法d) 建立中序线索，并进行中序遍历和反中序遍历5.实现二叉树的按层遍历算法6.设计一个测试用的二叉树并创建对应的内存二叉树，能够测试自己算法

2、的边界(包括树节点数为0、1以及1 的不同情形)。7.测试数据：输入数据：-+a *b -c d -e f 概要设计说明：本程序在递归调用中用到了链表，在非递归调用时用到了栈。1. 栈的抽象数据类型ADT Stack数据对象：D=ai|aichar,i=1,2,3.数据关系：R=| ai -1,ai D,i=2,3.基本操作：InitStack（&S） 操作结果：构造一个空栈StackEmpty( S ) 初始条件：栈S已存在。 操作结果：若S为空栈，则返回OK，否则返回ERROR。 Push( &S, e ) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 Pop( &S, &

3、e ) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 GetTop( S, &e ) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 2.二叉树的抽象数据类型ADT BinaryTree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若D=，则R=，称BinaryTree为空二叉树； 若D，则R=H，H是如下二元关系； （1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱； （2）若D-root，则存在D-root=D1,Dr，且D1Dr =； （3）若D1，则D1中存在惟一的元素x1，H，且存在D1上的 关系H1 H

4、；若Dr，则Dr中存在惟一的元素xr，H，且 存在上的关系Hr H；H=,H1,Hr； （4）(D1,H1)是一棵符合本定义的二叉树，称为根的左子树；(Dr,Hr)是一 棵符合本定义的二叉树，称为根的右子树。 基本操作： CreateBiTree( &T) 初始条件：给出二叉树T的定义。 操作结果：按要求构造二叉树T。 PreOrderTraverse_re( T, print() ) 初始条件：二叉树T存在，print是二叉树全部结点输出的应用函数。 操作结果：先序递归遍历T，对每个结点调用函数print一次且仅一次。一旦 print()失败，则操作失败。 InOrderTraverse(

5、T, print() ) 初始条件：二叉树T存在，print是二叉树全部结点输出的应用函数。 操作结果：中序非递归遍历T，对每个结点调用函数print一次且仅一次。一 旦printf()失败，则操作失败。 InOrderTraverse_re(T,print() ) 初始条件：二叉树T在在，print是二叉树全部结点输出的应用函数。操作结果：中序递归遍历T，对每个结点调用函数print一次且仅一次。一旦 printf()失败，则操作失败。 PreOrderTraverse(T,print() 初始条件：二叉树T存在，print是二叉树全部结点输出的应用函数。 操作结果：先序非递归遍历T，对每个

6、结点调用函数print一次且仅一次。一 旦print()失败，则操作失败。 Levelorder(T) 初始条件：二叉树T在在。操作结果：分层遍历二叉树T，并输出。InOrderThreading(Thrt,T);初始条件：二叉树T在在。操作结果：中序遍历二叉树，并将其中序线索化。InOrderTraverse_Thr( T, print);初始条件：二叉树T在在。操作结果：中序非递归遍历二叉线索树TInThreading(p);初始条件：结点p在在。操作结果：结点p及子树线索化。3.主程序的流程：void main()初始化;提示;执行二叉数ADT函数;4.本程序包含三个模块1） 主程序模块

7、void main()初始化；接受命令；显示结果；2） 链表模块。递归调用时实现链表抽象数据类型。3） 栈模块。非递归调用时实现栈的抽象数据类型。详细设计1.宏定义及全局变量#define TElemType char#define SElemType BiTree#define OK 1#define OVERFLOW 0#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10SqStack S;BiThrTree pre;BiThrTree i;2.函数定义int CreateBiTree(BiTree &T);

8、/创建二叉树void PreOrderTraverse_re(BiTree T,void (*print)(TElemType e);/先序递归遍历二叉树void InOrderTraverse(BiTree T,int (*print)(TElemType e);/中序非递归遍历二叉树void InOrderTraverse_re(BiTree T,int (*print)(TElemType e) ;/中序递归遍历二叉树void PreOrderTraverse(BiTree T,int (*print)(TElemType e);/先序非递归遍历二叉树int print(TElemTyp

9、e e);/打印元素void InitStack(SqStack &S);/栈的初始化void Pop(SqStack &S,SElemType &e);void Push(SqStack &S,SElemType &e);int StackEmpty(SqStack S);int GetTop(SqStack S,SElemType &e);void Levelorder(BiTree T) ;void InOrderThreading(BiThrTree &Thrt,BiThrTree T);int InOrderTraverse_Thr(BiThrTree T, int (*print)

10、(TElemType e);void InThreading(BiThrTree p);3.二叉树链表数据结构：typedef struct BiTNodeTElemType data;struct BiTNode *lchild ,*rchild;PointerTag LTag , RTag;BiTNode , *BiTree , BiThrNode , *BiThrTree; 基本操作：a)构造二叉树Tint CreateBiTree(BiTree &T)char ch;scanf(%c,&ch);if(ch= )T=NULL;elseif(!(T=(BiTNode *)malloc(si

11、zeof(BiTNode)return ERROR;T-data=ch;if (CreateBiTree(T-lchild) T-LTag=Link;if (CreateBiTree(T-rchild) T-RTag=Link;return OK;b)先序递归遍历二叉数T，并输出全部结点值。void PreOrderTraverse_re(BiTree T,int (*print)(TElemType e)if(T)if(print(T-data) PreOrderTraverse_re(T-lchild,print);PreOrderTraverse_re(T-rchild,print);r

12、eturn ;elsereturn ;c)中序非递归遍历二叉树T，并输出全部结点值void InOrderTraverse(BiTree T,int (*print)(TElemType e)SqStack S;S.base=NULL;S.top=NULL;SElemType p=NULL;InitStack(S);Push(S,T);while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild);Pop(S,p);if(!StackEmpty(S)Pop(S,p);print(p-data);Push(S,p-rchild);return;d

13、)中序递归遍历二叉树T，并输出全部结点值void InOrderTraverse_re(BiTree T,int (*print)(TElemType e) if(T) InOrderTraverse_re(T-lchild,print); print(T-data); InOrderTraverse_re(T-rchild,print); e)中序遍历二叉树T，并将其中序线索化，Thrt指向头结点 void InOrderThreading(BiThrTree &Thrt,BiThrTree T)Thrt=(BiThrTree)malloc(sizeof(BiThrNode);Thrt-LT

14、ag=Link;/建头结点Thrt-RTag=Thread;Thrt-rchild=Thrt;/右指针回指if(!T)Thrt-lchild=Thrt;elseThrt-lchild=T;pre=Thrt;InThreading(T);/中序遍历进行中序线索化pre-rchild=Thrt;pre-RTag=Thread;/最后一个结点线索化Thrt-rchild=pre;i=Thrt;/InOrderThreadingf)结点p线索化void InThreading(BiThrTree p) if (p) InThreading(p-lchild); / 左子树线索化 if (!p-lchi

15、ld) / 建前驱线索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后继线索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持pre指向p的前驱 InThreading(p-rchild); / 右子树线索化 / InThreadingg)/中序遍历线索化二叉树int InOrderTraverse_Thr(BiThrTree T, int (*print)(TElemType e)BiThrTree p=NULL;p=T-lchild;while(p!=T)while(p-LTag=

16、Link)p=p-lchild;if(!print(p-data)return ERROR;while(p-RTag=Thread & p-rchild!=T)p=p-rchild;print(p-data);p=p-rchild;return OK;4.栈数据结构：typedef structSElemType *base;SElemType *top;int stacksize;SqStack;基本操作：a)创建一个空栈void InitStack(SqStack &S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);

17、S.top=S.base;/初始为空S.stacksize=STACK_INIT_SIZE;return;b)栈顶插入元素void Push(SqStack &S,SElemType &e)if(S.top-S.base=S.stacksize)S.base=(SElemType*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;c)栈顶删除元素void Pop(SqStack &S,S

18、ElemType &e)if(S.top=S.base)return;e=*-S.top;return;d)判断栈是否为空栈int StackEmpty(SqStack S)if(S.top=S.base)return OK;elsereturn ERROR;e)e返回S的栈顶元素int GetTop(SqStack S,SElemType &e)if(S.top=S.base)return ERROR;e=*(S.top-1);return OK;5.主函数void main()int flag;BiTree T;BiThrTree Thrt;printf(*n);printf(* 实验12

19、 二叉树的遍历 *n);printf(* 1. 实现二叉树的不同遍历算法和二叉树的中序线索化算法 *n);printf(* a) 中序递归遍历算法； *n);printf(* b) 先序递归遍历算法； *n);printf(* c) 中序遍历的非递归算法； *n);printf(* d) 先序或后序遍历非递归算法之一； *n);printf(* e) 建立中序线利用线索进行中序遍历和反中序遍历。 *n);printf(* 2. 实现二叉树的按层遍历算法。 *n);printf(*n);printf(n选择操作：nt1.先序与中序遍历算法nt2.中序线索的中序遍历和反中序遍历算法nt3.按层遍历

20、算法n请选择：);scanf(%d,&flag);switch(flag) case 1:printf(前序递归创建二叉树（空格 表示此结点为空）:n);getchar();CreateBiTree(T);printf(中序递归遍历输出:);InOrderTraverse_re(T,print);printf(n前序递归遍历输出：);PreOrderTraverse_re(T,print);printf(n中序非递归遍历输出：);InOrderTraverse(T,print);printf(n前序非递归遍历输出：);PreOrderTraverse(T,print); printf(n);b

21、reak;case 2:printf(前序递归创建二叉树（空格 表示此结点为空）:n);getchar();CreateBiTree(T);printf(n中序遍历线索化二叉树:);InOrderThreading(Thrt , T);InOrderTraverse_Thr(Thrt , print);break;case 3: printf(前序递归创建二叉树（空格 表示此结点为空）:n);getchar();CreateBiTree(T);printf(n按层遍历输出：);Levelorder(T);printf(n);break;default:return;6. 函数间调用关系main

22、InOrderTraverse_reCreateBitreePreOrderTraverse_reInOrderTraversePreOrderTraverseInOrderThreadingInOrderTraverse_ThrThreadingStack操作调试分析1、二叉树的分层遍历，开始时想用队列来做，但考虑到比较麻烦，因而改为数组模拟队列，简单易懂，课后可自行尝试用队列来做。2 在线索化二叉树时考虑到如果将两种存储结构分开将导致两个类型的指针不能互相传值，造成许多麻烦。比较两种存储结构发现，线索二叉树比二叉树多了两个标志域LTag,Rtag。于是把两种存储结构合并为BiThrNode

23、,并在建立二叉树时把LTag,Rtag均置为Link。程序正常运行。 3.进入演示程序BiTree.cpp，完成编译，连接（即按下Ctrl F5）进入演示界面，或直接打开执行文件BiTree.exe，产生如下图所示的界面： 用户需根据用户提示信息操作，输入二叉树（以空格表示空结点），输入完成后按回车键，屏幕上打印出对应于该二叉树的各种遍历结果。如下图：六、 测试结果输入：-+a *b -c d -e f 屏幕输出：中序递归遍历输出：a+b*c-d前序递归遍历输出：+a*b-cd中序非递归遍历输出：a+b*c-d前序非递归遍历输出：+a*b-cd按层遍历输出：+a*b-cd中序遍历线索化二叉树：

24、a+b*c-d七、 附录BiTree.cppBiTree.exe#include#include#define QElemType BiTNode#define TElemType char#define OK 1#define OVERFLOW 0#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef enum PointerTagLink,Thread;/Link=0,指针，Thread=1,线索typedef struct BiTNodeTElemType data;struct BiTNode

25、 *lchild ,*rchild;PointerTag LTag , RTag;BiTNode , *BiTree , BiThrNode , *BiThrTree;/二叉树 #define QElemType BiTNode#define SElemType BiTreetypedef structSElemType *base;SElemType *top;int stacksize;SqStack;/全局变量SqStack S;BiThrTree pre;BiThrTree i;/*函数声明*/ int CreateBiTree(BiTree &T);/创建二叉树void PreOrd

26、erTraverse_re(BiTree T,void (*print)(TElemType e);/先序递归遍历二叉树void InOrderTraverse(BiTree T,int (*print)(TElemType e);/中序非递归遍历二叉树void InOrderTraverse_re(BiTree T,int (*print)(TElemType e) ;/中序递归遍历二叉树void PreOrderTraverse(BiTree T,int (*print)(TElemType e);/先序非递归遍历二叉树int print(TElemType e);/打印元素void In

27、itStack(SqStack &S);/栈的初始化void Pop(SqStack &S,SElemType &e);void Push(SqStack &S,SElemType &e);int StackEmpty(SqStack S);int GetTop(SqStack S,SElemType &e);void Levelorder(BiTree T) ;void InOrderThreading(BiThrTree &Thrt,BiThrTree T);int InOrderTraverse_Thr(BiThrTree T, int (*print)(TElemType e);voi

28、d InThreading(BiThrTree p);/*二叉树的创建递归创建*/int CreateBiTree(BiTree &T)char ch;scanf(%c,&ch);if(ch= )T=NULL;elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode)return ERROR;T-data=ch;if (CreateBiTree(T-lchild) T-LTag=Link;if (CreateBiTree(T-rchild) T-RTag=Link;return OK; /*/ /* 先序递归遍历输出 */ /*/void PreOrderTrav

29、erse_re(BiTree T,int (*print)(TElemType e)if(T)if(print(T-data) PreOrderTraverse_re(T-lchild,print);PreOrderTraverse_re(T-rchild,print);return ;elsereturn ; /*/ /* 中序非递归遍历输出 */ /*/void InOrderTraverse(BiTree T,int (*print)(TElemType e)SqStack S;S.base=NULL;S.top=NULL;SElemType p=NULL;InitStack(S);Pu

30、sh(S,T);while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild);Pop(S,p);if(!StackEmpty(S)Pop(S,p);print(p-data);Push(S,p-rchild);return; /*/ /* 中序递归遍历输出 */ /*/void InOrderTraverse_re(BiTree T,int (*print)(TElemType e) if(T) InOrderTraverse_re(T-lchild,print); print(T-data); InOrderTraverse_re(T-rc

31、hild,print); return ; /*/ /* 按照前序非递归遍历二叉树：栈 */ /*/ void PreOrderTraverse(BiTree T,int (*print)(TElemType e) SqStack S;S.base=NULL;S.top=NULL;SElemType p=T;/p指向当前访问的结点 InitStack(S); while(p|!StackEmpty(S) if(p) print(p-data); Push(S,p); p=p-lchild; else Pop(S,p); p=p-rchild; return; void InOrderThrea

32、ding(BiThrTree &Thrt,BiThrTree T)/中序遍历二叉树T，并将其中序线索化，Thrt指向头结点Thrt=(BiThrTree)malloc(sizeof(BiThrNode);Thrt-LTag=Link;/建头结点Thrt-RTag=Thread;Thrt-rchild=Thrt;/右指针回指if(!T)Thrt-lchild=Thrt;elseThrt-lchild=T;pre=Thrt;InThreading(T);/中序遍历进行中序线索化pre-rchild=Thrt;pre-RTag=Thread;/最后一个结点线索化Thrt-rchild=pre;i=T

33、hrt;/InOrderThreadingvoid 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; / 保持pre指向p的前驱 InThreading(p-rchild); / 右子树线索化 / InThreadingint InOrderTraverse_Thr(Bi

34、ThrTree T, int (*print)(TElemType e)/中序遍历线索化后的二叉树BiThrTree p=NULL;p=T-lchild;while(p!=T)while(p-LTag=Link)p=p-lchild;if(!print(p-data)return ERROR;while(p-RTag=Thread & p-rchild!=T)p=p-rchild;print(p-data);p=p-rchild;return OK;/*以下为辅助函数*/int print(TElemType e)printf(%c,e);return OK;/*栈函数*/*栈的初始化*/vo

35、id InitStack(SqStack &S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);S.top=S.base;/初始为空S.stacksize=STACK_INIT_SIZE;return;/*栈顶插入元素*/void Push(SqStack &S,SElemType &e)if(S.top-S.base=S.stacksize)S.base=(SElemType*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType);S.top=

36、S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;/*栈顶删除元素*/void Pop(SqStack &S,SElemType &e)if(S.top=S.base)return;e=*-S.top;return;int StackEmpty(SqStack S)/*若栈为空栈，则返回OK，否则返回ERROR*/if(S.top=S.base)return OK;elsereturn ERROR;int GetTop(SqStack S,SElemType &e)if(S.top=S.base)return ERROR;e=*(

37、S.top-1);return OK; /*/ /* 按层次顺序建立一棵二叉树 */ /*/ void Levelorder(BiTree T) int i,j; BiTNode *q20,*p; /*q20用于模拟队列，存储入队的结点*/ p=T; if(p!=NULL) i=1;qi=p;j=2; /*i为队首位置，j为队尾位置*/ while(i!=j) p=qi; printf(%c,p-data); /*访问队首元素*/ if (p-lchild!=NULL) qj=p-lchild; j+; /*若队首元素左链域不为空，则将其入队列*/ if (p-rchild!=NULL) qj

38、=p-rchild; j+; /*若队首元素右链域不为空，则将其入队列*/ i+; /*将队首移到下一个位置*/ void main()int flag;BiTree T;BiThrTree Thrt;printf(*n);printf(* 实验12 二叉树的遍历 *n);printf(* 1. 实现二叉树的不同遍历算法和二叉树的中序线索化算法 *n);printf(* a) 中序递归遍历算法； *n);printf(* b) 先序递归遍历算法； *n);printf(* c) 中序遍历的非递归算法； *n);printf(* d) 先序或后序遍历非递归算法之一； *n);printf(* e

39、) 建立中序线利用线索进行中序遍历和反中序遍历。 *n);printf(* 2. 实现二叉树的按层遍历算法。 *n);printf(*n);/*printf(n选择操作：nt1.先序与中序遍历算法nt2.中序线索的中序遍历和反中序遍历算法nt3.按层遍历算法n请选择：);scanf(%d,&flag);switch(flag)case 1:printf(前序递归创建二叉树（空格 表示此结点为空）:n);getchar();CreateBiTree(T);printf(中序递归遍历输出:);InOrderTraverse_re(T,print);printf(n前序递归遍历输出：);PreOrd

40、erTraverse_re(T,print);printf(n中序非递归遍历输出：);InOrderTraverse(T,print);printf(n前序非递归遍历输出：);PreOrderTraverse(T,print); printf(n);break;case 2:printf(前序递归创建二叉树（空格 表示此结点为空）:n);getchar();CreateBiTree(T);printf(n中序遍历线索化二叉树:);InOrderThreading(Thrt , T);InOrderTraverse_Thr(Thrt , print);break;case 3: printf(前

41、序递归创建二叉树（空格 表示此结点为空）:n);getchar();CreateBiTree(T);printf(n按层遍历输出：);Levelorder(T);printf(n);break;default:return;*/printf(前序递归创建二叉树（空格 表示此结点为空）:n);getchar();CreateBiTree(T);printf(中序递归遍历输出:);InOrderTraverse_re(T,print);printf(n前序递归遍历输出：);PreOrderTraverse_re(T,print);printf(n中序非递归遍历输出：);InOrderTraverse(T,print);printf(n前序非递归遍历输出：);PreOrderTraverse(T,print); printf(n按层遍历输出：);Levelorder(T);printf(n中序遍历线索化二叉树:);InOrderThreading(Thrt , T);InOrderTraverse_Thr(Thrt , print);printf(n);while(1);return;