数据结构程序报告(平衡二叉树的操作)

一 、实验目的和要求(1)掌握树的相关概念，包括树、节点的度、树的度、分支节点、叶子节点、孩子节点、双亲节 点、树的深度、森林等定义。

(2)掌握树的表示，包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。

(3)掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义。

(4)掌握二叉树的性质。

(5)重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。

(6)重点掌握二叉树的基本运算和各种遍历算法的实现。

(7)掌握线索二叉树的概念和相关算法的实现。

(8)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码的产生方法。

(9)掌握并查集的相关概念和算法。

(10)灵活运用二叉树这种数据结构解决一些综合应用问题。

二、实验内容注：二叉树b 为如图7-123所示的一棵二叉树图7-123+实验7.1 编写一个程序algo7-1.cpp,实现二叉树的各种运算，并在此基础上设计一个程序exp7-1.cpp 完成如下功能：(1)输出二叉树b ;(2)输出H 节点的左、右孩子节点值； (3)输出二叉树b 的深度； (4)输出二叉树b 的宽度； (5)输出二叉树b 的节点个数；(6)输出二叉树b 的叶子节点个数。

实验7.2设计一个程序exp7-2.cpp,实现二叉树的先序遍历、中序遍历和后序遍历和非递归算法， 以及层次变量里的算法。

并对图7-123所示的二叉树b 给出求解结果。

