2022年数据结构二叉树遍历实验报告.pdf

《2022年数据结构二叉树遍历实验报告.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构二叉树遍历实验报告.pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构之二叉树实验报告题目 :二叉树的遍历和子树交换指导老师 : 杨政宇班级：通信1202姓名 : 徐江学号： 07精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 17 页 - - - - - - - - - - 需求分析1. 演示程序分别用多种遍历算法遍历二叉树并把数据输出。2. 输入字符序列，递归方式建立二叉树。3. 在演示过程序中，用户敲击键盘，输入数据，即可看到数据的输出。4. 实现链式存储的二叉树的多种遍历算法。遍历算法包括：a)中序递归遍历算法、前序递归遍历算法【选】b)中序遍历

2、非递归算法c) 先序或后序遍历非递归算法d)建立中序线索，并进行中序遍历和反中序遍历5. 实现二叉树的按层遍历算法6. 设计一个测试用的二叉树并创建对应的内存二叉树，能够测试自己算法的边界( 包括树节点数为 0、1以及1 的不同情形 ) 。7. 测试数据：输入数据： -+a *b -c d -e f 概要设计说明：本程序在递归调用中用到了链表，在非递归调用时用到了栈。1. 栈的抽象数据类型ADT Stack数据对象： D=ai|aichar,i=1,2,3.数据关系： R=| ai-1,aiD,i=2,3 .基本操作：InitStack（&S ）操作结果：构造一个空栈StackEmpty( S

3、 )精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 17 页 - - - - - - - - - - 初始条件：栈 S已存在。操作结果：若 S为空栈，则返回 OK ，否则返回 ERROR。Push( &S, e )初始条件：栈 S已存在。操作结果：插入元素e 为新的栈顶元素。Pop( &S, &e )初始条件：栈 S已存在且非空。操作结果：删除 S的栈顶元素，并用e 返回其值。GetTop( S, &e )初始条件：栈 S已存在且非空。操作结果：用 e 返回 S的栈顶元素。2. 二叉树的抽象数

4、据类型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， H ，且存在 D1上的关系 H1 ? H；若 Dr，则 Dr 中存在惟一的元素xr ， H ，且存在上的关系Hr ? H；精品资料 - - - 欢迎下载 - - - - - - - - - - -

5、 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 17 页 - - - - - - - - - - H=,H1,Hr；（4）(D1,H1) 是一棵符合本定义的二叉树，称为根的左子树；(Dr,Hr)是一棵符合本定义的二叉树，称为根的右子树。基本操作：CreateBiTree( &T) 初始条件：给出二叉树T 的定义。操作结果：按要求构造二叉树T。PreOrderTraverse_re( T, print() ) 初始条件：二叉树 T存在，print是二叉树全部结点输出的应用函数。操作结果： 先序递归遍历 T，对每个结点调用函数print一次且仅一次。一旦 print()

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

7、树全部结点输出的应用函数。操作结果： 先序非递归遍历 T，对每个结点调用函数print一次且仅一次。一旦 print()失败，则操作失败。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 17 页 - - - - - - - - - - Levelorder(T) 初始条件：二叉树T在在。操作结果：分层遍历二叉树T，并输出。InOrderThreading(Thrt,T);初始条件：二叉树T在在。操作结果：中序遍历二叉树，并将其中序线索化。InOrderTraverse_Thr( T, prin

8、t);初始条件：二叉树T在在。操作结果：中序非递归遍历二叉线索树TInThreading(p);初始条件：结点p 在在。操作结果：结点p 及子树线索化。3. 主程序的流程：void main()初始化 ;提示;执行二叉数 ADT函数;4. 本程序包含三个模块1）主程序模块void main()初始化；接受命令；显示结果；精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 17 页 - - - - - - - - - - 2）链表模块。递归调用时实现链表抽象数据类型。3）栈模块。非递归调用时实现栈的

9、抽象数据类型。详细设计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); 叉树链表数据结构：typedef struct BiTNodeTElemType data;struct BiTNode *l

10、child ,*rchild;PointerTag LTag , RTag;BiTNode , *BiTree , BiThrNode , *BiThrTree; 基本操作：a)构造二叉树 Tint CreateBiTree(BiTree &T)精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 17 页 - - - - - - - - - - char ch;scanf(%c,&ch);if(ch= )T=NULL;elseif(!(T=(BiTNode *)malloc(sizeof(BiTN

11、ode)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);return ;els

12、ereturn ;精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 17 页 - - - - - - - - - - c) 中序非递归遍历二叉树T，并输出全部结点值void InOrderTraverse(BiTree T,int (*print)(TElemType e)SqStack S;=NULL;=NULL;SElemType p=NULL;InitStack(S);Push(S,T);while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lc

13、hild);Pop(S,p);if(!StackEmpty(S)Pop(S,p);print(p-data);Push(S,p-rchild);return;d)中序递归遍历二叉树T，并输出全部结点值void InOrderTraverse_re(BiTree T,int (*print)(TElemType e) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 17 页 - - - - - - - - - - if(T) InOrderTraverse_re(T-lchild,print);

14、 print(T-data); InOrderTraverse_re(T-rchild,print); e)中序遍历二叉树 T，并将其中序线索化， Thrt 指向头结点 void InOrderThreading(BiThrTree &Thrt,BiThrTree T)Thrt=(BiThrTree)malloc(sizeof(BiThrNode);Thrt-LTag=Link;数据结构：typedef structSElemType *base;SElemType *top;int stacksize;SqStack;基本操作：a)创建一个空栈void InitStack(SqStack &

15、S)=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);=; 函数void main()精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 17 页 - - - - - - - - - - int flag;BiTree T;BiThrTree Thrt;printf(*n);printf(* 实 验12 二 叉 树 的 遍 历*n);printf(* 1. 实现二叉树的不同遍历算法和二叉树的中序线索化算法*n);printf(* a) 中序

