实验三：二叉树操作

人睜理虫学实验报告学院（系）名称： 计算机与通信工程学院* *学号专业计算机科学与技术班级2015级*班实验项目实验三：二叉树操作课程名称数据结构与算法课程代码0661013实验时间年 月 日第节实验地点7 *考核 标准实验过程25分程序运行20分回答问题15分实验报告30分特色 功能5分考勤违 纪情况5分成绩成绩 栏其它批改意见：教师签字：考核 容评价在实验 课堂中的表 现，包括实 验态度、编 写程序过程 等容等。功能完善，功能不全有小错无法运行O正确o基本正确O有提示o无法回答o完整o较完整o般o容极少o无报告o有o无o有o无一、实验目的理解二叉树的逻辑特点和二叉树的性质；掌握二叉树的二叉链表存储结构，掌握二叉树的创建算法、遍历算法的递归与非递归实现，并能在遍历算法基础上实现较复杂算法设计。二、实验题目与要求1.每位同学按下述要现相应算法：以二叉链表为存储结构，实现二叉树的创建、遍历算法1）问题描述：在主程序中提供下列菜单： 1建立树2前序遍历树3中序（非递归）遍历树4后序遍历树0结束2）实验要求：定义下列过程：CreateTree（）:按从键盘输入的前序序列，创建树PreOrderTree（）:前序遍历树（递归） InOrderTree（）:中序（非递归）遍历树 LaOrderTree（）:后序遍历树（递归）每位冋学在实验过程中要单步运行程序，跟踪二叉树的创建过程与前序遍历的递归过程。3）注意问题： 注意理解递归算法的执行步骤。 注意子符类型数据在输入时的处理。重点理解如何利用栈结构实现非递归算2. 编写算法交换二叉树中所有结点的左、右子树1）问题描述：编写一算法，交换二叉树中所有结点的左、右子树2）实验要求：以二叉链表作为存储结构3. 试编写按层次顺序遍历二叉树的算法1）问题描述：编写按层次顺序遍历二叉树的算法2）实验要求：以二叉链表作为存储结构4. 编写算法求二叉树高度及宽度。1） 问题描述：二叉树高度是指树中所有节点的最大层数，二叉树宽度是指在二叉树的各层上, 有节点数最多的那一层上的节点总数。2）实验要求：以二叉链表作为存储结构三、实验过程与实验结果应包括如下主要容：? 数据结构定义二叉树是个节点的有限集合，该集合或者为空，或者由一个根节点及两个分别称为左子树和 右子树的互不相交的二叉树组成。当集合为空时，称该二叉树为空二叉树。算法设计思路简介1、利用递归算法前序建立二叉树，并完成二叉树的前序、中序和后序遍历。其中前序遍历 和后序遍历均用递归算法，中序遍历借助栈的机制，实现非递归遍历。2、在前序遍历的过程中利用中间变量交换左右子树。3、利用队列。当上一层中的数据全部出队（遍历）完毕再遍历本层节点。4、高度：获取所有节点到根节点的最长路径。宽度：在层次遍历的基础上，返回最多节点 的层的节点数。算法描述：可以用自然语言、伪代码或流程图等方式1、创建树：（1 ）声明节点（2）输入当前节点，若输入为 #则当前节点为空，否则为当前节点申请空间。（3） 将输入的值赋给当前节点的 data域，并前序建立当前节点的左子树和右子树。（4 ）返回当前节点。前序遍历树：（1）若当前节点为空则返回上一级函数，否则打印当前节点。 （2 ）前序遍历当前节点的左子树。（3 ）前序遍历当前节点的右子树。中序遍历树：（1 ）声明一个顺序栈，并用p指针指向当前节点。（2）若当前节点和栈不同时为空则重复进行下一步。否则程序结束（3 ）若当前节点不为空则重复进行第四步，否则执行第五步。（4） 在栈不满的情况下将当前节点入栈，并把p指针指向当前节点左子树的根节点。（5）若栈为空则执行第三步，否则执行第六步。（6） 将栈顶元素出栈，并打印栈顶元素的data，将p指向栈顶元素的右子树的根节点。 行第二步。前序遍历树:(1)若当前节点为空则返回上一级函数否则执行下一步。后序遍历当前节点的左子树。(3)后序遍历当前节点的右子树。(3)打印当前节点的data。(1)(3)若当前节点为空则返回 NULL,结束。否则执行下一步。 利用中间变量temp交换当前节点的左右子树。交换当前的点左子树根节点的左右子树。(4)交换当前节点右子树根节点的左右子树。(4)返回根节点。(1)(3)(4)利用指针temp指向根节点，并初始化一个队列。 将temp指向的当点节点入队。重复指向以下所有步骤，直到遇到break语句。用变量len记录队列中二叉树当前层的节点数。(5)(6)(7)(8)若len为0则结束整个程序，否则执行第六步。当len0 （即队列中还有前层的节点时）重复指向以下所有步骤。否则执行第三步。 将当前对头出栈，len+，打印出队元素 如果出队元素的左子树的根节点不为空则入队,len-.(9)如果出队元素的右子树的根节点不为空则入队,len-.(1)利用指针temp指向根节点，并初始化一个队列。将temp指向的当点节点入队。并声明当前层最大节点数为 重复指向以下所有步骤，直到遇到break语句。若遇到（3）返回最大节点数。break语句则结束整个程序并(4)用变量len记录队列中二叉树当前层的节点数。(5)(6)(7)(8)若len为0则结束整个程序，否则执行第六步。 当len0 （即队列中还有前层的节点时）重复七 将当前对头出栈，len+，打印出队元素 如果出队元素的左子树的根节点不为空则入队 如果出队元素的右子树的根节点不为空则入队,len-.否则执行第十步。（9）（10）当前层最大节点数等于上一层最大节点数和当前队列中的节点数中较大的一个。 执行第三步。,len-.算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等输入：ABH#FD#E#CK#G#1、输出:i V* L E#果果果继 料结给结诞 M历历万意 护遍遍遍圧 的序序序按 屈前中后请S3 C:W1Nstcm32crnd.exe2、输入：ABH#FD#E#CK#G#输出：S9 C ：W1 N D 0W S$yste m 3 2cir d. exe怕 HfKFKH： L i：CK3C中序遍历原二叉树：HBDFAEKCG中J?遍历交换之后的二叉斑：GCKEAFDRH 请按任意键继续 3、?输入：ABH#FD#E#CK#G#输出：3 C:WlNDOWSsystcm32cmdxxcW. H 曲 FXH - iiCKS iGC t 应EHFCDKG请按任意键继续.4、输入：ABH#FD#E#CK#G#输出：电匚:WVINDOASsystem32CTTid.exe算法时间复杂度分析1、0(n).2、0(n).3、0(n).4、0(n).四、收获与体会学了二叉树之后顿时感觉之前的容有多简单了。二叉树中用到很多递归算法，看起来很难懂。需要- 步一步的跟下去才能理解，但是理解还远远不够，关键是是自己能写出来属于自己的递归算法。经过长时 间的练习，我已经能写出来一些简单的递归算法了，但是稍微难一点的就写不出来了。后面的图还更难。 革命尚未成功，诸君还需努力呐。我相信经过自己不屑的练习，我会提高的！五、源代码清单1、#include #inelude #define MaxSize 100typedef char Elemtype;typedef struct BitNodeElemtype data;struct BitNode *lchild;struct BitNode *rchild;BitNode;BitNode *CreateTree()char ch;BitNode *T;scanf( %c,&ch);if (ch = # ) T = NULL;else if (!(T = (BitNode*)malloc( sizeof (BitNode)exit(1);T-data = ch;T-lchild = CreateTree();T-rchild = CreateTree(); return T;void PreOrder(BitNode *T)if (T = NULL) return ; printf( %c,T-data);PreOrder(T-lchild);PreOrder(T-rchild);void PostOrder(BitNode *T)if (T = NULL) return ;PostOrder(T-lchild);PostOrder(T-rchild);printf( %c,T-data);void InOrder(BitNode *T)BitNode *p,*q;BitNode *StackMaxSize;int top = 0;p = T;while (!(p = NULL & top = 0)while (p != NULL)if (top lchild;if (top rchild;int main()BitNode *root;root = CreateTree(); printf(前序遍历结果);PreOrder(root);printf( n);printf(中序遍历结果);InO rder(root);printf( n);printf(后序遍历结果”);PostOrder(root);printf( n);return 0;2、#include #include typedef char Elemtype;typedef struct BitTreeElemtype data;struct BitTree *lchild;struct BitTree *rchild;BitTree;BitTree *CreateTree()char ch;BitTree *T;scanf( %c,&ch);if (ch = # ) T = NULL;else T = (BitTree*)malloc( sizeof (BitTree);T-data = ch;T-lchild = CreateTree();T-rchild = CreateTree();return T;void InOrder(BitTree *T)if (T = NULL) returnInO rder(T-lchild);InO rder(T-rchild);BitTree *Excha nge(BitTree *T) BitTree *temp;if (T = NULL) return NULL;temp = T-lchild;T-lchild = T-rchild;T-rchild = temp;Excha nge(T-lchild);Excha nge(T-rchild); return T;int main()BitTree *root;root = CreateTree();printf(中序遍历原二叉树：);InO rder(root);root = Excha nge(root);printf( n中序遍历交换后的二叉树：);InO rder(root);return 0;3、#include #inelude #define MaxSize 100 typedef char Elemtype; typedef struct BitTreeElemtype data;struct BitTree *lchild; struct BitTree *rchild;BitTree;typedef BitTree Elementtype; typedef struct QueueNode Eleme nttype *base;int front;int rear;QueueNode;BitTree *CreateTree()char ch;BitTree *T;scanf( %c,&ch);if (ch = # ) T = NULL;else T = (BitTree*)malloc( sizeof (BitTree);T-data = ch;T-lchild = CreateTree();T-rchild = CreateTree();return T;/*以上为树*/QueueNode *ln itQueue() QueueNode *Q;Q = (QueueNode*)malloc( sizeof (QueueNode);Q-base = (Elementtype*)malloc(MaxSize* sizeof (Elementtype);Q-rear = Q-fro nt = 0;return Q;int QueueFull(QueueNode *Q)if (Q-rear+1) % MaxSize = Q-front) return 1;else return 0;int QueueEmpty(QueueNode *Q)if (Q-rear = Q-front)return 1;else return 0;QueueNode *Push(QueueNode *Q,Eleme nttype *ele)if (QueueFull(Q)printf(队列已满，无法入队！); else *(Q-base + Q-rear) = *ele;Q-rear = (Q-rea 叶1) % MaxSize;return Q;QueueNode *Pop(QueueNode *Q,Eleme nttype *ele)if (QueueEmpty(Q)printf(队列为空，无法出队); else *ele = *(Q-base+Q-fro nt);Q-fro nt = (Q-fro nt+1) % MaxSize;return Q;void display(BitTree *T)if (T = NULL) return ;Eleme nttype elem;BitTree *temp;temp = T;QueueNode *queue;queue = In itQueue();queue = Push(queue,temp);doqueue = Pop(queue，& elem);temp = & elem;printf( %c ,temp-data);if (temp-lchild != NULL)queue = Push(queue,temp-lchild);if (temp-rchild != NULL)queue = Push(queue,temp-rchild);while (!QueueEmpty(queue);/*以上为队列*/int main()BitTree *root;root = CreateTree(); display(root);return 0;4、#include #include #define MaxSize 100 typedef char Elemtype; typedef struct BitTreeElemtype data;struct BitTree *lchild; struct BitTree *rchild;BitTree;typedef BitTree Elementtype; typedef struct QueueNodeEleme nttype *base;int front;int rear;QueueNode;BitTree *CreateTree()char ch;BitTree *T;scanf( %c,&ch);if (ch = # ) T = NULL;else T = (BitTree*)malloc( sizeof (BitTree);T-data = ch;T-lchild = CreateTree();T-rchild = CreateTree();return T;/*以上为树*/QueueNode *lni tQueue()QueueNode *Q;Q = (QueueNode*)malloc( sizeof (QueueNode);Q-base = (Elementtype*)malloc(MaxSize* sizeof (Elementtype);Q-rear = Q-fro nt = 0;return Q;int QueueFull(QueueNode *Q)if (Q-rear+1) % MaxSize = Q-front)return 1;else return 0;int QueueEmpty(QueueNode *Q)if (Q-rear = Q-front) return 1;else return 0;int GetLength(QueueNode *Q)int i = Q-front;int j = 1;while (i != Q-rear)i = (i+1)%MaxSize;j+;return (j-1);QueueNode *Push(QueueNode *Q,Eleme nttype *ele)if (QueueFull(Q)printf(队列已满，无法入队！); else *(Q-base + Q-rear) = *ele;Q-rear = (Q-rea 叶1) % MaxSize;return Q;QueueNode *Pop(QueueNode *Q,Eleme nttype *ele)if (QueueEmpty(Q)printf(队列为空，无法出队！); else *ele = *(Q-base+Q-fro nt);Q-fro nt = (Q-fro nt+1) % MaxSize;return Q;int GetHeight(BitTree *T)if (T = NULL) return 0;else int LeftHeight = GetHeight(T-lchild);int RightHeight = GetHeight(T-rchild);return LeftHeight RightHeight ? (LeftHeight+1) : (RightHeight+1);int GetWidth(BitTree *T)if (T = NULL) return 0;int MaxWidth = 0;Eleme nttype elem;BitTree *temp;QueueNode *queue; queue = In itQueue(); queue = Push(queue,T);while (1)int len 二 GetLength(queue);if (len = 0)break;while (len 0)queue = Pop(queue，& elem);len-;temp = & elem;if (temp-lchild != NULL)queue = Push(queue,temp-lchild);if (temp-rchild != NULL)queue = Push(queue,temp-rchild);GetLe ngth(queue);MaxWidth = MaxWidth GetLength(queue) ? MaxWidth :return MaxWidth;/*以上为队列*/int main()BitTree *root;root = CreateTree();printf( %d %d,GetHeight(root),GetWidth(root);return 0;实用文档实用文档实用文档