下载文档原格式
北京物资学院信息学院实验报告课程名数据结构(C++)实验实验名称二叉树算法的实现实验日期年月日实验报告日期年月日姓名______ ___ 班级_____ _______ 学号___一、实验目的1.掌握二叉树的存储的结构；2. 掌握建立二叉树的算法；3. 掌握对二叉树的遍历算法；4. 掌握二叉搜索树的算法；5. 掌握建立哈夫曼树和哈夫曼编码的算法；二、实验内容基本部分1. 采用广义表形式建立二叉树(参考图5-11(a)和/或图5-13(a))；2. 对已建立的二叉树，进行先、中、后序和按层遍历；3. 用广义表形式输出二叉树；4. 【习题5-3】1, 2 (2题选作)【提示：参考递归遍历算法】；特殊二叉树部分1．用插入算法建立一棵二叉搜索树，原始数据为：{30,50,20,40,25,70,54,23,80,92}，并中序遍历该树、查找其中的元素；2. 构造一棵叶子结点权值分别为3，5，6，7，9，13，21的哈夫曼树；3. 对2题进行哈夫曼编码。
三、实验地点与环境3.1 实验地点(南实验楼教室)3.2实验环境(所用语言环境)四、实验步骤1.2.3.…五、实验结果与分析5.1 实验结果(原始数据，预期结果和运行结果)序号算法名称(函数名) 所在头文件名原始数据与与功能主函数所在文件名运行结果*1 函数名：功能：头文件：CPP文件：原始数据：运行结果：23* 如果不能按“原始数据”、“运行结果”列出数据则不列，必要时在“分析”部分说明5.2 分析（选择部分算法分析，包括函数参数说明、调试中所遇到的问题和解决方法、中间结果等，必要时给出函数和主函数的关键段落。
所选算法应是：重要的算法、有编程特点的算法等）六、小结（收获与心得）。
实验三二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。
2、熟练掌握二叉树的各种遍历算法。
二、实验内容1、问题描述建立一棵二叉树，试编程实现二叉树的如下基本操作：(1). 按先序序列构造一棵二叉链表表示的二叉树T；(2). 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；(3). 求二叉树的深度/结点数目/叶结点数目；(选做)(4). 将二叉树每个结点的左右子树交换位置。
（选做）2、基本要求从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）。
3、测试数据如输入：abc00de0g00f000（其中ф表示空格字符）则输出结果为：先序：a->b->c->d->e->g->f中序：a->b->c->d->e->g->f后序：a->b->c->d->e->g->f三、程序代码#include<malloc.h>#include<iostream.h>#define OK 1#define ERROR -1typedef char TElemType;int i;typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;int CreateBiTree(BiTree&T) //创建二叉树{char a;cin>>a;if(a=='0') T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) {return ERROR;}T->data=a;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}return OK;}int PreOrderTraverse(BiTree&T) //先序遍历二叉树{if(T){//cout<<"此为先序遍历"<<endl;cout<<T->data<<"->";if(PreOrderTraverse(T->lchild))if(PreOrderTraverse(T->rchild))return OK;return ERROR;}else return OK;}int InOrderTraverse(BiTree&T) //中序遍历二叉树{if(T){//cout<<"此为中序遍历"<<endl;if(InOrderTraverse(T->lchild)){cout<<T->data<<"->";if(InOrderTraverse(T->rchild))return OK;}return ERROR;}else return OK;}int PostOrderTraverse(BiTree&T) //后序遍历二叉树{if(T){//cout<<"此为后序遍历"<<endl;if (PostOrderTraverse(T->lchild))if(PostOrderTraverse(T->rchild)){cout<<T->data<<"->";i++;return (OK);}return (ERROR);}elsereturn (OK);}int CountDepth(BiTree&T) //计算二叉树的深度{if(T==NULL){return 0;}else{int depl=CountDepth(T->lchild);int depr=CountDepth(T->lchild);if(depl>depr){return depl+1;}else{return depr+1;}}}void main() //主函数{BiTree T;cout<<"请输入二叉树节点的值以创建树"<<endl;CreateBiTree(T);cout<<"此为先序遍历";PreOrderTraverse(T);cout<<"end"<<endl;cout<<"此为中序遍历";InOrderTraverse(T);cout<<"end"<<endl;cout<<"此为后序遍历";PostOrderTraverse(T);cout<<"end"<<endl<<"此树节点数是"<<i<<endl<<"此树深度是"<<CountDepth(T)<<endl;}四、调试结果及运行界面：五、实验心得通过这次程序上机实验让我认识到了以前还不太了解的二叉树的性质和作用，这次实验的的确确的加深了我对它的理解。
数据结构实验三实验报告数据结构实验三实验报告一、实验目的本次实验的目的是通过实践掌握树的基本操作和应用。
具体来说，我们需要实现一个树的数据结构，并对其进行插入、删除、查找等操作，同时还需要实现树的遍历算法，包括先序、中序和后序遍历。
二、实验原理树是一种非线性的数据结构，由结点和边组成。
树的每个结点都可以有多个子结点，但是每个结点只有一个父结点，除了根结点外。
树的基本操作包括插入、删除和查找。
在本次实验中，我们采用二叉树作为实现树的数据结构。
二叉树是一种特殊的树，每个结点最多只有两个子结点。
根据二叉树的特点，我们可以使用递归的方式实现树的插入、删除和查找操作。
三、实验过程1. 实现树的数据结构首先，我们需要定义树的结点类，包括结点值、左子结点和右子结点。
然后，我们可以定义树的类，包括根结点和相应的操作方法，如插入、删除和查找。
2. 实现插入操作插入操作是将一个新的结点添加到树中的过程。
我们可以通过递归的方式实现插入操作。
具体来说，如果要插入的值小于当前结点的值，则将其插入到左子树中；如果要插入的值大于当前结点的值，则将其插入到右子树中。
如果当前结点为空，则将新的结点作为当前结点。
3. 实现删除操作删除操作是将指定的结点从树中移除的过程。
我们同样可以通过递归的方式实现删除操作。
具体来说，如果要删除的值小于当前结点的值，则在左子树中继续查找；如果要删除的值大于当前结点的值，则在右子树中继续查找。
如果要删除的值等于当前结点的值，则有三种情况：- 当前结点没有子结点：直接将当前结点置为空。
- 当前结点只有一个子结点：将当前结点的子结点替代当前结点。
- 当前结点有两个子结点：找到当前结点右子树中的最小值，将其替代当前结点，并在右子树中删除该最小值。
4. 实现查找操作查找操作是在树中寻找指定值的过程。
同样可以通过递归的方式实现查找操作。
具体来说，如果要查找的值小于当前结点的值，则在左子树中继续查找；如果要查找的值大于当前结点的值，则在右子树中继续查找。
数据结构实验报告二叉树《数据结构与算法》实验报告专业班级姓名学号实验项目实验三二叉树。
实验目的1、掌握用递归方法实现二叉树的遍历。
2、加深对二叉树的理解，逐步培养解决实际问题的编程能力。
题目：(1)编写二叉树的遍历操作函数。
①先序遍历，递归方法re_preOrder(TREE *tree)②中序遍历，递归方法re_midOrder(TREE *tree)③后序遍历，递归方法re_postOrder(TREE *tree)(2)调用上述函数实现先序、中序和后序遍历二叉树操作。
算法设计分析（一）数据结构的定义要求用c语言编写一个演示程序，首先建立一个二叉树，让用户输入一个二叉树，实现该二叉树的便利操作。
二叉树型存储结构定义为：typedef struct TNode{ char data;//字符型数据struct TNode *lchild,*rchild;//左右孩子指针}TNode,* Tree;（二）总体设计程序由主函数、二叉树建立函数、先序遍历函数、中序遍历函数、后序遍历函数五个函数组成。
其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能。
int main()（2）二叉树建立函数：根据用户意愿运用先序遍历建立一个二叉树。
int CreateBiTree(Tree &T)（3）先序遍历函数：将所建立的二叉树先序遍历输出。
void PreOrder(Tree T)（4）中序遍历函数：将所建立的二叉树中序遍历输出。
void InOrder(Tree T)（5）后序遍历函数：将所建立的二叉树后序遍历输出。
void PostOrder(Tree T)（三）各函数的详细设计：（1）建立一个二叉树，按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树。
对T动态分配存储空间，生成根节点，构造左、右子树（2）编写先序遍历函数，依次访问根节点、左子结点、右子节点（3）编写中序遍历函数，依次访问左子结点、根节点、右子节点（4）编写后序遍历函数，依次访问左子结点、右子节点、根节点（5）编写主函数，调用各个函数，以实现二叉树遍历的基本操作。
二叉树的基本操作实验报告学号姓名实验日期 2012-12-26实验室计算机软件技术实验指导教师设备编号 401实验内容二叉树的基本操作一实验题目实现二叉树的基本操作的代码实现二实验目的1、掌握二叉树的基本特性2、掌握二叉树的先序、中序、后序的递归遍历算法3、通过求二叉树的深度、度为2的结点数和叶子结点数等算法三实习要求(1)认真阅读书上给出的算法(2)编写程序并独立调试四、给出二叉树的抽象数据类型ADT BinaryTree{//数据对象D:D是具有相同特性的数据元素的集合。
//数据关系R:// 若D=Φ，则R=Φ，称BinaryTree为空二叉树;// 若D?Φ，则R={H}，H是如下二元关系;// (1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱; // (2)若D-{root}?Φ，则存在D-{root}={D1,Dr}，且D1?Dr =Φ; // (3)若D1?Φ，则D1中存在惟一的元素x1，<root,x1>?H，且存在D1上的关系H1 ?H;若Dr?Φ，则Dr中存在惟一的元素xr，<root,xr>?H，且存在上的关系Hr ?H;H={<root,x1>,<root,xr>,H1,Hr};// (4)(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树;(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。
//基本操作:CreateBiTree( &T, definition ) // 初始条件:definition给出二叉树T的定义。
// 操作结果:按definiton构造二叉树T。
BiTreeDepth( T )// 初始条件:二叉树T存在。
// 操作结果:返回T的深度。
PreOrderTraverse( T, visit() ) // 初始条件:二叉树T存在，Visit是对结点操作的应用函数。
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、对二叉树进行遍历操作。
二叉树的遍历有多种方法，本实验使用的是先序遍历。
首先从根节点出发，根据先序遍历的顺序，先访问左子树，然后再访问右子树，最后访问根节点。
三、实验步骤
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，直到创建完整个二叉树。
数据结构实验报告1. 实验目的和内容：掌握二叉树基本操作的实现方法2. 程序分析2.1存储结构链式存储2．程序流程2.3关键算法分析算法一：Create(BiNode<T>* &R,T data[],int i,int n)【1】算法功能：创建二叉树【2】算法基本思想：利用顺序存储结构为输入，采用先建立根结点，再建立左右孩子的方法来递归建立二叉链表的二叉树【3】算法空间时间复杂度分析：O(n)【4】代码逻辑：如果位置小于数组的长度则{ 创建根结点将数组的值赋给刚才创建的结点的数据域创建左子树，如果当前结点位置为i,则左孩子位置为2i创建右子树，如果当前结点位置为i,则右孩子位置为2i+1}否则R为空算法二：CopyTree(BiNode<T>*sR,BiNode<T>* &dR)）【1】算法功能：复制构造函数【2】算法基本思想：按照先创建根结点，再递归创建左右子树的方法来实现。
【3】算法空间时间复杂度分析：O（n)【4】代码逻辑:如果源二叉树根结点不为空则{创建根结点调用函数自身，创建左子树调用函数自身，创建右子树}将该函数放在复制构造函数中调用，就可以实现复制构造函数算法三：PreOrder(BiNode<T>*R)【1】算法功能：二叉树的前序遍历【2】算法基本思想：这个代码用的是优化算法，提前让当前结点出栈。
【3】算法空间时间复杂度分析：O（n）【4】代码逻辑（伪代码）如果当前结点为非空，则{访问当前结点当前结点入栈将当前结点的左孩子作为当前结点}如果为空{则栈顶结点出栈则将该结点的右孩子作为当前结点}反复执行这两个过程，直到结点为空并且栈空算法四：InOrder(BiNode<T>*R)【1】算法功能：二叉树的中序遍历【2】算法基本思想：递归【3】算法空间时间复杂度分析：未知【4】代码逻辑：如果R为非空：则调用函数自身遍历左孩子访问该结点再调用自身访问该结点的右孩子算法五：LevelOrder(BiNode<T>*R)【1】算法功能：二叉树的层序遍历【2】算法基本思想：【3】算法空间时间复杂度分析：O（n）【4】代码逻辑（伪代码）：如果队列不空{对头元素出队访问该元素若该结点的左孩子为非空，则左孩子入队；若该结点的右孩子为非空，则右孩子入队；}算法六：Count(BiNode<T>*R)【1】算法功能：计算结点的个数【2】算法基本思想：递归【3】算法空间时间复杂度分析：未知【4】代码逻辑：如果R不为空的话{调用函数自身计算左孩子的结点数调用函数自身计算右孩子的结点数}template<class T>int BiTree<T>::Count(BiNode<T>*R){if(R==NULL)return 0;else{int m=Count(R->lchild);int n=Count(R->rchild);return m+n+1;}}算法七：Release(BiNode<T>*R)【1】算法功能：释放动态内存【2】算法基本思想：左右子树全部释放完毕后再释放该结点【3】算法空间时间复杂度分析：未知【4】代码逻辑：调用函数自身，释放左子树调用函数自身，释放右子树释放根结点释放二叉树template<class T>void BiTree<T>::Release(BiNode<T>*R) {if(R!=NULL){Release(R->lchild);Release(R->rchild);delete R;}}template<class T>BiTree<T>::~BiTree(){Release(root);}int main(){BiTree<int> BTree(a,10);BiTree<int>Tree(BTree);BTree.PreOrder(BTree.root);cout<<endl;Tree.PreOrder(Tree.root);cout<<endl;BTree.InOrder(BTree.root);cout<<endl;Tree.InOrder(Tree.root);cout<<endl;BTree.PostOrder(BTree.root);cout<<endl;Tree.PostOrder(Tree.root);cout<<endl;BTree.LevelOrder(BTree.root);cout<<endl;Tree.LevelOrder(Tree.root);cout<<endl;int m=BTree.Count(BTree.root);cout<<m<<endl;return 0;}3.测试数据：int a[10]={1,2,3,4,5};1 2 4 5 31 2 4 5 34 25 1 34 5 2 3 11 2 3 4 554.总结：4.1:这次实验大多用了递归的算法，比较好理解。
《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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，失败。
⼆叉树基本操作--实验报告实验三⼆叉树的基本操作学院:物理与电⼦学院班级:电信1105班姓名:刘岩学号:29⼀、实验⽬的1、熟悉⼆叉树的基本操作，掌握⼆叉树的实现以及实际应⽤。
3、加深对于⼆叉树的理解，逐步培养解决实际问题的编程能⼒。
⼆、实验环境1台WINDOWS环境的PC机，装有Visual C++ 。
三、实验内容1、问题描述现需要编写⼀套⼆叉树的操作函数，以便⽤户能够⽅便的利⽤这些函数来实现⾃⼰的应⽤。
其中操作函数包括：1>创建⼆叉树CreateBTNode(*b,*str)：根据⼆叉树括号表⽰法的字符串*str⽣成对应的链式存储结构。
2>输出⼆叉树DispBTNode(*b)：以括号表⽰法输出⼀棵⼆叉树。
3>查找结点FindNode(*b,x)：在⼆叉树b中寻找data域值为x的结点,并返回指向该结点的指针。
4>求⾼度BTNodeDepth(*b)：求⼆叉树b的⾼度。
若⼆叉树为空,则其⾼度为0；否则,其⾼度等于左⼦树与右⼦树中的最⼤⾼度加l。
5>求⼆叉树的结点个数NodesCount(BTNode *b)6>先序遍历的递归算法：void PreOrder(BTNode *b)7>中序遍历的递归算法：void InOrder(BTNode *b)8>后序遍历递归算法：void PostOrder(BTNode *b)9>层次遍历算法void LevelOrder(BTNode *b)2、基本要求实现以上9个函数。
主函数中实现以下功能：创建下图中的树b输出⼆叉树b找到’H’节点，输出其左右孩⼦值输出b的⾼度输出b的节点个数输出b的四种遍历顺序3、程序编写上图转化为⼆叉树括号表⽰法为A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))程序:#include <>#include <>#define MaxSize 100typedef char ElemType;typedef struct node{ElemType data; /*数据元素*/struct node *lchild; /*指向左孩⼦*/struct node *rchild; /*指向右孩⼦*/} BTNode;void CreateBTNode(BTNode *&b,char *str);//创建BTNode *FindNode(BTNode *b,ElemType x);//查找节点int BTNodeHeight(BTNode *b);//求⾼度void DispBTNode(BTNode *b);//输出int NodesCount(BTNode *b);//⼆叉树的结点个数void PreOrder(BTNode *b);//先序遍历递归void InOrder(BTNode *b);//中序遍历递归void PostOrder(BTNode *b);//后序遍历递归void LevelOrder(BTNode *b);//层次遍历//创建void CreateBTNode(BTNode *&b,char *str){BTNode *St[MaxSize],*p=NULL;int top=-1,k,j=0;char ch;b=NULL;ch=str[j];while(ch!='\0'){switch(ch){case '(':top++;St[top]=p;k=1;break;case ')':top--;break;case ',':k=2;break;default:p=(BTNode *)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL)b=p;else{switch(k){case 1:St[top]->lchild=p;break;case 2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}//输出void DispBTNode(BTNode *b){if(b!=NULL){printf("%c",b->data);if(b->lchild!=NULL||b->rchild!=NULL){printf("(");DispBTNode(b->lchild);if(b->rchild!=NULL)printf(",");DispBTNode(b->rchild);printf(")");}}}//查找节点BTNode *FindNode(BTNode *b,ElemType x){ BTNode *p;if(b==NULL)return b;else if(b->data==x)return b;else{p=FindNode(b->lchild,x);if(p!=NULL)return p;elsereturn FindNode(b->rchild,x);}}//求⾼度int BTNodeHeight(BTNode *b){int lchildh,rchildh;if(b==NULL)return (0);else{lchildh=BTNodeHeight(b->lchild);rchildh=BTNodeHeight(b->rchild);return(lchildh>rchildh)(lchildh+1):(rchildh+1);}}//⼆叉树的结点个数int NodesCount(BTNode *b){if(b==NULL)return 0;elsereturn NodesCount(b->lchild)+NodesCount(b->rchild)+1; }//先序遍历递归void PreOrder(BTNode *b){ if(b!=NULL){printf("%c",b->data); PreOrder(b->lchild); PreOrder(b->rchild);}}//中序遍历递归void InOrder(BTNode *b){if(b!=NULL){InOrder(b->lchild);printf("%c",b->data); InOrder(b->rchild);}}//后序遍历递归void PostOrder(BTNode *b){ if(b!=NULL){PostOrder(b->lchild); PostOrder(b->rchild);printf("%c",b->data);}}//层次遍历void LevelOrder(BTNode *b){ BTNode *p;BTNode *qu[MaxSize];int front,rear;front=rear=-1;rear++;qu[rear]=b;while(front!=rear){front=(front+1)%MaxSize;p=qu[front];printf("%c",p->data);if(p->lchild!=NULL){rear=(rear+1)%MaxSize;qu[rear]=p->lchild;}if(p->rchild!=NULL){rear=(rear+1)%MaxSize;qu[rear]=p->rchild;}}}void main(){BTNode *b,*p,*lp,*rp;char str[]="A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";//根据树形图改写成的//⼆叉树括号表⽰法的字符串*str //char str[100];scanf("%s",&str);//⾃⾏输⼊括号表⽰的⼆叉树CreateBTNode(b,str); //创建树bprintf("\n");printf("输出⼆叉树:");//输出⼆叉树bDispBTNode(b);printf("\n");printf("'H'结点:");//找到'H'节点，输出其左右孩⼦值p=FindNode(b,'H');printf("\n");if (p!=NULL){printf("左孩⼦节点的值");printf("%c",p->lchild->data);printf("\n");printf("右孩⼦节点的值");printf("%c",p->rchild->data);printf("\n");//此处输出p的左右孩⼦节点的值}printf("\n");printf("⼆叉树b的深度:%d\n",BTNodeHeight(b));//输出b的⾼度printf("⼆叉树b的结点个数:%d\n",NodesCount(b));//输出b的节点个数printf("\n");printf(" 先序遍历序列:\n");//输出b的四种遍历顺序printf(" 算法:");PreOrder(b);printf("\n");printf(" 中序遍历序列:\n");printf(" 算法:");InOrder(b);printf("\n");printf(" 后序遍历序列:\n");printf(" 算法:");PostOrder(b);printf("\n");printf(" 层次遍历序列:\n");printf(" 算法:");LevelOrder(b); printf("\n");}四、实验⼼得与⼩结通过本次实验，我熟悉⼆叉树的基本知识内容，对课本的知识有了更加深刻的理解与掌握掌握。
二叉树的基本操作与实现实验报告二叉树是一种重要的数据结构，在计算机科学领域中被广泛应用。
本实验将介绍二叉树的基本操作与实现，并给出相应的实验报告。
一、引言二叉树是一种特殊的树状结构，每个节点至多有两个子节点。
二叉树有许多重要的特性，如平衡二叉树、二叉树等，应用广泛。
在本实验中，我们将介绍二叉树的基本操作和实现。
二、实验目的1.掌握二叉树的基本概念和特性；2.熟悉二叉树的基本操作，包括创建、插入、删除、遍历等；3.学会使用编程语言实现二叉树的基本操作。
三、实验内容本实验主要包括以下内容：1.二叉树的定义和基本概念；2.二叉树的基本操作，包括创建、插入、删除、遍历等；3.使用编程语言实现二叉树的基本操作；4.测试和验证二叉树的基本操作的正确性。
四、实验步骤1.二叉树的定义和基本概念二叉树是一种树状结构，每个节点至多有两个子节点。
二叉树的每个节点包含一个数据项和指向左子树和右子树的指针。
二叉树的特性有很多，如完全二叉树、平衡二叉树、二叉树等。
2.二叉树的基本操作（1）创建二叉树：可以通过手动输入节点数据来创建二叉树，也可以通过读取文件中的数据来创建二叉树。
（2）插入节点：在指定位置插入一个新节点。
（3）删除节点：删除指定位置的节点。
（4）遍历二叉树：有前序遍历、中序遍历和后序遍历三种遍历方式。
3.使用编程语言实现二叉树的基本操作实现二叉树的基本操作可以使用编程语言来完成。
我们可以定义一个二叉树的结构体，包含节点数据和指向左右子树的指针。
然后根据具体的需求，实现相应的操作函数。
4.测试和验证二叉树的基本操作的正确性在完成二叉树的基本操作后，我们可以编写测试代码来验证操作的正确性。
通过创建二叉树，并进行插入、删除和遍历操作，观察输出结果是否符合预期。
五、实验结果与分析在完成二叉树的基本操作后，我们可以进行测试和验证。
通过输出二叉树的遍历结果，比对预期结果来判断操作是否正确。
同时，我们还可以观察二叉树的结构和特性，如是否满足平衡二叉树或二叉树的条件。
二叉树的基本操作实验报告二叉树的基本操作实验报告引言：二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点。
二叉树的基本操作包括创建、遍历、插入和删除等。
本实验旨在通过实践来深入了解二叉树的基本操作，并通过实验结果验证其正确性和有效性。
一、创建二叉树创建二叉树是二叉树操作中的第一步。
在本实验中，我们使用了递归算法来创建二叉树。
递归算法是一种重要的算法思想，通过将问题划分为更小的子问题来解决复杂的问题。
在创建二叉树时，我们首先创建根节点，然后递归地创建左子树和右子树。
二、遍历二叉树遍历二叉树是对二叉树中的每个节点进行访问的过程。
常见的遍历方式有前序遍历、中序遍历和后序遍历。
前序遍历先访问根节点，然后递归遍历左子树和右子树；中序遍历先递归遍历左子树，然后访问根节点，最后递归遍历右子树；后序遍历先递归遍历左子树和右子树，最后访问根节点。
三、插入节点插入节点是向二叉树中添加新节点的操作。
插入节点的过程需要遵循二叉树的特性，即左子节点的值小于父节点的值，右子节点的值大于父节点的值。
在插入节点时，我们需要找到合适的位置，将新节点插入到正确的位置上。
四、删除节点删除节点是从二叉树中移除节点的操作。
删除节点的过程相对复杂，需要考虑多种情况。
如果要删除的节点是叶子节点，直接删除即可。
如果要删除的节点只有一个子节点，将其子节点连接到父节点上。
如果要删除的节点有两个子节点，我们需要找到其后继节点或前驱节点来替代被删除的节点。
实验结果：通过实验，我们成功地实现了二叉树的基本操作。
创建二叉树的递归算法能够正确地创建出符合要求的二叉树。
遍历二叉树的算法能够按照指定的顺序遍历每个节点。
插入节点和删除节点的操作也能够正确地修改二叉树的结构。
讨论与总结：二叉树的基本操作是数据结构中的重要内容，对于理解和应用其他数据结构具有重要意义。
通过本次实验，我们深入了解了二叉树的创建、遍历、插入和删除等操作，并通过实验验证了其正确性和有效性。
数据结构实验报告二叉树二叉树是一种重要的数据结构，广泛应用于计算机科学和算法设计中。
在本次实验中，我们通过实际编程实践，深入理解了二叉树的基本概念、性质和操作。
一、二叉树的定义和基本性质二叉树是一种特殊的树结构，每个节点最多有两个子节点。
它具有以下基本性质：1. 根节点：二叉树的顶部节点称为根节点，它没有父节点。
2. 子节点：每个节点最多有两个子节点，分别称为左子节点和右子节点。
3. 叶节点：没有子节点的节点称为叶节点。
4. 深度：从根节点到某个节点的路径长度称为该节点的深度。
5. 高度：从某个节点到其叶节点的最长路径长度称为该节点的高度。
6. 层次遍历：按照从上到下、从左到右的顺序遍历二叉树的节点。
二、二叉树的实现在本次实验中，我们使用C++语言实现了二叉树的基本操作，包括创建二叉树、插入节点、删除节点、查找节点等。
通过这些操作，我们可以方便地对二叉树进行增删改查。
三、二叉树的遍历二叉树的遍历是指按照某种顺序访问二叉树的所有节点。
常用的遍历方式有三种：前序遍历、中序遍历和后序遍历。
1. 前序遍历：先访问根节点，然后依次递归遍历左子树和右子树。
2. 中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。
3. 后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。
四、二叉树的应用二叉树在计算机科学和算法设计中有广泛的应用。
以下是一些常见的应用场景：1. 二叉搜索树：二叉搜索树是一种特殊的二叉树，它的左子树的值都小于根节点的值，右子树的值都大于根节点的值。
它可以高效地支持插入、删除和查找操作，常用于有序数据的存储和检索。
2. 堆：堆是一种特殊的二叉树，它的每个节点的值都大于（或小于）其子节点的值。
堆常用于实现优先队列等数据结构。
3. 表达式树：表达式树是一种用二叉树表示数学表达式的方法。
通过对表达式树的遍历，可以实现对数学表达式的计算。
4. 平衡树：平衡树是一种特殊的二叉树，它的左右子树的高度差不超过1。
《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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，失败。
删除B 后，以广义表形式打印A （，C （F （，G ）））二、 概要设计程序中将涉及下列两个抽象数据类型：一个是二叉树，一个是队列。
1、设定“二叉树”的抽象数据类型定义：ADT BiTree{数据对象D ：D 是具有相同特性的数据元素的集合。
数据关系R ：若 Φ=D ，则Φ=R ，称BiTree 为空二叉树；若 Φ≠D ，则{}H R =，H 是如下二元关系：（1） 在D 中存在唯一的称为根的数据元素root ，它在关系H 下无前驱；（2） 若{} ,Φ≠-root D 则存在{}{},,r l D D root D =-且Φ=⋂r l D D ;（3） 若,Φ≠l D 则l D 中存在唯一的元素l x ,,,H x root l >∈<且存在l D 上的关系;H H l ⊂若,Φ≠r D 则r D 中存在唯一的元素r x ,,,H x root r >∈<且存在r D 上的关系{}r l r l r H H x root x root H H H ,,,,,;><><=⊂；（4） {}()l l H D ,是一棵符合本定义的二叉树，称为根的左子树，{}()r r H D ,是一棵符合本定义的二叉树，称为根的有字树基本操作：CreateBiTree&T)操作结果：按照T 的定义构造一个二叉树。
BiTreeDepth(& T)初始条件：二叉树T 已存在。
操作结果：返回T 的深度。
BiTreeWidth(&T)初始条件：二叉树T 已存在。
操作结果：返回T 的宽度。
PreOderTraverse&T)初始条件：二叉树T 已存在。
操作结果：先序遍历打印T ，InOderTraverse(&T)初始条件：二叉树T 已存在。
操作结果：中序遍历打印T 。
PostOderTraverse(&T)初始条件：二叉树T 已存在。
操作结果：后序遍历打印T 。
LevelTraverse(&T)初始条件：二叉树T 已存在。
操作结果：层次遍历T 。
DeleteXTree(&T,TElemType x)初始条件：二叉树已存在。
操作结果：删除元素为x 的结点以及其左子树和右子树。
CopyTree(&T)初始条件：二叉树T 已存在。
操作结果：以T 为模板，复制另一个二叉树。
｝ADT BiTree2、设定队列的抽象数据类型定义：ADT Queue{数据对象：D={i a },+∈∈N i BiTree a i 数据关系：R1={<1,-i i a a >|1-i a ,D a i ∈,i=2,…，n}约定1a 端为队列头，n a 端为队列尾。
基本操作：InitQueue(&Q)操作结果：构造一个空队列Q 。
EnQueue(&Q,&e)初始条件：队列Q 已存在。
操作结果：插入元素e 为Q 的新的队尾元素。
DeQueue(&Q)初始条件：队列Q 已存在。
操作结果：删除Q 的对头元素，并返回其值。
QueueEmpty(&Q)初始条件：队列Q 已存在。
操作结果：若Q 为空队列，则返回1，否则0。
} ADT Queue3、本程序包含四个模块1）主程序模块void main( ){初始化；先序输入二叉树各结点元素；各种遍历二叉树；对二叉树进行常见运算；复制二叉树；在复制的二叉树上进行二叉树的常见操作；｝2）二叉树模块——实现二叉树的抽象数据类型和基本操作2）队列模块——实现队列的抽象数据类型及今本操作3）广义表打印模块——以广义表形式打印二叉树4）二叉树运算模块——对二叉树的叶子、非空子孙结点数目、度为2或1的结点数三、 详细设计1、主程序中需要的全程量#define M 10 // 统计二叉树宽度时需用数组对每层宽度进行存储，这M表示数组的长度2、队列的建立与基本操作typedef struc t QNode{BiTree data; //队列中存储的元素类型struct QNode *next; //指向二叉树结点的指针}QNode,*Queueptr;typedef struct{Queueptr front; //队列的队头指针Queueptr rear; //队列的队尾指针}LinkQueue;算法描述：为了对二叉树进行层次遍历，需要“先访问的结点，其孩子结点必然也先访问”，故需运用到队列。
而考虑到层次遍历对队列操作的需要，只需进行队列的初始化，入队和出队以及检查队列是否为空。
伪码算法：void InitQueue(LinkQueue *Q){//初始化队列申请一个结点Q->front=Q->rear=(Queueptr)malloc(sizeof(QNode));if(!Q->front)exit(1);//存储分配失败处理Q->front->next=NULL;//构成带头结点里的空链队列}void EnQueue(LinkQueue *Q,BiTree e){//插入元素为e为Q的队尾元素Queueptr q;q=(Queueptr)malloc(sizeof(QNode));if(!q)exit(1);q->data=e;q->next=NULL;Q->rear->next=q; //元素e的结点入列Q->rear=q;}BiTree DeQueue(LinkQueue *Q){//从队列中删除队头元素，并直接返回给调用的主函数Queueptr p;BiTree q;if(Q->front==Q->rear){//队列为空printf("ERROR!\n");exit(1);}p=Q->front->next;q=p->data;Q->front->next=p->next; //删除该结点if(Q->rear==p)Q->rear=Q->front;free(p);return q;//返回队头元素}int QueueEmpty(LinkQueue *Q){//检查队列是否为空，若为空则返回真值，否则返回0if(Q->front==Q->rear)return 1;elsereturn 0;}3、二叉树的建立与基本操作typedef struct BiTNode{TElemType data; //二叉树结点存储的元素类型struct BiTNode *lchild,*rchild; //二叉树左右孩子指针}BiTNode,*BiTree;算法分析：二叉树的基本操作是本程序的核心，考虑到二叉树的定义就是采用递归定义，所以很容易想到对二叉树的操作可通过递归调用来实现。
1）二叉树的遍历算法描述：二叉树中常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就需要遍历二叉树。
即要求按某条路径寻访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。
回顾二叉树的递归定义可知，二叉树是由3个基本单元组成：根节点、左子树和右子树。
因此，若能依次遍历这三部分，便是遍历了整棵二叉树。
如果以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。
若限定先右后左，则只有前三种情况，分别称之为先（根）序遍历。
中（根）序遍历和后（根）序遍历。
基于二叉树的递归定义，可得下述遍历二叉树的递归定义算法。
先序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。
伪码算法：void PreOderTraverse(BiTree T){//采用二叉链表存储结构if(T){putchar(T->data);//最简单的访问结点法，输出结点元素，这里先访问根结点PreOderTraverse(T->lchild);PreOderTraverse(T->rchild);}}中序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。
伪码算法：void InOderTraverse(BiTree T){//采用二叉链表存储结构if(T){InOderTraverse(T->lchild);//先遍历左子树putchar(T->data);// 最简单的访问结点法，输出结点元素，这里第二访问根结点InOderTraverse(T->rchild);}}后序遍历二叉树的操作定义：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。
