数据结构实验-二叉树的操作

实验二二叉树操作
（一）实验内容
二叉树的建立和遍历。

（二）实验目的
1.进一步掌握指针变量的使用。

2.掌握二叉树的结构特征以及各种存储结构的特点及使用范围。

3.掌握用指针类型描述、访问和处理二叉树的运算。

4.掌握栈或队列的使用。

（三）实验题目
本实验要求实现以下功能：
1.按前序次序建立一棵二叉树，以‘＃’表示空。

2.中序、后序遍历该二叉树，输出遍历序列。

3.求出该二叉树的深度并输出，或求出该二叉树的叶子数目并输出。

4.试以栈为辅助存储结构实现二叉树的前序非递归算法或以队列为辅
助存储结构实现二叉树的层次遍历算法。

（四）实验仪器设备
1.学生每个一台PC机
2.已安装环境。

数据结构二叉树遍历实验报告数据结构二叉树遍历实验报告一、引言本文档旨在详细介绍二叉树遍历的实验过程和结果。

二叉树是一种在计算机科学领域常用的数据结构，通过遍历二叉树可以获取树中的所有节点数据。

本实验将分别介绍前序遍历、中序遍历和后序遍历这三种常见的遍历方法。

二、实验目的本实验的目的是通过实际操作，加深对二叉树遍历方法的理解，并验证这些遍历方法的正确性和效率。

三、实验环境本实验使用的环境如下：●操作系统: Windows 10●开发工具: Visual Studio Code●编程语言: C++四、实验步骤1.创建二叉树数据结构1.1 定义二叉树节点的结构，包含数据和左右子节点指针。

1.2 创建一个二叉树类，包含插入节点、删除节点、查找节点等方法。

1.3 使用已有的数据集构建二叉树，确保树的结构合理。

2.前序遍历前序遍历是先访问根节点，然后递归地遍历左子树和右子树。

2.1 以递归方式实现前序遍历。

2.2 以迭代方式实现前序遍历。

3.中序遍历中序遍历是先遍历左子树，然后访问根节点，最后遍历右子树。

3.1 以递归方式实现中序遍历。

3.2 以迭代方式实现中序遍历。

4.后序遍历后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。

4.1 以递归方式实现后序遍历。

4.2 以迭代方式实现后序遍历。

五、实验结果1.前序遍历结果：[节点1数据] [节点2数据] [节点4数据] [节点5数据] [节点3数据]2.中序遍历结果：[节点4数据] [节点2数据] [节点5数据] [节点1数据] [节点3数据]3.后序遍历结果：[节点4数据] [节点5数据] [节点2数据] [节点3数据] [节点1数据]六、实验分析通过实验结果可以看出，不同的遍历顺序得到的节点顺序也不同。

前序遍历先访问根节点，中序遍历先遍历左子树，后序遍历先遍历右子树。

根据需要，可以选择合适的遍历方法来处理二叉树的节点数据。

七、结论本实验验证了前序遍历、中序遍历和后序遍历的正确性，并且对比了它们的不同。

华科数据结构二叉树实验报告一、实验目的本实验旨在通过实践操作，加深对数据结构中二叉树的理解，掌握二叉树的基本操作和应用。

二、实验内容1. 实现二叉树的创建和初始化。

2. 实现二叉树的插入操作。

3. 实现二叉树的删除操作。

4. 实现二叉树的查找操作。

5. 实现二叉树的遍历操作：前序遍历、中序遍历、后序遍历。

6. 实现二叉树的层次遍历。

7. 实现二叉树的销毁操作。

8. 进行实验测试，并分析实验结果。

三、实验步骤1. 创建二叉树的数据结构，包括节点的定义和指针的初始化。

2. 实现二叉树的创建和初始化函数，根据给定的数据构建二叉树。

3. 实现二叉树的插入操作函数，将新节点插入到二叉树的合适位置。

4. 实现二叉树的删除操作函数，删除指定节点，并保持二叉树的结构完整。

5. 实现二叉树的查找操作函数，根据给定的值查找对应的节点。

6. 实现二叉树的遍历操作函数，包括前序遍历、中序遍历、后序遍历。

