数据结构实验报告二叉树

2024-11-24

数据结构实验报告二叉树（精选5篇）

1.数据结构实验报告二叉树篇一

数据结构课程设计报告

题目名称：二叉树的应用问题专业班级：计算机科学与技术

学生姓名：

学生学号：

指导教师：

一、题目要求..............................................二、需求分析..............................................三、概要设计..............................................四、详细设计..............................................五、调试分析.............................................六、心得体会.............................................一、题目要求

实现二叉树，求解若干二叉树应用问题

 实现二叉链表表示的二叉树，包括下列运算：

 建立一棵二叉树；

 按先序、中序和后序遍历二叉树；  按层次遍历；

 求一棵二叉树的高度；

 交换一棵二叉树的左右子树；

 设计一个菜单驱动程序，测试上述算法

二、需求分析

建立一棵二叉树：

int CreateBiTree(BiTree &T)按先序遍历二叉树：

void PreOrder(BiTree &T)按中序遍历二叉树：

void InOrder(BiTree &T)按后序遍历二叉树：

void PostOrder(BiTree &T)按层次遍历：

void LevelOrder(BiTree &T)求一棵二叉树的高度：

int Depth(BiTree &T)交换一棵二叉树的左右子树：int PreOrderTraverse(BiTree T)菜单驱动程序：

void menu()

三、概要设计

定义二叉树的存储结构，每个结点中设置三个域，即值域、左指针域、右指针域。要建立二叉树T的链式存储结构，即建立二叉链表。根据输入二叉树结点的形式不同，建立的方法也不同，本系统采用先序序列递归建立二叉树。

先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则：（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。

中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则：（1）中序遍历左子树；（2）访问根结点；

（3）中序遍历右子树。

后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。

层次遍历二叉树的操作选用队列的存储结构。先建立一个长度为1的队列，利用while循环，将根结点放入队首，再将队列长度加一。然后依次遍历左子树和右子树，每遍历一次，2、先序遍历二叉树：

void PreOrder(BiTree &T){ if(!T)

return;cout<data<<“ ”;PreOrder(T->left_child);PreOrder(T->right_child);}

3、中序遍历二叉树：

void InOrder(BiTree &T){ if(!T)return;InOrder(T->left_child);cout<data<<“ ”;InOrder(T->right_child);}

4、后序遍历二叉树：

void PostOrder(BiTree &T){ if(!T)return;PostOrder(T->left_child);PostOrder(T->right_child);cout<data<<“ ”;}

5、按层次遍历：