b+ACF GIKL+NM+E+HdJD₄B臣1607-1.CPPif(b?-HULL)re3P4+;Qu[rear]-p-b;Qu[rear].1no=1;while(reart=front){Front++;b=Qu[front]-P;lnum-Qu[front].1no;if(b->Ichildt=NULL)rpar+t;Qu[rear]-p=b->1child;Qu[rear].Ino-lnun+1;if(D->rch11d?=NULL)1/根结点指针入队//根结点的层次编号为1 1/队列不为空1/队头出队1/左孩子入队1/右孩子入队redr+t;qu[rear]-p=b->rchild;Qu[rear].1no-lnun*1;}}nax-0;lnun-1;i-1;uhile(i<=rear){n=0;whdle(i<=rear ge Qu[1].1no==1num)n+t;it+;Inun-Qu[i].1n0;if(n>max)nax=n;}return max;田1607-1.CPPreturn max;}elsereturn o;口×int Modes(BTNode *D) //求二叉树D的结点个数int nun1,nun2;if(b==NULL)returng,else if(b->ichild==NULL&D->rchild==NULL)return 1;else{num1-Hodes(b->Ichild);num2=Nodes(b->rchild);return(num1+nun2+1);LeafNodes(BINode *D) //求二叉树p的叶子结点个数int num1,num2;1f(D==NULL)return 0;else if(b->1chi1d==NULLc& b->rch11d==NULL)return 1;else{num1-LeafModes(b->lchild);num2=LeafNodes(b->rchild);return(nun1+nun2);int程序执行结果如下：xCProrn FlslirosfViu l SudiollyPrjecslro7 LJebuglFoj7 ex<1)输出二叉树：A<B<D,E<H<J,K<L,M<,N>>>>),C<F,G<,I>>)<2)'H’结点：左孩子为J石孩子为K(3)二叉树b的深度：7<4)二叉树b的宽度：4(5)二叉树b的结点个数：14(6)二叉树b的叶子结点个数：6<?>释放二叉树bPress any key to continue实验7 . 2程序exp7-2.cpp设计如下：坠eTPT-2.EPP#include<stdio.h》winclude<malloc.h>deFn Masie 00typde chr ElemTyetypede sruct nde{ElemType data;stuc node *lclldstruct node rchild;》BTHode;extern vod reaeBNodeBTNode extrn void DispBTHode(BTNodeuoid ProrderBTNode *b)if(b?-NULL)- 回1 / 数据元素1 / 指向左孩子1 / 指向右孩子*eb car *str)xb1 / 先序遍历的递归算法1 / 访问根结点/ / 递归访问左子树1 7 递归访问右子树/ / 根结点入栈//栈不为空时循环/ / 退栈并访问该结点/ / 右孩子入栈{》v oidprintf(*c“,b->data); Preorder(b->lchild); Pre0rder(b->rchild);Preorder1(BTNode *b)BTNode xSt[Maxsize],*p;int top=-1;if(b!-HULL)top++;St[top]-b;uhle (op>-)p-St[top];top--;printf("%c“,p->data);if(p->rchild?-HULL)A约e程p7-2.CPPprintF(”后序逅历序列：\n");printf(" 递归算法=");Postorder(b);printf("\n");printf(“非递归算法：“);Postorder1(b);printf("\n");序执行结果如下：xCAPrograFleicsoftVisal SudlyrjecsProj 2Debuzlroj72ex"二叉树b:A(B(D,ECH<J,K(L,M<,N)>))),C(F,GC.I>))层次遍历序列：A B C D E F G H I J K L M N先序遍历序列：递归算法：A B D E H J K L M N C F G I非归算法：A B D E H J K L M N C F G I中序遍历序列：递归算法： D B J H L K M N E A F C G I非递归算法：D B J H L K M N E A F C G I后序遍历序列：递归算法： D J L N M K H E B F I G C A非递归算法：D J L N H K H E B F I G C APress any key to continue臼p7-3.CPP15Pp a t h[p a t h l e n]-b->d a t a;//将当前结点放入路径中p a t h l e n t+;/7路任长度培1Al1Path1(b->ichild,patn,pathlen);1/递归扫描左子树Al1Path1(b->rchild,path,pathlen); //递归扫描右子树pathlen-- ; //恢复环境uoid Longpath(BTNode *b,Elemtype path[1,int pathlen,Elemtype longpath[],int elongpatnien) int i;1f(b==NULL){if(pathlen>longpatnlen) //若当前路径更长，将路径保存在1ongpatn中for(i-pathlen-1;i>-8;i--)longpath[i]=path[1];longpathlen-pathlen;elsepath[pathlen]=b->data; pathlen4; //将当前结点放入路径中//路径长度增1iongPath(b->lchild,path₇pathlen,langpath,longpathien);//递归扫描左子树LongPath(b->rchiid,path,pathien,longpath,longpathien);//递归扫描石子树pathlen--; /7饮其环境oid DispLeaf(BTNode xb)- 口凶uoid DispLeaf(BTNode xb)iE(D!=NULL){ if(b->1child--HULL B& b->rchild--HULL)printf("3c“,b->data);elsepispLeaf(b->ichild);DispLeaf(b->rchild);oid nain()8TNodexb;ElenType patn[Maxsize],longpath[Maxsize];int i.longpathien-U;CreateBTNode(b,"A(B(D,E(H(J,K(L,H(,N))))),C(F,G(,I)))");printf("\n二灾树b:");DispBTNode(b);printf("\n\n*);printf(”b的叶子结点：");DispLeaf(b);printf("\n\n");printf("A11Path:");A11Path(b);printf("m");printf("AiiPath1:n");AliPath1(b.path.);printf("");LongPath(b,path,8,longpath,longpathlen);printf(”第一条量长路径长度=d\n”,longpathlen);printf(”"第一茶最长路径：");for(i=longpathlen;i>=0;i--)printf("c",longpatn[1]);printf("\n\n");。

数据结构程序报告数据结构，是计算机科学中一门研究各种数据的存储方式、组织方式和管理方式的学科，是计算机科学的基础课程之一、平衡二叉树，是数据结构中的一种重要的树结构，其能够在插入和删除的过程中自动保持其左右子树高度的平衡。

本文将对平衡二叉树的操作进行详细介绍。

首先，平衡二叉树的特点是每个节点的左右子树的高度差不超过1、这样一来，平衡二叉树的查找、插入和删除的时间复杂度均能保持在O(logn)的级别，使得其在大规模数据处理中具有较高的效率。

为了保持平衡，我们需要对插入和删除操作进行一系列的旋转操作。

平衡二叉树的插入操作分为两个步骤：首先进行二叉查找树的插入操作，然后对每个经过的节点检查其平衡因子，如果平衡因子超过了1或-1，则需要进行相应的旋转操作。

常用的旋转操作有左旋和右旋。

左旋是指以一些节点为支点，使其右子树成为新的支点，原支点成为新支点的左子树。

右旋与左旋的操作类似，只是方向相反。

通过旋转操作，可以让插入后的平衡二叉树保持平衡。

平衡二叉树的删除操作分为三个步骤：首先进行二叉查找树的删除操作，然后对每个经过的节点检查其平衡因子，如果平衡因子超过了1或-1，则需要进行相应的旋转操作；最后，检查删除节点的父节点是否平衡，如果不平衡，则需要进行旋转操作。

删除操作涉及到对树的旋转和重新平衡的过程，操作较为复杂。

平衡二叉树的查询操作与普通的二叉查找树类似，通过比较节点的值大小来确定当前节点的位置，进而进行查找。

由于平衡二叉树的平衡性，查询的时间复杂度能够保持在O(logn)的级别。

总结来说，平衡二叉树是一种能够在插入和删除过程中自动保持平衡的树结构。

通过旋转操作和调整平衡因子，可以在一定程度上减少二叉树的高度，提高插入、删除和查询的效率。

但是，由于平衡二叉树的调整过程较为繁琐，实际应用中一般采用平衡二叉树的变种，如AVL树、红黑树等。

在实际应用中，平衡二叉树的操作是数据结构领域的一个关键问题，对于构建高效的数据存储和处理系统具有重要意义。

平衡二叉树操作演示.数据结构实习报告题目：平衡二叉树的操作演示班级：信息管理与信息系统11-平衡二叉树的操作演示班级：信息管理与信息系统11：崔佳学号：201101050903完成日期：2013.06.25一、需求分析1. 初始，平衡二叉树为空树，操作界面给出两棵平衡二叉树的显示、查找、插入、删除、销毁、合并两棵树，几种选择。

其中查找、插入和删除操作均要提示用户输入关键字。

每次插入或删除一个节点后都会更新平衡二叉树的显示。

2. 平衡二叉树的显示采用凹入表形式。

3.每次操作完毕后都会给出相应的操作结果，并进入下一次操作，知道用户选择退出二、概要设计1.平衡二叉树的抽象数据类型定义：ADT BalancedBinaryTree{ 数据对象D：D是具有相同特性的数据元素的集合。

各个数据元素均含有类型相同，可唯一标志的数据元素的关键字。

数据关系R：数据元素同属一个集合。

基本操作P：InitA VL(BSTree T) 操作结果：构造一个空的平衡二叉树T DestroyA VL(BSTree T) 初始条件：平衡二叉树T存在操作结果：销毁平衡二叉树T SearchA VL(BSTree T,int key) 初始条件：平衡二叉树T存在，key为和关键字相同类型的给定值操作结果：若T中存在关键字和key相等的数据元素，则返回指向该元素的指针，否则为空InsertA VL(BSTree T,int key,Status taller) 初始条件：平衡二叉树T存在，key和关键字的类型相同操作结果：若T中存在关键字等于key的数据元素则返回，若不存在则插入一个关键字为key的元素DeleteA VL(BSTree T,int key,Status lower) 初始条件：平衡二叉树T存在，key和关键字的类型相同操作结果：若T中存在关键字和key相同的数据元素则删除它}ADT BalancedBinaryTree2.本程序包含二个模块1）主程序模块：void main（）{ 接收命令；While(“命令”！＝“退出”){ 处理命令；清屏并得新打印提示信息；接收下一条命令；}}2）平衡二叉树基本操作实现平衡二叉树的抽象数据类型的各函数原型。

[精品]【数据结构】二叉树实验报告二叉树实验报告一、实验目的：1.掌握二叉树的基本操作；2.理解二叉树的性质；3.熟悉二叉树的广度优先遍历和深度优先遍历算法。

二、实验原理：1.二叉树是一种树形结构，由n(n>=0)个节点组成；2.每个节点最多有两个子节点，称为左子节点和右子节点；3.二叉树的遍历分为四种方式：前序遍历、中序遍历、后序遍历和层次遍历。

三、实验环境：1.编程语言：C++；2.编译器：Dev-C++。

四、实验内容：1.定义二叉树节点结构体：struct BinaryTreeNode{int data; // 节点数据BinaryTreeNode *leftChild; // 左子节点指针BinaryTreeNode *rightChild; // 右子节点指针};2.初始化二叉树：queue<BinaryTreeNode *> q; // 使用队列存储节点q.push(root);int i = 1; // 创建子节点while (!q.empty() && i < length){BinaryTreeNode *node = q.front();q.pop();if (data[i] != -1) // 创建左子节点 {BinaryTreeNode *leftChild = new BinaryTreeNode;leftChild->data = data[i];leftChild->leftChild = nullptr;leftChild->rightChild = nullptr;node->leftChild = leftChild;q.push(leftChild);}i++;if (data[i] != -1) // 创建右子节点 {BinaryTreeNode *rightChild = new BinaryTreeNode;rightChild->data = data[i];rightChild->leftChild = nullptr;rightChild->rightChild = nullptr;node->rightChild = rightChild;q.push(rightChild);}i++;}return root;}3.前序遍历二叉树：五、实验结果：输入：int data[] = {1, 2, 3, 4, -1, -1, 5, 6, -1, -1, 7, 8};输出：前序遍历结果：1 2 4 5 3 6 7 8中序遍历结果：4 2 5 1 6 3 7 8后序遍历结果：4 5 2 6 8 7 3 1层次遍历结果：1 2 3 4 5 6 7 8通过本次实验，我深入理解了二叉树的性质和遍历方式，并掌握了二叉树的基本操作。

数据结构二叉树的实验报告数据结构二叉树的实验报告一、引言数据结构是计算机科学中非常重要的一个领域，它研究如何组织和存储数据以便高效地访问和操作。

二叉树是数据结构中常见且重要的一种，它具有良好的灵活性和高效性，被广泛应用于各种领域。

本实验旨在通过实际操作和观察，深入了解二叉树的特性和应用。

二、实验目的1. 理解二叉树的基本概念和特性；2. 掌握二叉树的创建、遍历和查找等基本操作；3. 通过实验验证二叉树的性能和效果。

三、实验过程1. 二叉树的创建在实验中，我们首先需要创建一个二叉树。

通过输入一系列数据，我们可以按照特定的规则构建一棵二叉树。

例如，可以按照从小到大或从大到小的顺序将数据插入到二叉树中，以保证树的有序性。

2. 二叉树的遍历二叉树的遍历是指按照一定的次序访问二叉树中的所有节点。

常见的遍历方式有前序遍历、中序遍历和后序遍历。

前序遍历是先访问根节点，然后再依次遍历左子树和右子树；中序遍历是先遍历左子树，然后访问根节点，最后再遍历右子树；后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。

3. 二叉树的查找二叉树的查找是指在二叉树中寻找指定的节点。

常见的查找方式有深度优先搜索和广度优先搜索。

深度优先搜索是从根节点开始，沿着左子树一直向下搜索，直到找到目标节点或者到达叶子节点；广度优先搜索是从根节点开始，逐层遍历二叉树，直到找到目标节点或者遍历完所有节点。

四、实验结果通过实验，我们可以观察到二叉树的特性和性能。

在创建二叉树时，如果按照有序的方式插入数据，可以得到一棵平衡二叉树，其查找效率较高。

而如果按照无序的方式插入数据，可能得到一棵不平衡的二叉树，其查找效率较低。

在遍历二叉树时，不同的遍历方式会得到不同的结果。

前序遍历可以用于复制一棵二叉树，中序遍历可以用于对二叉树进行排序，后序遍历可以用于释放二叉树的内存。

在查找二叉树时，深度优先搜索和广度优先搜索各有优劣。

深度优先搜索在空间复杂度上较低，但可能会陷入死循环；广度优先搜索在时间复杂度上较低，但需要较大的空间开销。

数据结构实验报告—二叉树数据结构实验报告—二叉树引言二叉树是一种常用的数据结构，它由节点和边构成，每个节点最多有两个子节点。

在本次实验中，我们将对二叉树的基本结构和基本操作进行实现和测试，并深入了解它的特性和应用。

实验目的1. 掌握二叉树的基本概念和特性2. 熟练掌握二叉树的基本操作，包括创建、遍历和查找等3. 了解二叉树在实际应用中的使用场景实验内容1. 二叉树的定义和存储结构：我们将首先学习二叉树的定义，并实现二叉树的存储结构，包括节点的定义和节点指针的表示方法。

2. 二叉树的创建和初始化：我们将实现二叉树的创建和初始化操作，以便后续操作和测试使用。

3. 二叉树的遍历：我们将实现二叉树的前序、中序和后序遍历算法，并测试其正确性和效率。

4. 二叉树的查找：我们将实现二叉树的查找操作，包括查找节点和查找最大值、最小值等。

5. 二叉树的应用：我们将探讨二叉树在实际应用中的使用场景，如哈夫曼编码、二叉搜索树等。

二叉树的定义和存储结构二叉树是一种特殊的树形结构，它的每个节点最多有两个子节点。

节点被表示为一个由数据和指向其左右子节点的指针组成的结构。

二叉树可以分为三类：满二叉树、完全二叉树和非完全二叉树。

二叉树可以用链式存储结构或顺序存储结构表示。

- 链式存储结构：采用节点定义和指针表示法，通过将节点起来形成一个树状结构来表示二叉树。

- 顺序存储结构：采用数组存储节点信息，通过计算节点在数组中的位置来进行访问和操作。

二叉树的创建和初始化二叉树的创建和初始化是二叉树操作中的基础部分。

我们可以通过手动输入或读取外部文件中的数据来创建二叉树。

对于链式存储结构，我们需要自定义节点和指针，并通过节点的方式来构建二叉树。

对于顺序存储结构，我们需要定义数组和索引，通过索引计算来定位节点的位置。

一般来说，初始化一个二叉树可以使用以下步骤：1. 创建树根节点，并赋初值。

2. 创建子节点，并到父节点。

3. 重复步骤2，直到创建完整个二叉树。

《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。

问题分析：二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。

由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。

处理本问题，我觉得应该：1、建立二叉树；2、通过递归方法来遍历（先序、中序和后序）二叉树；3、通过队列应用来实现对二叉树的层次遍历；4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等；5、运用广义表对二叉树进行广义表形式的打印。

算法规定：输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。

输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。

对二叉树的一些运算结果以整型输出。

程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。

计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。

对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。

测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E预测结果：先序遍历ABCDEGF中序遍历CBEGDFA后序遍历CGEFDBA层次遍历ABCDEFG广义表打印A（B（C,D（E（,G）,F）））叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2查找5，成功，查找的元素为E删除E后，以广义表形式打印A（B（C,D（,F）））输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B预测结果：先序遍历ABDEHCFG中序遍历DBHEAGFC后序遍历DHEBGFCA层次遍历ABCDEFHG广义表打印A（B(D,E(H)),C(F(,G))）叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3查找10，失败。

数据结构二叉树实验报告总结一、实验目的本次实验的主要目的是通过对二叉树的学习和实践，掌握二叉树的基本概念、性质和遍历方式，加深对数据结构中树形结构的理解。

二、实验内容1. 二叉树的基本概念和性质在本次实验中，我们首先学习了二叉树的基本概念和性质。

其中，二叉树是由节点组成的有限集合，并且每个节点最多有两个子节点。

同时，我们还学习了二叉树的高度、深度、层数等概念。

2. 二叉树的遍历方式在了解了二叉树的基本概念和性质之后，我们开始学习如何遍历一个二叉树。

在本次实验中，我们主要学习了三种遍历方式：前序遍历、中序遍历和后序遍历。

其中，前序遍历指先访问节点自身再访问左右子节点；中序遍历指先访问左子节点再访问自身和右子节点；后序遍历指先访问左右子节点再访问自身。

3. 二叉搜索树除了以上内容之外，在本次实验中我们还学习了一种特殊的二叉树——二叉搜索树。

二叉搜索树是一种特殊的二叉树，它的每个节点都满足左子节点小于该节点，右子节点大于该节点的性质。

由于这个性质，二叉搜索树可以被用来进行快速查找、排序等操作。

三、实验过程1. 实现二叉树的遍历方式为了更好地理解和掌握二叉树的遍历方式，我们首先在编程环境中实现了前序遍历、中序遍历和后序遍历。

在代码编写过程中，我们需要考虑如何递归地访问每个节点，并且需要注意访问顺序。

2. 实现二叉搜索树为了更好地理解和掌握二叉搜索树的特性和操作，我们在编程环境中实现了一个简单的二叉搜索树。

在代码编写过程中，我们需要考虑如何插入新节点、删除指定节点以及查找目标节点等操作。

3. 实验结果分析通过对代码运行结果进行分析，我们可以清晰地看到每个遍历方式所得到的结果以及对应的顺序。

同时，在对二叉搜索树进行操作时，我们也可以看到不同操作所产生的不同结果。

四、实验总结通过本次实验，我们进一步加深了对二叉树的理解和掌握，学习了二叉树的遍历方式以及二叉搜索树的特性和操作。

同时，在编程实践中，我们也进一步熟悉了代码编写和调试的过程。

数据结构实验十姓名：朱彦荣学号：20132184专业：软件工程2实验题目：排序平衡二叉树完成语言：C++语言上级系统：VC++6.0日期：2014/12/16一．实验内容建立排序平衡二叉树。

二．输入与输出输入：输入一组节点，从而建立平衡排序二叉树。

输出：输出平衡二叉树的先序，中序遍历，以及每个节点的平衡因子，以便进行还原二叉树的形状，判断算法是否正确。

三．关键数据结构与核心算法关键数据结构：因为是二叉树，则要有基本的节点，左右孩子指针，因为要排序旋转，则要知道平衡因子，注意此处可以根据需要来添加双亲指针，因为运用了引用，则省去了此处。

因此数据结构为：typedef struct BSTNode{int data;//信息int bf;//平衡因子struct BSTNode *lchild,*rchild; //平衡树左右儿子指针}BSTNode,*BSTree;//平衡二叉排序树结构的定义核心算法：建立平衡排序二叉树算是算法中比较复杂的一个了，但是找到核心之后，也就只是比较复杂一些罢了，多练习一下即可。

那核心是什么呢？要回答这个问题，就要深刻理解“平衡”和“排序”两个词的含义。

顾名思义，平衡二叉树加上排序二叉树即是所要建的树。

1.平衡二叉树要求每一个节点的左子树深度减去右子树的深度的绝对值要小于1。

2.排序二叉树要求按照中序遍历该二叉树得到从小到大排序的序列。

因此在每插入一个结点的时候都要判断是否平衡，1.若平衡则按照排序二叉树的方法插入之，然后刷新平衡因子即可。

2.重要是不平衡的时候就要从最接近的不平衡的地方旋转的让它平衡，这样继续下去，不断插入就可以得到排序平衡二叉树。

下面主要解释一下旋转方法：旋转共有4种方式，其实，最核心的只有两种基本操作即是L_Rotate( )和R_Rotate( )，分别是左旋和右旋。

对于LL型，即是最先出错的节点平衡因子是2，左儿子平衡因子是1，运用一次右旋操作再刷新平衡因子即可。

实验5：树（二叉树）（采用二叉链表存储）一、实验项目名称二叉树及其应用二、实验目的熟悉二叉树的存储结构的特性以及二叉树的基本操作。

三、实验基本原理之前我们都是学习的线性结构，这次我们就开始学习非线性结构——树。

线性结构中结点间具有唯一前驱、唯一后继关系，而非线性结构中结点的前驱、后继的关系并不具有唯一性。

在树结构中，节点间关系是前驱唯一而后继不唯一，即结点之间是一对多的关系。

直观地看，树结构是具有分支关系的结构（其分叉、分层的特征类似于自然界中的树）。

四、主要仪器设备及耗材Window 11、Dev-C++5.11五、实验步骤1.导入库和预定义2.创建二叉树3.前序遍历4.中序遍历5.后序遍历6.总结点数7.叶子节点数8.树的深度9.树根到叶子的最长路径10.交换所有节点的左右子女11.顺序存储12.显示顺序存储13.测试函数和主函数对二叉树的每一个操作写测试函数，然后在主函数用while+switch-case的方式实现一个带菜单的简易测试程序，代码见“实验完整代码”。

实验完整代码：#include <bits/stdc++.h>using namespace std;#define MAX_TREE_SIZE 100typedef char ElemType;ElemType SqBiTree[MAX_TREE_SIZE];struct BiTNode{ElemType data;BiTNode *l,*r;}*T;void createBiTree(BiTNode *&T){ElemType e;e = getchar();if(e == '\n')return;else if(e == ' ')T = NULL;else{if(!(T = (BiTNode *)malloc(sizeof (BiTNode)))){cout << "内存分配错误!" << endl;exit(0);}T->data = e;createBiTree(T->l);createBiTree(T->r);}}void createBiTree2(BiTNode *T,int u) {if(T){SqBiTree[u] = T->data;createBiTree2(T->l,2 * u + 1);createBiTree2(T->r,2 * u + 2); }}void outputBiTree2(int n){int cnt = 0;for(int i = 0;cnt <= n;i++){cout << SqBiTree[i];if(SqBiTree[i] != ' ')cnt ++;}cout << endl;}void preOrderTraverse(BiTNode *T) {if(T){cout << T->data;preOrderTraverse(T->l);preOrderTraverse(T->r);}}void inOrderTraverse(BiTNode *T) {if(T){inOrderTraverse(T->l);cout << T->data;inOrderTraverse(T->r);}}void beOrderTraverse(BiTNode *T){if(T){beOrderTraverse(T->l);beOrderTraverse(T->r);cout << T->data;}}int sumOfVer(BiTNode *T){if(!T)return 0;return sumOfVer(T->l) + sumOfVer(T->r) + 1;}int sumOfLeaf(BiTNode *T){if(!T)return 0;if(T->l == NULL && T->r == NULL)return 1;return sumOfLeaf(T->l) + sumOfLeaf(T->r);}int depth(BiTNode *T){if(!T)return 0;return max(depth(T->l),depth(T->r)) + 1;}bool LongestPath(int dist,int dist2,vector<ElemType> &ne,BiTNode *T) {if(!T)return false;if(dist2 == dist)return true;if(LongestPath(dist,dist2 + 1,ne,T->l)){ne.push_back(T->l->data);return true;}else if(LongestPath(dist,dist2 + 1,ne,T->r)){ne.push_back(T->r->data);return true;}return false;}void swapVer(BiTNode *&T){if(T){swapVer(T->l);swapVer(T->r);BiTNode *tmp = T->l;T->l = T->r;T->r = tmp;}}//以下是测试程序void test1(){getchar();cout << "请以先序次序输入二叉树结点的值，空结点用空格表示:" << endl; createBiTree(T);cout << "二叉树创建成功!" << endl;}void test2(){cout << "二叉树的前序遍历为:" << endl;preOrderTraverse(T);cout << endl;}void test3(){cout << "二叉树的中序遍历为:" << endl;inOrderTraverse(T);cout << endl;}void test4(){cout << "二叉树的后序遍历为:" << endl;beOrderTraverse(T);cout << endl;}void test5(){cout << "二叉树的总结点数为：" << sumOfVer(T) << endl;}void test6(){cout << "二叉树的叶子结点数为：" << sumOfLeaf(T) << endl; }void test7(){cout << "二叉树的深度为：" << depth(T) << endl;}void test8(){int dist = depth(T);vector<ElemType> ne;cout << "树根到叶子的最长路径:" << endl;LongestPath(dist,1,ne,T);ne.push_back(T->data);reverse(ne.begin(),ne.end());cout << ne[0];for(int i = 1;i < ne.size();i++)cout << "->" << ne[i];cout << endl;}void test9(){swapVer(T);cout << "操作成功!" << endl;}void test10(){memset(SqBiTree,' ',sizeof SqBiTree);createBiTree2(T,0);cout << "操作成功!" << endl;}void test11(){int n = sumOfVer(T);outputBiTree2(n);}int main(){int op = 0;while(op != 12){cout << "-----------------menu--------------------" << endl;cout << "--------------1：创建二叉树--------------" << endl;cout << "--------------2：前序遍历----------------" << endl;cout << "--------------3：中序遍历----------------" << endl;cout << "--------------4：后序遍历----------------" << endl;cout << "--------------5：总结点数----------------" << endl;cout << "--------------6：叶子节点数--------------" << endl;cout << "--------------7：树的深度----------------" << endl;cout << "--------------8：树根到叶子的最长路径----" << endl;cout << "--------------9：交换所有节点左右子女----" << endl;cout << "--------------10：顺序存储---------------" << endl;cout << "--------------11：显示顺序存储-----------" << endl;cout << "--------------12：退出测试程序-----------" << endl;cout << "请输入指令编号:" << endl;if(!(cin >> op)){cin.clear();cin.ignore(INT_MAX,'\n');cout << "请输入整数!" << endl;continue;}switch(op){case 1:test1();break;case 2:test2();break;case 3:test3();break;case 4:test4();break;case 5:test5();break;case 6:test6();break;case 7:test7();break;case 8:test8();break;case 9:test9();break;case 10:test10();break;case 11:test11();break;case 12:cout << "测试结束!" << endl;break;default:cout << "请输入正确的指令编号!" << endl;}}return 0;}六、实验数据及处理结果测试用例：1.创建二叉树（二叉链表形式）2.前序遍历3.中序遍历4.后序遍历5.总结点数6.叶子结点数7.树的深度8.树根到叶子的最长路径9.交换所有左右子女10.顺序存储七、思考讨论题或体会或对改进实验的建议通过这次实验，我掌握了二叉树的顺序存储和链式存储，体会了二叉树的存储结构的特性，掌握了二叉树的树上相关操作。