7. 实现二叉树的层次遍历函数，按照层次顺序遍历二叉树。

8. 实现二叉树的销毁操作函数，释放二叉树的内存空间。

9. 编写测试程序，对上述函数进行测试，并分析实验结果。

四、实验结果与分析经过测试，实验结果如下：1. 创建和初始化函数能够正确构建二叉树，并初始化节点的值和指针。

2. 插入操作函数能够将新节点插入到二叉树的合适位置，并保持二叉树的结构完整。

3. 删除操作函数能够正确删除指定节点，并保持二叉树的结构完整。

4. 查找操作函数能够根据给定的值找到对应的节点。

5. 遍历操作函数能够按照指定的顺序遍历二叉树，并输出节点的值。

6. 层次遍历函数能够按照层次顺序遍历二叉树，并输出节点的值。

7. 销毁操作函数能够释放二叉树的内存空间，防止内存泄漏。

根据实验结果分析，二叉树的基本操作和应用都能够正常实现，达到了预期的效果。

五、实验总结通过本次实验，我进一步加深了对数据结构中二叉树的理解，并掌握了二叉树的基本操作和应用。

通过实践操作，我更加熟悉了二叉树的创建、插入、删除、查找和遍历等操作，同时也学会了如何进行层次遍历和销毁二叉树。

数据结构实验报告二叉树数据结构实验报告：二叉树引言：数据结构是计算机科学中的重要基础，它为我们提供了存储和组织数据的方式。

二叉树作为一种常见的数据结构，广泛应用于各个领域。

本次实验旨在通过实践，深入理解二叉树的概念、性质和操作。

一、二叉树的定义与性质1.1 定义二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树可以为空树，也可以是由根节点和左右子树组成的非空树。

1.2 基本性质（1）每个节点最多有两个子节点；（2）左子树和右子树是有顺序的，不能颠倒；（3）二叉树的子树仍然是二叉树。

二、二叉树的遍历2.1 前序遍历前序遍历是指首先访问根节点，然后按照先左后右的顺序遍历左右子树。

在实际应用中，前序遍历常用于复制一颗二叉树或创建二叉树的副本。

2.2 中序遍历中序遍历是指按照先左后根再右的顺序遍历二叉树。

中序遍历的结果是一个有序序列，因此在二叉搜索树中特别有用。

2.3 后序遍历后序遍历是指按照先左后右再根的顺序遍历二叉树。

后序遍历常用于计算二叉树的表达式或释放二叉树的内存。

三、二叉树的实现与应用3.1 二叉树的存储结构二叉树的存储可以使用链式存储或顺序存储。

链式存储使用节点指针连接各个节点，而顺序存储则使用数组来表示二叉树。

3.2 二叉树的应用（1）二叉搜索树：二叉搜索树是一种特殊的二叉树，它的左子树上的节点都小于根节点，右子树上的节点都大于根节点。

二叉搜索树常用于实现查找、插入和删除等操作。

（2）堆：堆是一种特殊的二叉树，它满足堆序性质。

堆常用于实现优先队列，如操作系统中的进程调度。

（3）哈夫曼树：哈夫曼树是一种带权路径最短的二叉树，常用于数据压缩和编码。

四、实验结果与总结通过本次实验，我成功实现了二叉树的基本操作，包括创建二叉树、遍历二叉树和查找节点等。

在实践中，我进一步理解了二叉树的定义、性质和应用。

二叉树作为一种重要的数据结构，在计算机科学中有着广泛的应用，对于提高算法效率和解决实际问题具有重要意义。

实验三二叉树的操作一、实验目的1、掌握二叉树的逻辑结构；2、掌握二叉树的二叉链表存储结构；3、掌握基于二叉链表存储的二叉树的遍历操作的实现。

二、实验内容1、采用二叉链表存储建立一棵含有n个结点的二叉树；2、前序打印该二叉树的所有叶子结点；3、统计该二叉树的结点个数；4、计算该二叉树的深度；5、交换该二叉树的所有左右子树。

