实验三：二叉树操作(16页).doc

《实验三：二叉树操作(16页).doc》由会员分享，可在线阅读，更多相关《实验三：二叉树操作(16页).doc（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-实验三：二叉树操作-第 16 页实验报告学院（系）名称：计算机与通信工程学院姓名* *学号* *专业计算机科学与技术班级2015级*班实验项目实验三：二叉树操作 课程名称数据结构与算法课程代码0661013实验时间年 月 日第节实验地点7-*考核标准实验过程25分程序运行20分回答问题15分实验报告30分特色功能5分考勤违纪情况5分成绩成绩栏其它批改意见: 教师签字：考核内容评价在实验课堂中的表现，包括实验态度、编写程序过程等内容等。功能完善, 功能不全有小错无法运行正确基本正确有提示无法回答完整较完整一般内容极少无报告有无有无 一、实验目的理解二叉树的逻辑特点和二叉树的性质；掌握二叉树的二

2、叉链表存储结构，掌握二叉树 的创建算法、遍历算法的递归与非递归实现，并能在遍历算法基础上实现较复杂算法设计。二、实验题目与要求1.每位同学按下述要求实现相应算法：以二叉链表为存储结构，实现二叉树的创建、遍历算法 1）问题描述：在主程序中提供下列菜单： 1建立树 2前序遍历树 3中序(非递归)遍历树 4后序遍历树 0结束 2）实验要求： 定义下列过程： CreateTree(): 按从键盘输入的前序序列，创建树 PreOrderTree()：前序遍历树（递归） InOrderTree()：中序(非递归)遍历树 LaOrderTree(): 后序遍历树（递归） 每位同学在实验过程中要单步运行程序，

3、跟踪二叉树的创建过程与前序遍历的递归过程。 3）注意问题: 注意理解递归算法的执行步骤。 注意字符类型数据在输入时的处理。 重点理解如何利用栈结构实现非递归算2. 编写算法交换二叉树中所有结点的左、右子树 1）问题描述：编写一算法，交换二叉树中所有结点的左、右子树 2）实验要求：以二叉链表作为存储结构3. 试编写按层次顺序遍历二叉树的算法 1）问题描述：编写按层次顺序遍历二叉树的算法 2）实验要求：以二叉链表作为存储结构4. 编写算法求二叉树高度及宽度。 1） 问题描述：二叉树高度是指树中所有节点的最大层数，二叉树宽度是指在二叉树的各层上， 具有节点数最多的那一层上的节点总数。 2） 实验要求

4、：以二叉链表作为存储结构三、实验过程与实验结果 应包括如下主要内容： 数据结构定义 二叉树是个节点的有限集合，该集合或者为空，或者由一个根节点及两个分别称为左子树和右子树的互不相交的二叉树组成。当集合为空时，称该二叉树为空二叉树。 算法设计思路简介 1、利用递归算法前序建立二叉树，并完成二叉树的前序、中序和后序遍历。其中前序遍历和后序遍历均用递归算法，中序遍历借助栈的机制，实现非递归遍历。 2、在前序遍历的过程中利用中间变量交换左右子树。 3、利用队列。当上一层中的数据全部出队（遍历）完毕再遍历本层节点。 4、高度：获取所有节点到根节点的最长路径。宽度：在层次遍历的基础上，返回最多节点的层的节

5、点数。 算法描述：可以用自然语言、伪代码或流程图等方式 1、创建树： （1）声明节点 （2）输入当前节点，若输入为#则当前节点为空，否则为当前节点申请空间。 （3）将输入的值赋给当前节点的data域，并前序建立当前节点的左子树和右子树。 （4）返回当前节点。 前序遍历树： （1）若当前节点为空则返回上一级函数，否则打印当前节点。 （2）前序遍历当前节点的左子树。 （3）前序遍历当前节点的右子树。 中序遍历树： （1）声明一个顺序栈，并用p指针指向当前节点。 （2）若当前节点和栈不同时为空则重复进行下一步。否则程序结束 （3）若当前节点不为空则重复进行第四步，否则执行第五步。 （4）在栈不满的情

6、况下将当前节点入栈，并把p指针指向当前节点左子树的根节点。 （5）若栈为空则执行第三步，否则执行第六步。 （6）将栈顶元素出栈，并打印栈顶元素的data，将p指向栈顶元素的右子树的根节点。执行第二步。 前序遍历树： （1）若当前节点为空则返回上一级函数否则执行下一步。 （2）后序遍历当前节点的左子树。 （3）后序遍历当前节点的右子树。 （3）打印当前节点的data。 2、 （1）若当前节点为空则返回NULL,结束。否则执行下一步。 （2）利用中间变量temp交换当前节点的左右子树。 （3）交换当前的点左子树根节点的左右子树。 （4）交换当前节点右子树根节点的左右子树。 （4）返回根节点。 3、

7、 （1）利用指针temp指向根节点，并初始化一个队列。 （2）将temp指向的当点节点入队。 （3）重复指向以下所有步骤，直到遇到break语句。 （4）用变量len记录队列中二叉树当前层的节点数。 （5）若len为0则结束整个程序，否则执行第六步。 （6）当len0（即队列中还有前层的节点时）重复指向以下所有步骤。否则执行第三步。 （7）将当前对头出栈，len+，打印出队元素 （8）如果出队元素的左子树的根节点不为空则入队,len-. （9）如果出队元素的右子树的根节点不为空则入队,len-. 4、 （1）利用指针temp指向根节点，并初始化一个队列。 （2）将temp指向的当点节点入队。并

