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

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

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