三、程序实现1、二叉链表结点类型BiNode.htemplate<class T>struct BiNode{T data;BiNode<T> *lchild,*rchild;};2、二叉树的建立及操作BiTree.htemplate<class T>struct BiNode{T data;BiNode<T> *lchild,*rchild;};template <class T>class BiTree{public:BiTree( ); //构造函数，初始化一棵二叉树，其前序序列由键盘输入~BiTree(); //析构函数，释放二叉链表中各结点的存储空间BiNode<T>* Getroot(); //获得指向根结点的指针void PreOrder(BiNode<T> *root); //前序遍历二叉树void InOrder(BiNode<T> *root); //中序遍历二叉树void PostOrder(BiNode<T> *root); //后序遍历二叉树void LevelOrder(BiNode<T> *root); //层序遍历二叉树private:BiNode<T> *root; //指向根结点的头指针BiNode<T>* Creat(); //有参构造函数调用void Release(BiNode<T> *root); //析构函数调用};template<class T>BiTree<T>::BiTree(){cout<<"请按前根序输入该二叉树的各个结点(#号表示为空):\n";this->root=Creat();}template <class T>BiNode<T>* BiTree<T>::Creat(){BiNode<T> *root;T ch;cin>>ch;if (ch=='#') root = NULL;else{root = new BiNode<T>; //生成一个结点root->data=ch;root->lchild=Creat(); //递归建立左子树root->rchild=Creat(); //递归建立右子树}return root;}template<class T>BiTree<T>::~BiTree(){Release(root);}template<class T>BiNode<T>* BiTree<T>::Getroot( ){return root;}template<class T>void BiTree<T>::PreOrder(BiNode<T> *root){if(root==NULL) return;else{cout<<root->data<<" ";PreOrder(root->lchild);PreOrder(root->rchild);}}template <class T>void BiTree<T>::InOrder (BiNode<T> *root){if (root==NULL) return; //递归调用的结束条件else{InOrder(root->lchild); //中序递归遍历root的左子树cout<<root->data<<" "; //访问根结点的数据域InOrder(root->rchild); //中序递归遍历root的右子树}}template <class T>void BiTree<T>::PostOrder(BiNode<T> *root){if (root==NULL) return; //递归调用的结束条件else{PostOrder(root->lchild); //后序递归遍历root的左子树PostOrder(root->rchild); //后序递归遍历root的右子树cout<<root->data<<" "; //访问根结点的数据域}}template <class T>void BiTree<T>::LevelOrder(BiNode<T> *root){const int MaxSize = 100;int front = 0;int rear = 0; //采用顺序队列，并假定不会发生上溢BiNode<T>* Q[MaxSize];BiNode<T>* q;if (root==NULL) return;else{Q[rear++] = root;while (front != rear){q = Q[front++];cout<<q->data<<" ";if (q->lchild != NULL) Q[rear++] = q->lchild;if (q->rchild != NULL) Q[rear++] = q->rchild;}}}template<class T>void BiTree<T>::Release(BiNode<T>* root){if (root != NULL){Release(root->lchild); //释放左子树Release(root->rchild); //释放右子树delete root;}}3、主程序实现#include<iostream.h>#include "BiTree.h"int SumNode(BiNode<char> *root)//统计二叉树结点个数{int sum;if(root==NULL)return 0;else{sum=SumNode(root->lchild)+1;sum+=SumNode(root->rchild);return sum;}}void PrePrint(BiNode<char> *root)//前序打印二叉树叶子结点{if(root==NULL) return;else{if(root->lchild==NULL&&root->rchild==NULL)cout<<root->data<<' ';PrePrint(root->lchild);PrePrint(root->rchild);}}int TreeDeepth(BiNode<char> *root)//计算二叉树的深度{int deepth;if(root==NULL) return 0;else{deepth=(TreeDeepth(root->lchild)+1)>(TreeDeepth(root->rchild)+1)?(TreeDeepth(root->lchi ld)+1):(TreeDeepth(root->rchild)+1);return deepth;}}void Changechild(BiNode<char> *root)//交换二叉树的所有左右子树{BiNode<char> *temp;if(root==NULL||(root->lchild==NULL&&root->rchild==NULL)) return;else{Changechild(root->lchild);Changechild(root->rchild);if(root->lchild==NULL){root->lchild=root->rchild;root->rchild=NULL;}if(root->rchild==NULL){root->rchild=root->lchild;root->lchild=NULL;}else{temp=root->lchild;root->lchild=root->rchild;root->rchild=temp;}}}void main(){BiTree<char> Q;int deepth,sum;cout<<"Q的前序遍历为:\n";Q.PreOrder(Q.Getroot());cout<<"\nQ的中序遍历为:\n";Q.InOrder(Q.Getroot());cout<<"\nQ的后序遍历为:\n";Q.PostOrder(Q.Getroot());cout<<"\nQ的层序遍历为:\n";Q.LevelOrder(Q.Getroot());sum=SumNode(Q.Getroot());cout<<"\n结点个数为:"<<sum<<endl;deepth=TreeDeepth(Q.Getroot());cout<<"该二叉树的深度为:"<<deepth<<endl;cout<<"该二叉树叶子结点的前序打印顺序为:"<<'\n';PrePrint(Q.Getroot());cout<<"\n交换前二叉树的层序遍历为:\n";Q.LevelOrder(Q.Getroot());Changechild(Q.Getroot());cout<<"\n交换后二叉树的层序遍历为:\n";Q.LevelOrder(Q.Getroot());cout<<endl;}四、运行结果输入的二叉树结点的前根序序列为：ABDG##H##E#I##CF#J###二叉树形式为 AB CD E FG H I运行结果：五、实验心得体会通过本次实验过程，自己熟悉了二叉树的一些基本操作，掌握二叉树的逻辑结构；二叉树的二叉链表存储结构；熟悉了基于二叉链表存储的二叉树的遍历操作。

TextFile中。

(4) P：打印代码文件(Print)。

将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrin中。

(5) T：打印哈夫曼树(Tree printing)。

将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

3) 实现提示：(1) 文件CodeFile的基类型可以设为字节型。