void LevelOrder(BiTree &T){ BiTree queue[100];int front,rear;if(T==NULL)return;front=-1;rear=0;queue[rear]=T;while(front!=rear){ front++;cout<data<<“ ”;if(queue[front]->left_child!=NULL){ rear++;queue[rear]=queue[front]->left_child;

cin>>a;if(a>=0||a<=7){ switch(a){ case 0:

{

cout<<“建立后的二叉树为：n”;

Output(T);

cout<

}

system(“pause”);

break;case 1:

cout<<“该树的树深为: ”<

system(“pause”);

break;case 2:

{

cout<<“该树以先序遍历输出为：n”;

PreOrder(T);

cout<

}

system(“pause”);

break;case 3:

{

cout<<“该树以中序遍历输出为:n”;

InOrder(T);

cout<

}

system(“pause”);

break;case 4:

{

cout<<“该树以后序遍历输出为：n”;

PostOrder(T);

cout<

}

system(“pause”);

break;case 5:

{

cout<<“该树的层次遍历：n”;

LevelOrder(T);

cout<

（二）详细程序代码：{ if(!T){

cout<<“空树!n”;

return;} cout<data<<“ ”;if(T->left_child)Output(T->left_child);if(T->right_child)Output(T->right_child);}

int Depth(BiTree &T){ int i,j;if(!T)return 0;i=Depth(T->left_child);j=Depth(T->right_child);return(i>j?i:j)+1;}

void PreOrder(BiTree &T){ if(!T)

return;cout<data<<“ ”;PreOrder(T->left_child);PreOrder(T->right_child);}

void InOrder(BiTree &T){ if(!T)return;InOrder(T->left_child);cout<data<<“ ”;InOrder(T->right_child);}

void PostOrder(BiTree &T){ if(!T)return;PostOrder(T->left_child);PostOrder(T->right_child);cout<data<<“ ”;}

void LevelOrder(BiTree &T)

cout<<“<<

1.二叉树树深

>>”<

cout<<“<<

2.二叉树的先序遍历

>>”<

cout<<“<<

3.二叉树的中序遍历

>>”<

cout<<“<<

4.二叉树的后序遍历

>>”<

cout<<“<<

5.二叉树的层次遍历

>>”<

cout<<“<<

6.左右孩子交换

>>”<

cout<<“<<

7.退出

>>”<

cout<<“*******************************************************************”<

void main(){

int br,a;BiTree T;br=CreateBiTree(T);

while(1){

menu();

cout<<“请输入选择的命令-->”;

cin>>a;

if(a>=0||a<=7)

{

switch(a)

{

case 0:

{

cout<<“建立后的二叉树为：n”;

Output(T);

cout<

}

system(“pause”);

break;

case 1:

cout<<“该树的树深为: ”<

system(“pause”);

break;

case 2:

{

cout<<“该树以先序遍历输出为：n”;

PreOrder(T);

cout<

}

system(“pause”);

break;

case 3:

{

cout<<“该树以中序遍历输出为:n”;

（一）先序输入二叉树：

（二）建立一棵二叉树：

1后序遍历：

（四）按层次遍历：

3中序遍历交换后的二叉树：

六、心得体会

这次数据结构课程设计我选择的题目是二叉树的应用操作，题目要求中最难的部分是二叉树的层次遍历。在实现这个要求的时候我想了很久，最后通过在CSDN上找到了解决思路，就是用队列的方式。虽然是二叉树的题目，但是和其他知识点都有很多内在的联系。经过这次的实验，我不仅在二叉树的应用操作层面上更加熟悉，对二叉树的理解更加深刻，更重要的是我认识到知识要融会贯通才是它的价值所在。我的C语言基础不是很扎实，所以在写代码的时候也遇到很大的困难。像很基础的“j?i:j”也是通过翻阅以前的书籍才找到答案。还有在编程过程中的习惯也不是很好，函数及变量的命名等细节问题，如果不加以注意的话，会对后面的编译调试造成很多不必要的麻烦。我应该在以后的学习中加强实践，这样才能更扎实地掌握所学知识点，更有效地将书本上的知识变成解决实际问题的经验。

2.数据结构实验报告二叉树篇二

二叉树是数据结构非常重要的一种非线性结构，是树型结构的一种特殊形式，在计算机处理领域有着广泛的应用。况且对二叉数的大部分操作，都是在遍历过程中实现的，在许多教材中，都指出了如何对二叉数进行遍历，但并没有对如何通过二叉数的遍历序列还原二叉数作更详尽的介绍，本文就针对如何由二叉数的遍历序列还原二叉数的算法方面进行分析研究，并在turboC中实现此算法。

一、二叉数的定义

是有限元素的集合，是另一种树型结构，它可以为空，也可以由树根结点和至多两棵子树组成，每棵子树内部又是一棵二叉数。在二叉树中，每个结点的左子数的根结点被称之为左孩子，右子树的根结点被称之为右孩子。

二、二叉树的遍历

从二叉数的定义或组成可以知道，标准二叉数包括树根和左右子数三个部分。而且二叉树是递归定义的，换句话说，二叉树的每棵子树中，也是由这三个部分组成的。所以，寻找对二叉树进行遍历的规律，实际上就是研究对这三个部分访问顺序的规律。按照数学排列组合的方法，这三个部分有六种不同的访问顺序：DLR、DRL、LDR、RDL、LRD、RLD。其中D代表树根，R代表右子树，L代表左子树。但六种不同的访问顺序又可以分为从左到右和从右到左的两组，每组有三种不同的访问顺序。两组不同的访问顺序对称的，因此，只考虑其中一组即可。

这里以从左到右的一组为例，有DLR、LDR、LRD三种访问顺序，我们以访问根结点的顺序，对它们分别命名为先根遍历、中根遍历、后根遍历。

1、先根遍历（前序遍历）

若二叉树为空，则不访问任何结点。若二叉树不为空，则其访问顺序为：

(1)访问根结点

(2)先根遍历左子树

(3)先根遍历右子树

2、中根遍历（中序遍历）

若二叉树为空，则不访问任何结点，若二叉树不为空，则其访问顺序为：

(1)中根遍历左子树

(2)访问根结点

(3)中根遍历右子树

3、后根遍历 (后序遍历)

(1) 后跟遍历左子树

(2)后跟遍历右子树

(3)访问根结点

由前序和中序遍历或者由中序和后序遍历序列，可以唯一确定一颗二叉树，而由前序和后序遍历序列不能唯一确定一棵二叉树。

三、还原二叉数的步骤与算法

1、由先序和中序遍历还原二叉树的步骤为：

画出先序遍历序列的第一个结点，即二叉树的根结点

在中序遍历序列中找到根结点，以此为界分别数出二叉树根结点的左、右子树的结点个数

依照左、右子树的结点个数由先序遍历序列的第二个结点数起，分别找出左、右子树的先序遍历序列

由左至右，对二叉树的非空子树重复以上步骤，直至所有结点全部画出

2、由先序和中序遍历还原二叉树的算法为：

3、由后序和中序遍历还原二叉树的步骤为：

画出后序遍历序列的最后一个结点即为二叉树的根结点

中序遍历序列中找到根结点，以此为界数出二叉树根结点的左子树结点个数

依照左子树的结点个数由后序遍历序列的第一个结点数起，则可分别找出左、右子树的后序遍历序列

从左至右，对二叉树的非空子树重复以上步骤，直至所有结点全部画出。

4、由后序和中序遍历还原二叉树的算法为：

结束语

在许多的教材中都只对二叉树的三种遍历给出了算法描述，却没有提到如何由遍历序列来确定二叉树，但掌握各个序列间的相互联系，学会利用二叉树的各种遍历序列特性去还原二叉树在实际应用中恰恰是不容忽视的问题，本文对如何还原二叉树的问题进行了说明，并用Turbo C语言编写并验证了相应的算法代码。

摘要：二叉树是一种常用的数据结构, 它的实际应用十分广泛。二叉树的遍历有三种方式, 分别为先序, 中序和后序, 本文针对如何由二叉树的遍历序列还原二叉树的问题, 提出了由先序遍历和中序遍历或后序遍历和中序遍历唯一确定一棵二叉树的算法, 并对这两种算法进行了分析描述, 并在turboC中得以实现。

关键词：先序遍历,中序遍历,后序遍历,还原,二叉树

参考文献

[1]严蔚敏、吴伟民:《数据结构》, 清华大学出版社, 2007年。

3.二叉树的顺序存储结构篇三

/* * 4月19日 16:44:48 * 目的:用顺序存储结构来表示二叉树 * 二叉树比较难,所以更应该同过程序来好好理解二叉树的概念，

二叉树的顺序存储结构

。 * 顺序存储是顺序储存在数组中的，以完全二叉树的形式，不存在的结点 * 在数组中用0表示。当二叉树是完全二叉树时,效率高而且简单 * 但是当不是完全二叉树时,会出现内存浪费的情况,这个程序仅仅 * 用来说明顺序结构怎么存储二叉树的,而且一般二叉树不会用顺序结构,缺点明显 */# include# define MAXSIZE 50 //设置二叉树最大结点数int treeData[MAXSIZE]; //定义一个存储结点的数组int length; //数组中除了首元素外,因为首元素表示了结点的个数,真正元素的个数,包括0;0表示二叉树不存在的结点.void init{ treeData[0] = 0; //用数组的第一个元素来表示中结点的个数 length = 0;}//判断树是否为空bool isEmpty(){ if(treeData[0] == 0) return true; else return false;}//自己创建一个二叉树void createTree(){ printf(”请根据二叉树的特点输入数据,二叉树中不存在的结点请用0表示!想要结束请输入-1“); int number = 0; //当用户输入-1表示结束 while(number != -1) { scanf(”%d“,&number); if(number!=-1) { length++; treeData[length] = number; if(number != 0)www.2cto.com treeData[0]++; //结点个数+1 } if(length+1 >= MAXSIZE) { printf(”数组越界了!“); break; //跳出循环 } }}//打印出二叉树void showTree(){ if(isEmpty()) { printf(”树中没有元素,无法显示!“); } else { for(int i = 1;i <= length;i++) { printf(”%d “,treeData[i]); if(i % 10 == 0) printf(”“); } printf(”“); }}void getpointLength(){ printf(”二叉树中结点的个数为%d“,treeData[0]);}/* 这个程序本身写的很简单 * 但是这个程序却让我知道了怎么用顺序结构来存储二叉树 * 还有用顺序结构存储一般二叉树,为什么不赞成使用这种方法 * 原因大家应该很清楚,会浪费太多内存空间了.*/int main(void){ init(); createTree(); showTree(); getpointLength(); return 0;}

4.数据结构实验报告二叉树篇四

一．需求分析

1、建立平衡二叉树并进行创建、增加、删除、调平等操作。

2、设计一个实现平衡二叉树的程序，可进行创建、增加、删除、调平等操作，实现动态的输入数据，实时的输出该树结构。

3、测试数据：自选数据

二．概要设计

平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下：

⑴ 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点；

⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；

⑶ 判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整；

⑷ 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；

⑸ 计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。

三．详细设计

树的内部变量

— 1 — typedef struct BTNode {

int data;int bf;//平衡因子 struct BTNode *lchild,*rchild;//左、右孩子

}BTNode,*BTree;调平二叉树(左右调平方式大体雷同，之具体写出其中一种调平方式)if(插入元素与当前根元素相等){ printf(“已存在相同关键字的结点n”);} if(插入元素小于当前根元素)){ if(插入新结点不成功)

return 0;if(插入成功)

switch(查看根的平衡因子)

{

case +1:

进行左平衡处理;

{

检查*T的左子树的平衡度，并作相应平衡处理

{

case +1:

令根及其左孩子的平衡因子为0;

做右平衡处理;

{

BTree lc;

lc指向的结点左子树根结点;

rc的右子树挂接为结点的左子树;

lc的右孩子为原结点;

原结点指向新的结点lc;

}

break;

case-1:

rd指向*T的左孩子的右子树根

switch(查看右孩子平衡因子)

{

case +1:

根的平衡因子为-1;

根左孩子的平衡因子为0;

break;

case 0:

令根和根左孩子的平衡因子为0;— 2 —

}

break;根平衡因子为0;根左孩子平衡因子为1;break;

case-1:

根右孩子的平衡因子为0;对*T的左子树作左旋平衡处理;对*T作右旋平衡处理;break;令根的平衡因子为+1;break;令根的平衡因子为-1;break;case 0:

case-1:

四．调试分析

在进行对插入新结点并调平时由于利用的是普通的插入方法进行LL、LR、RL、RR型的转换，使得在调试时经常没有更改内部变量的值，导致编译出错。

对于在空树情况下删除结点的考虑，是在后期的调试检验过程中发现的。在没有更改代码前，如果按此操作，程序就会崩溃。原因就是在删除函数中虽然考虑到了空树的情况，但是在输出树的函数中没有加入空树的考虑而只是在创建树函数中加入了if…else…的判断。经过反复的检查，发现可以直接在输出函数中加入判断而不必再其他位置判断，并且调试成功。

五．使用说明和测试结果

测试数据：

创建二叉树

增加二叉树

直接创建平衡二叉树

— 4 —平衡二叉树加入新节点并调平

删除结点

六．心得体会

了解了建立树的方法；

学会了利用二分法建立树结构。、；学习到了二叉树的调平方法；

学会了向一个已知树插入或删除结点的方法。