8、声明当前层最大节点数为0 （3）重复指向以下所有步骤，直到遇到break语句。若遇到break语句则结束整个程序并返回最大节点数。 （4）用变量len记录队列中二叉树当前层的节点数。 （5）若len为0则结束整个程序，否则执行第六步。 （6）当len0（即队列中还有前层的节点时）重复七九步。否则执行第十步。 （7）将当前对头出栈，len+，打印出队元素 （8）如果出队元素的左子树的根节点不为空则入队,len-. （9）如果出队元素的右子树的根节点不为空则入队,len-. （10）当前层最大节点数等于上一层最大节点数和当前队列中的节点数中较大的一个。 执行第三步。 算法的实现和测试结果：包括算法

9、运行时的输入、输出，实验中出现的问题及解决办法等 1、 输入：ABH#FD#E#CK#G# 输出： 2、 输入：ABH#FD#E#CK#G# 输出： 3、 输入：ABH#FD#E#CK#G# 输出： 4、 输入：ABH#FD#E#CK#G# 输出： 算法时间复杂度分析 1、O(n). 2、O(n). 3、O(n). 4、O(n).四、收获与体会学了二叉树之后顿时感觉之前的内容有多简单了。二叉树中用到很多递归算法，看起来很难懂。需要一步一步的跟下去才能理解，但是理解还远远不够，关键是是自己能写出来属于自己的递归算法。经过长时间的练习，我已经能写出来一些简单的递归算法了，但是稍微难一点的就写不出来

10、了。后面的图还更难。革命尚未成功，诸君还需努力呐。我相信经过自己不屑的练习，我会提高的！五、源代码清单1、#include#include#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*)ma

11、lloc(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

12、);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 data);p = p-rchild;int main()BitNode *root;root = CreateTree();printf(前序遍历结果);PreOrder(root);printf(n);printf(中序遍历结果);InOrder(root);printf(n);printf(后序遍历结果)

13、;PostOrder(root);printf(n);return 0;2、#include#includetypedef 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-lchi

14、ld = CreateTree();T-rchild = CreateTree();return T;void InOrder(BitTree *T)if(T = NULL) return;InOrder(T-lchild);printf(%c,T-data);InOrder(T-rchild);BitTree *Exchange(BitTree *T)BitTree *temp;if(T = NULL) return NULL;temp = T-lchild;T-lchild = T-rchild;T-rchild = temp;Exchange(T-lchild);Exchange(T-r

15、child);return T;int main()BitTree *root;root = CreateTree();printf(中序遍历原二叉树：);InOrder(root);root = Exchange(root);printf(n中序遍历交换后的二叉树：);InOrder(root);printf(n);return 0;3、#include#include#define MaxSize 100typedef char Elemtype;typedef struct BitTreeElemtype data;struct BitTree *lchild;struct BitTre

16、e *rchild;BitTree;typedef BitTree Elementtype;typedef struct QueueNodeElementtype *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

17、 T;/*以上为树*/QueueNode *InitQueue()QueueNode *Q;Q = (QueueNode*)malloc(sizeof(QueueNode);Q-base = (Elementtype*)malloc(MaxSize*sizeof(Elementtype);Q-rear = Q-front = 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

18、-front) return 1;else return 0;QueueNode *Push(QueueNode *Q,Elementtype *ele)if(QueueFull(Q)printf(队列已满，无法入队！); else *(Q-base + Q-rear) = *ele;Q-rear = (Q-rear+1) % MaxSize;return Q;QueueNode *Pop(QueueNode *Q,Elementtype *ele)if(QueueEmpty(Q)printf(队列为空，无法出队); else *ele = *(Q-base+Q-front);Q-front

19、= (Q-front+1) % MaxSize;return Q;void display(BitTree *T)if(T = NULL) return;Elementtype elem;BitTree *temp;temp = T;QueueNode *queue;queue = InitQueue();queue = Push(queue,temp);doqueue = Pop(queue,&elem);temp = &elem;printf(%c,temp-data);if(temp-lchild != NULL)queue = Push(queue,temp-lchild);if(te

20、mp-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 100typedef char Elemtype;typedef struct BitTreeElemtype data;struct BitTree *lchild;struct BitTree *rchild;BitTree;

21、typedef BitTree Elementtype;typedef struct QueueNodeElementtype *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;/*以上为树*/QueueNo

22、de *InitQueue()QueueNode *Q;Q = (QueueNode*)malloc(sizeof(QueueNode);Q-base = (Elementtype*)malloc(MaxSize*sizeof(Elementtype);Q-rear = Q-front = 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;e

23、lse 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,Elementtype *ele)if(QueueFull(Q)printf(队列已满，无法入队！); else *(Q-base + Q-rear) = *ele;Q-rear = (Q-rear+1) % MaxSize;return Q;QueueNode *Pop(QueueNode *Q,Ele

24、menttype *ele)if(QueueEmpty(Q)printf(队列为空，无法出队！); else *ele = *(Q-base+Q-front);Q-front = (Q-front+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) : (Ri

25、ghtHeight+1);int GetWidth(BitTree *T)if(T = NULL) return 0;int MaxWidth = 0;Elementtype elem;BitTree *temp;QueueNode *queue;queue = InitQueue();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);MaxWidth = MaxWidth GetLength(queue) ? MaxWidth : GetLength(queue);return MaxWidth;/*以上为队列*/int main()BitTree *root;root = CreateTree();printf(%d %d,GetHeight(root),GetWidth(root);return 0;