(2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。

请用户键入一个选择功能符。

此功能执行完毕后再显示此菜单，直至某次用户选择了“E”为止。

(3) 在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。

每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。

三、实验过程与实验结果实验3-01：以二叉链表为存储结构，实现二叉树的创建、遍历数据结构定义：typedef struct BiTNode{char data;BiTNode *lchild, *rchild;}BiTNode;typedef BiTNode *BiTree;算法设计思路简介：本实验需要实现以下操作：二叉树的初始化、前中后序遍历等基本操作1.利用递归实现前后序遍历，思路简洁，仅需要调整递归体的执行顺序即可实现。

2.利用非递归实现中序遍历，需要利用栈操作，按照中序遍历规则将节点依次入栈后出栈实现。

算法描述：图1 中序遍历（非递归）实现算法的实现和测试结果（参考OJ）实验3-02：编写算法交换二叉树中所有结点的左、右子树数据结构定义：typedef struct BiTNode{char data;BiTNode *lchild, *rchild;}BiTNode;typedef BiTNode *BiTree;算法设计思路简介：本实验需要实现以下操作：二叉树的初始化、前中后序遍历等基本操作1.利用递归实现前后序遍历，思路简洁，仅需要调整递归体的执行顺序即可实现。

二叉树基本操作实验报告实验名称二叉树基本操作实验目的1.熟悉二叉树结点的结构和二叉树的基本操作；2.掌握二叉树每种操作的具体实现；3.学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法；4.在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法；5.掌握构造哈夫曼树以及哈夫曼编码的方法。

实验内容编制一个演示二叉树创建、遍历、计算等操作的程序。

问题描述用数据结构相关知识，实现二叉树的定义和操作。

该程序包括二叉树结构类型以及对二叉树操作的具体的函数定义（包括：初始化二叉树、清空二叉树、检查二叉树是否为空、遍历二叉树（先序、后序、中序、层次）、求二叉树的深度、求二叉树所有节点数）。

问题分析该实验是基于C语言和数据结构知识基础的对二叉树的基本操作的检验，无需设计复杂的算法，程序语句也相对简单。

因此，我直接按要求定义了对二叉树操作的具体函数，并于主函数中实现对应的功能调用，其中，功能选择靠switch语句实现。

实验步骤1．需求分析本演示程序用VC++编写，完成二叉树的生成、遍历、计算等基本操作。

①输入的形式和输入值的范围：以字符（其中‘#’表示虚节点）的形式输入，以创建二叉树；在输入二叉树节点前，必须先确定该序列能正确创建二叉树。

②输出的形式：在所有三种操作中都显示操作是否正确以及操作后二叉树的内容。

③程序所能达到的功能：完成二叉树的生成、遍历（包括先序、后序、中序、层次四种方式）、计算等基本操作。

④测试数据：创建操作中依次输入a,b,d,#,g,#,#,#,c,e,#,#,f,#,#生成一个二叉树。

2．概要设计1）为了实现上述程序功能，需要定义二叉树的抽象数据类型：ADT BitTree {数据对象：由一个根节点和两个互不相交的左右子树构成数据关系：结点具有相同的数据类型及层次结构基本操作：Void BinTreeInit(BitTree *T)初始条件：无操作结果：初始化一棵二叉树Void BinTreeCreat(BitTree *T)初始条件：二叉树T已存在操作结果：按先序次序创建一棵二叉树2）本程序包含7个函数：①主函数main() ②初始化二叉树函数BinTreeInit() ③建立一棵二叉树函数BinTreeCreat() ④先序遍历函数PreOrderTraverse() ⑤中序遍历函数InOrderTraverse()⑥后序遍历函数PostOrderTraverse()⑦层次遍历函数LevelOrderTraverse()⑧求二叉树深度函数Countlevel()⑨检验空树函数BinTreeEmpty()⑩求节点数函数 Countnode()函数说明#include<stdio.h>#include<stdlib.h>typedef char Datatype;typedef struct NodeType{Datatype data;struct NodeType *lchild;struct NodeType *rchild;}BiTNode;typedef BiTNode * BinTree;//初始化二叉树。

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

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

实验目的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，失败。

实验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.顺序存储七、思考讨论题或体会或对改进实验的建议通过这次实验，我掌握了二叉树的顺序存储和链式存储，体会了二叉树的存储结构的特性，掌握了二叉树的树上相关操作。

二叉树的基本操作实验报告二叉树的基本操作实验报告引言：二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点。

二叉树的基本操作包括创建、遍历、插入和删除等。

本实验旨在通过实践来深入了解二叉树的基本操作，并通过实验结果验证其正确性和有效性。

一、创建二叉树创建二叉树是二叉树操作中的第一步。

在本实验中，我们使用了递归算法来创建二叉树。

递归算法是一种重要的算法思想，通过将问题划分为更小的子问题来解决复杂的问题。

在创建二叉树时，我们首先创建根节点，然后递归地创建左子树和右子树。

二、遍历二叉树遍历二叉树是对二叉树中的每个节点进行访问的过程。

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

前序遍历先访问根节点，然后递归遍历左子树和右子树；中序遍历先递归遍历左子树，然后访问根节点，最后递归遍历右子树；后序遍历先递归遍历左子树和右子树，最后访问根节点。

三、插入节点插入节点是向二叉树中添加新节点的操作。

插入节点的过程需要遵循二叉树的特性，即左子节点的值小于父节点的值，右子节点的值大于父节点的值。

在插入节点时，我们需要找到合适的位置，将新节点插入到正确的位置上。

四、删除节点删除节点是从二叉树中移除节点的操作。

删除节点的过程相对复杂，需要考虑多种情况。

如果要删除的节点是叶子节点，直接删除即可。

如果要删除的节点只有一个子节点，将其子节点连接到父节点上。

如果要删除的节点有两个子节点，我们需要找到其后继节点或前驱节点来替代被删除的节点。

实验结果：通过实验，我们成功地实现了二叉树的基本操作。

创建二叉树的递归算法能够正确地创建出符合要求的二叉树。

遍历二叉树的算法能够按照指定的顺序遍历每个节点。

插入节点和删除节点的操作也能够正确地修改二叉树的结构。

讨论与总结：二叉树的基本操作是数据结构中的重要内容，对于理解和应用其他数据结构具有重要意义。

通过本次实验，我们深入了解了二叉树的创建、遍历、插入和删除等操作，并通过实验验证了其正确性和有效性。

二叉树操作实验报告一、实验背景二叉树是一种常用的数据结构，它由节点和连接节点的边组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。

在二叉树的操作中，常用的操作包括创建二叉树、插入节点、删除节点、查找节点、遍历等。

本次实验旨在通过对二叉树的操作，加强对二叉树数据结构的理解，并熟练掌握其操作方法。

二、实验目的1．掌握二叉树的创建方法，能够编写代码创建一个二叉树；2．了解二叉树的插入节点操作，掌握节点的插入方法；3．掌握二叉树的删除节点操作，了解节点删除的细节和方法；4．熟练掌握二叉树的查找节点操作；5．掌握二叉树的遍历方法，能够实现对二叉树的前序、中序、后序、层次遍历。

三、实验原理1．二叉树的创建方法：通过递归的方式，先创建根节点，再依次创建左子树和右子树；2．二叉树的插入节点操作：从根节点开始，根据节点值的大小关系，将待插入节点放到适当的位置；3．二叉树的删除节点操作：首先查找待删除的节点，然后根据其子节点的情况，进行相应的删除处理；4．二叉树的查找节点操作：从根节点开始遍历，根据节点值的大小关系，在左子树或右子树中继续查找，直到找到目标节点或遍历到叶子节点；5．二叉树的遍历方法：前序遍历先访问根节点，再遍历左子树和右子树；中序遍历先遍历左子树，再访问根节点和右子树；后序遍历先遍历左子树和右子树，再访问根节点；层次遍历按层次逐个访问节点。

四、实验过程1．创建二叉树：首先，定义二叉树的节点类，包含节点值和左右子节点；然后，通过递归的方式创建根节点、左子树和右子树。

2．插入节点：要插入一个节点，首先需要找到插入位置。

如果待插入节点大于当前节点的值，则插入到右子树中，否则插入到左子树中。

如果节点为空，则表示找到了插入位置。

3．删除节点：删除节点有以下几种情况：(1) 待删除节点为叶子节点：直接删除即可；(2) 待删除节点只有一个子节点：用子节点替换待删除节点的位置；(3) 待删除节点有两个子节点：找到待删除节点的后继节点（右子树的最左下角节点），用后继节点替换待删除节点的位置。

数据结构实验报告二叉树二叉树是一种重要的数据结构，广泛应用于计算机科学和算法设计中。

在本次实验中，我们通过实际编程实践，深入理解了二叉树的基本概念、性质和操作。

一、二叉树的定义和基本性质二叉树是一种特殊的树结构，每个节点最多有两个子节点。

它具有以下基本性质：1. 根节点：二叉树的顶部节点称为根节点，它没有父节点。

2. 子节点：每个节点最多有两个子节点，分别称为左子节点和右子节点。

3. 叶节点：没有子节点的节点称为叶节点。

4. 深度：从根节点到某个节点的路径长度称为该节点的深度。

5. 高度：从某个节点到其叶节点的最长路径长度称为该节点的高度。

6. 层次遍历：按照从上到下、从左到右的顺序遍历二叉树的节点。

二、二叉树的实现在本次实验中，我们使用C++语言实现了二叉树的基本操作，包括创建二叉树、插入节点、删除节点、查找节点等。

通过这些操作，我们可以方便地对二叉树进行增删改查。

三、二叉树的遍历二叉树的遍历是指按照某种顺序访问二叉树的所有节点。

常用的遍历方式有三种：前序遍历、中序遍历和后序遍历。

1. 前序遍历：先访问根节点，然后依次递归遍历左子树和右子树。

2. 中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。

3. 后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。

四、二叉树的应用二叉树在计算机科学和算法设计中有广泛的应用。

以下是一些常见的应用场景：1. 二叉搜索树：二叉搜索树是一种特殊的二叉树，它的左子树的值都小于根节点的值，右子树的值都大于根节点的值。

它可以高效地支持插入、删除和查找操作，常用于有序数据的存储和检索。

2. 堆：堆是一种特殊的二叉树，它的每个节点的值都大于（或小于）其子节点的值。

堆常用于实现优先队列等数据结构。

3. 表达式树：表达式树是一种用二叉树表示数学表达式的方法。

通过对表达式树的遍历，可以实现对数学表达式的计算。

4. 平衡树：平衡树是一种特殊的二叉树，它的左右子树的高度差不超过1。

数据结构实验报告—二叉树目录1. 引言1.1 背景1.2 目的2. 前期准备2.1 问题定义2.2 数据准备3. 算法设计3.1 插入节点3.2 删除节点3.3 查找节点3.4 遍历二叉树4. 实验过程4.1 实验环境4.2 实验步骤5. 实验结果与分析5.1 插入节点的结果 5.2 删除节点的结果 5.3 查找节点的结果5.4 遍历二叉树的结果6. 总结与讨论6.1 实验总结6.2 实验改进方向7. 结论8. 参考文献1. 引言1.1 背景介绍二叉树的概念和应用领域，以及在数据结构中的重要性。

1.2 目的明确本实验的目标，即设计一个能够实现插入、删除、查找和遍历二叉树的算法，并对其进行实验验证。

2. 前期准备2.1 问题定义对二叉树的基本操作进行定义，包括插入节点、删除节点、查找节点和遍历二叉树。

2.2 数据准备准备一组用于测试的数据集，包括插入节点、删除节点和查找节点时所需的数据。

3. 算法设计3.1 插入节点详细描述如何设计实现插入节点的算法，并分析算法的时间复杂度和空间复杂度。

3.2 删除节点详细描述如何设计实现删除节点的算法，并分析算法的时间复杂度和空间复杂度。

3.3 查找节点详细描述如何设计实现查找节点的算法，并分析算法的时间复杂度和空间复杂度。

3.4 遍历二叉树详细描述如何设计实现遍历二叉树的算法，并分析算法的时间复杂度和空间复杂度。

4. 实验过程4.1 实验环境描述实验所用的编程语言和相关工具的环境配置。

4.2 实验步骤详细描述实验的具体步骤，包括数据准备、算法实现、代码编写、实验运行和结果分析等。

5. 实验结果与分析5.1 插入节点的结果展示插入节点的实验结果，并对结果进行详细分析和讨论。

5.2 删除节点的结果展示删除节点的实验结果，并对结果进行详细分析和讨论。

5.3 查找节点的结果展示查找节点的实验结果，并对结果进行详细分析和讨论。

5.4 遍历二叉树的结果展示遍历二叉树的实验结果，并对结果进行详细分析和讨论。

实验4：二叉树的操作
【问题描述】
二叉树是一种常用的非线性数据结构。

设计一个程序，实现对二叉树的创建、遍历、计算等操作。

【实验目的】
递归过程是如何执行的？递归程序该如何编写？――这一直是困惑学生的问题。

通过对二叉树操作的练习，使学生增加对递归过程的感性认识，从而帮助他们理解递归方法，提高编写递归程序的能力。

【基本要求】
(1)创建二叉树
(2)实现对二叉树的先序、中序、后序和按层次遍历
(3)实现对二叉数的各种运算，如结点总数、叶子数、深度、宽度等
(4)实现二叉树的其他操作，如找已知结点的双亲、孩子、兄弟、祖先，复制二叉树等
【实现提示】
(1) 二叉树用二叉链表表示：
BiTNode{
Bitypedef
struct
ElemType data;
*rchild;
struct
BiTNode *lchild,
BiTNode,
*BiTree;
}
(2)创建二叉树可以通过输入能够唯一定义一棵二叉树的序列，如：扩展二叉树的先序序列、
扩展二叉树的后序序列、二叉树的先序序列和中序序列、二叉树的后序序列和中序序列、扩展二叉树的按层次遍历序列等
(3)可以采用多级菜单的操作界面
(4)可以创建多棵二叉树，用一个指针数组来管理这些二叉树的树根指针
【选做内容】
借助于栈，用非递归的方法实现对二叉树的遍历、运算或操作。