16、递归遍历算法；*n);printf(* b) 先序递归遍历算法；*n);printf(* c) 中序遍历的非递归算法；*n);printf(* d) 先 序 或 后 序 遍 历 非 递 归 算 法 之 一 ；*n);printf(* e) 建立 中序 线利 用线 索进 行中 序遍 历和 反中 序 遍 历 。*n);printf(* 2. 实现二叉树的按层遍历算法。*n);printf(*n);printf(n选择操作：nt1.先序与中序遍历算法 nt2.中序线索的中序遍历和反中序遍历算法 nt3.按层遍历算法 n 请选择： );scanf(%d,&flag);switch(flag)精品资料

17、- - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 17 页 - - - - - - - - - - case 1: printf(前序递归创建二叉树（空格表示此结点为空） :n);getchar();CreateBiTree(T);printf(中序递归遍历输出 :);InOrderTraverse_re(T,print);printf(n前序递归遍历输出： );PreOrderTraverse_re(T,print);printf(n中序非递归遍历输出： );InOrderTraverse(T,pri

18、nt);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(前序递归创建二叉树（空格表示此结点为空） :n);getchar();CreateBiTree

19、(T);printf(n按层遍历输出： );精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 17 页 - - - - - - - - - - Levelorder(T);printf(n);break;default:return;6. 函数间调用关系调试分析1、二叉树的分层遍历，开始时想用队列来做，但考虑到比较麻烦，因而改为数组模拟队列，简单易懂，课后可自行尝试用队列来做。2在线索化二叉树时考虑到如果将两种存储结构分开将导致两个类型的指针不能互相传值，造成许多麻烦。比较两种存储结构发现，线

20、索二叉树比二叉树多了两个标志域LTag,Rtag 。于是把两种存储结构合并为BiThrNode, 并在建立二叉树时把LTag,Rtag 均置为Link 。程序正常运行。 3. 进入演示程序，完成编译，连接（即按下Ctrl F5）进入演示界面，或直接打开执行文件，产生如下图所示的界面：mainInOrderTCreateBiPreOrdeInOrderTPreOrderTInOrderTInOrderTrThreadinStack 操精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 17 页 -

21、 - - - - - - - - - 用户需根据用户提示信息操作，输入二叉树（以空格表示空结点），输入完成后按回车键，屏幕上打印出对应于该二叉树的各种遍历结果。如下图：六、测试结果输入： -+a *b -c d -e f 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 17 页 - - - - - - - - - - 屏幕输出：中序递归遍历输出：a+b*c-d前序递归遍历输出：+a*b-cd中序非递归遍历输出：a+b*c-d前序非递归遍历输出：+a*b-cd按层遍历输出：+a*b-cd中序遍

22、历线索化二叉树：a+b*c-d七、附录#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; 实现二叉树的不同遍历算法和二叉树的中序线索化算法 *n);printf(* a) 中序递归遍历算法； *n);printf(* b) 先序递归遍历算法； *n);prin

23、tf(* c) 中序遍历的非递归算法； *n);printf(* d) 先序或后序遍历非递归算法之一； *n);精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 14 页，共 17 页 - - - - - - - - - - printf(* e) 建立中序线利用线索进行中序遍历和反中序遍历。 *n);printf(* 2. 实现二叉树的按层遍历算法。 *n);printf(*n);/* printf(n选择操作： nt1.先序与中序遍历算法nt2.中序线索的中序遍历和反中序遍历算法 nt3.按层遍历算法

24、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);br

25、eak;case 2: printf(前序递归创建二叉树（空格表示此结点为空）:n);getchar();CreateBiTree(T);printf(n中序遍历线索化二叉树:);InOrderThreading(Thrt , T);精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 15 页，共 17 页 - - - - - - - - - - InOrderTraverse_Thr(Thrt , print);break;case 3: printf(前序递归创建二叉树（空格表示此结点为空）:n);get

26、char();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前序非递归遍历输出

27、：);PreOrderTraverse(T,print); printf(n按层遍历输出：);Levelorder(T);printf(n中序遍历线索化二叉树:);精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 16 页，共 17 页 - - - - - - - - - - InOrderThreading(Thrt , T);InOrderTraverse_Thr(Thrt , print);printf(n);while(1);return;精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 17 页，共 17 页 - - - - - - - - - -