实验3 - 二叉树的建立及基本操作

二叉树的建立与基本操作二叉树是一种特殊的树形结构，它由节点（node）组成，每个节点最多有两个子节点。

二叉树的基本操作包括建立二叉树、遍历二叉树、查找二叉树节点、插入和删除节点等。

本文将详细介绍二叉树的建立和基本操作，并给出相应的代码示例。

一、建立二叉树建立二叉树有多种方法，包括使用数组、链表和前序、中序、后序遍历等。

下面以使用链表的方式来建立二叉树为例。

1.定义二叉树节点类首先，定义一个二叉树节点的类，包含节点值、左子节点和右子节点三个属性。

```pythonclass Node:def __init__(self, value):self.value = valueself.left = Noneself.right = None```2.建立二叉树使用递归的方法来建立二叉树，先构造根节点，然后递归地构造左子树和右子树。

```pythondef build_binary_tree(lst):if not lst: # 如果 lst 为空，则返回 Nonereturn Nonemid = len(lst) // 2 # 取 lst 的中间元素作为根节点的值root = Node(lst[mid])root.left = build_binary_tree(lst[:mid]) # 递归构造左子树root.right = build_binary_tree(lst[mid+1:]) # 递归构造右子树return root```下面是建立二叉树的示例代码：```pythonlst = [1, 2, 3, 4, 5, 6, 7]root = build_binary_tree(lst)```二、遍历二叉树遍历二叉树是指按照其中一规则访问二叉树的所有节点，常见的遍历方式有前序遍历、中序遍历和后序遍历。

1.前序遍历前序遍历是指先访问根节点，然后访问左子节点，最后访问右子节点。

```pythondef pre_order_traversal(root):if root:print(root.value) # 先访问根节点pre_order_traversal(root.left) # 递归访问左子树pre_order_traversal(root.right) # 递归访问右子树```2.中序遍历中序遍历是指先访问左子节点，然后访问根节点，最后访问右子节点。

二叉树实验报告二叉树实验报告引言：二叉树作为一种常用的数据结构，在计算机科学领域中具有广泛的应用。

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

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

树的最顶层节点称为根节点。

1.2 二叉树的特点二叉树具有以下特点：- 每个节点最多有两个子节点，分别称为左子节点和右子节点；- 左子节点的值小于等于父节点的值，右子节点的值大于等于父节点的值；- 二叉树的左子树和右子树也是二叉树。

二、二叉树的遍历方式2.1 先序遍历先序遍历是指先访问根节点，然后按照先序遍历的方式依次访问左子树和右子树。

2.2 中序遍历中序遍历是指按照中序遍历的方式依次访问左子树，根节点和右子树。

2.3 后序遍历后序遍历是指按照后序遍历的方式依次访问左子树，右子树和根节点。

三、二叉树的实验操作3.1 二叉树的创建为了便于实验操作，我们选择使用Python编程语言来实现二叉树的创建和操作。

首先，我们需要定义一个二叉树节点的类，包含节点的值、左子节点和右子节点。

3.2 二叉树的插入在已有的二叉树中插入一个新的节点，需要遵循二叉树的规则。

如果插入的节点值小于当前节点的值，则将节点插入到当前节点的左子树；如果插入的节点值大于当前节点的值，则将节点插入到当前节点的右子树。

3.3 二叉树的查找在二叉树中查找一个特定的节点，需要遍历整个二叉树。

从根节点开始，如果要查找的节点值小于当前节点的值，则继续在左子树中查找；如果要查找的节点值大于当前节点的值，则继续在右子树中查找；如果要查找的节点值等于当前节点的值，则找到了目标节点。

3.4 二叉树的删除在二叉树中删除一个节点，需要考虑多种情况。

如果要删除的节点没有子节点，直接将其删除即可；如果要删除的节点只有一个子节点，将子节点替换为要删除的节点；如果要删除的节点有两个子节点，需要找到其右子树中的最小节点，将其值替换到要删除的节点，然后删除最小节点。

实验三二叉树的基本运算一、实验目的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）掌握二叉树的先序、中序和后序遍历算法。

【实验内容】1. 编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。

如：输入先序序列abc###de###，则建立如下图所示的二叉树。

并显示其先序序列为：abcde中序序列为：cbaed后序序列为：cbeda【实验步骤】1.打开VC++。

2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。

至此工程建立完毕。

3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。

给文件起好名字，选好路径，点OK。

至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码5．编译－＞链接－＞调试#include#include#define OK 1#define OVERFLOW -2typedef int Status;typedef char TElemType;typedef struct BiTNode{TElemType data;struct BiTNode *lchild, *rchild;}BiTNode,*BiTree;Status CreateBiTree(BiTree &T){TElemType ch;scanf("%c",&ch);if (ch=='#')T= NULL;else{if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))return OVERFLOW;T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); }return OK;} // CreateBiTreevoid PreOrder(BiTree T) {if(T){printf("%c",T->data); PreOrder(T->lchild); PreOrder(T->rchild);}}void InOrder(BiTree T) {if(T){InOrder(T->lchild);printf("%c",T->data);InOrder(T->rchild);}}void PostOrder(BiTree T){if(T){PostOrder(T->lchild); PostOrder(T->rchild);printf("%c",T->data);}}void main(){BiTree T;CreateBiTree(T);printf("\n先序遍历序列:"); PreOrder(T);printf("\n中序遍历序列:"); InOrder(T);printf("\n后序遍历序列:"); PostOrder(T);}【实验心得】这次实验主要是通过先序序列建立二叉树，和二叉树的先序、中序、后续遍历算法。

实验三二叉树的基本操作一、实验目的1、进一步掌握树的结构及非线性特点，递归特点和动态性。

2、掌握二叉树的建立算法。

3、掌握二叉树的三种遍历方法以及基于遍历的几种基本操作。

二、实验内容1、二叉树的链式存储结构的建立；2、二叉树的三种遍历算法以及基于遍历的几种操作的实现。

三、实验要求1、学生用C++/C完成算法设计和程序设计并上机调试通过；2、撰写实验报告，提供实验测试数据和实验结果；3、分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。

四、实验准备1、了解树的结构特点及概念、二叉树的概念及结构特点。

2、了解树和二叉树的基本概念和术语。

3、二叉树的三种遍历方法（先序、中序、后序遍历）先序遍历：若二叉树为空，则空操作，否则①访问根结点；②先序遍历左子树；③先序遍历右子树。

中序遍历：若二叉树为空，则空操作，否则①中序遍历左子树；②访问根结点；③中序遍历右子树。

后序遍历：若二叉树为空，则空操作，否则①后序遍历左子树；②后序遍历右子树；③访问根结点。

4、二叉树的各种存储结构及其适用范围，特别是链式存储结构。

五、实验步骤1、编程实现二叉树的建立、遍历以及基于遍历的几种基本操作。

(1)采用二叉链表存储结构创建一个二叉树；(2)用递归方法实现二叉树的三种遍历算法(3)求二叉树中叶子结点的个数,度为1 的结点个数和度为2 的结点个数；(4)求二叉树的深度。

六、实验参考代码#include "iostream.h"#include "stdio.h"#include "stdlib.h"#define OK 1#define ERROR 0#define OVERFLOW -2#define NULL 0typedef char TElemType; //限定元素的数据类型typedef int Status;typedef struct BiTNode // 定义二叉树结点结构{TElemType data;BiTNode *lchild, *rchild; // 左右孩子指针} BiTNode, *BiTree;//按扩展的前序序列建立二叉树存储结构的算法Status CreateBiTree(BiTree &T){char ch;scanf("%c",&ch);if (ch=='#') T = NULL;else{if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);T->data = ch; // 生成根结点CreateBiTree(T->lchild); // 构造左子树CreateBiTree(T->rchild); // 构造右子树}return OK;} // CreateBiTree// 先序遍历二叉树void PreOrder (BiTree T){if (T) {printf("%4c",T->data); // 访问结点PreOrder(T->lchild); // 遍历左子树PreOrder(T->rchild) ; // 遍历右子树}}// 中序遍历二叉树void InOrder (BiTree T){if (T){InOrder(T->lchild); // 遍历左子树printf("%4c",T->data); // 访问结点InOrder(T->rchild);// 遍历右子树}}// 后序遍历二叉树void PostOrder (BiTree T){if (T) {PostOrder (T->lchild); // 遍历左子树PostOrder (T->rchild);// 遍历右子树printf("%4c",T->data); // 访问结点}}//求二叉树的叶子结点数void CountLeaf (BiTree T, int& count){if(T){if((!T->lchild)&&(!T->rchild)) count++;CountLeaf(T->lchild,count);CountLeaf(T->rchild,count);}}//求二叉树中度为1的结点和度为2 的结点的数void CountBT(BiTree T,int &m,int &n){if(T){if((T->lchild!=0)&&(T->rchild!=0))n++; //度为2的结点else if(((T->lchild!=0)&&(T->rchild==0))||((T->lchild==0)&&(T->rchild!=0)))m++; //度为1 的结点CountBT (T->lchild,m,n);CountBT (T->rchild,m,n);}}//以下是求二叉树的深度int Depth (BiTree T ){int m,n;if(!T) return 0;else{m = Depth(T->lchild);n = Depth(T->rchild);return (m>n?m:n)+1;}}//主函数void main(){BiTree T;int s=0,m=0,n=0,d=0;T=NULL;int select;while(1) {printf("\n 请选择要执行的操作:\n");printf("1.创建二叉树\n");printf("2.二叉树的递归遍历算法（前、中、后）\n");printf("3.求二叉树的叶子结点数\n");printf("4.求二叉树的深度\n");printf("0.退出\n");scanf("%d",&select);getchar();switch(select) {case 0:return;case 1:printf("\n 请按先序次序输入各结点的值，以#表示空树:\n");CreateBiTree(T);printf("二叉树已建立完毕！\n");break;case 2:if(!T) printf("\n 未建立树，请先建树！\n");else {printf("\n 先序遍历:");PreOrder(T);printf("\n 中序遍历:");InOrder(T);printf("\n 后序遍历:");PostOrder(T);printf("\n");}break;case 3:if(!T) printf("\n 未建立树，请先建树！\n");else{CountLeaf(T,s);printf("\n 叶子结点数为：%d\n",s);CountBT(T,m,n);printf("度为1的结点数为：%d\n",m);printf("度为2 的结点数为：%d\n",n);}break;case 4:if(!T) printf("\n 未建立树，请先建树！\n");else{d=Depth(T);printf("\n 二叉树的深度为：%d\n",d);}break;default:printf("请确认选择项:\n");}//end switch}//end while}七、测试数据教材138 页，图7-10所示的二叉树按展的前序序列输入序列为：A B D # G # # # C E # # F H # # #。

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.利用递归实现前后序遍历，思路简洁，仅需要调整递归体的执行顺序即可实现。

《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为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、熟练掌握二叉树的各种遍历算法。

二、实验内容题目一：二叉树的基本操作实现（必做题）[ 问题描述]建立一棵二叉树，试编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；（选做）4. 将二叉树每个结点的左右子树交换位置。

（选做）[ 基本要求]从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），[ 测试数据]如输入：AB（$巾D邱毋巾F巾巾巾（其中巾表示空格字符）则输出结果为先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA层序：ABCDEFG[ 选作内容]采用非递归算法实现二叉树遍历三、算法设计1、 主要思想：根据二叉树的图形结构创建出二叉树的数据结构, 用指针对树进行操作，重点掌握二叉树的结构和性质。

2、 本程序包含四个模块：然后 (1)结构体定义(2) 创建二叉树(3) 对树的几个操作(4) 主函数四、调试分析这是一个比较简单程序，调试过程中并没有出现什么问题,思路比较清晰五、实验结果六、总结此次上机实验对二叉树进行了以一次实际操作，让我对二叉树 有了更深的了解，对二叉树的特性有了更熟悉的认知，让我知道了二叉树的重要性和便利性，这对以后的编程有更好的帮助。

七、源程序#in clude <iostream>#in clude <queue>using namespacestd;#defi ne TElemType char#defi ne Status int#defi ne OK1#defi ne ERRORtypedef struct BiTNode{TEIemTypedata;struct BiTNode * Ichild, *rchild;} BiTNode,* BiTree ;Status CreateBiTree( BiTree &T) {TElemTypech;cin >> ch;if (ch == '#')T = NULLelse{if (!( T = ( BiTNode *)malloc( sizeof (BiTNode))))exit( OVERFLOW「>data = ch;CreateBiTree( T->lchild);CreateBiTree( T->rchild);}return OKStatus PreOrderTraverse( BiTree T){if ( T){cout << T->data;if (PreOrderTraverse( T->lchild))if (PreOrderTraverse( T->rchild))return OKreturn ERRQR}elsereturn OK}Status InOrderTraverse( BiTree T){if ( T) In OrderTraverse( T->lchild); cout << T->data;In OrderTraverse( T->rchild);}return OK}Status PostOrderTraverse( BiTree T){if ( T){PostOrderTraverse( T->lchild);PostOrderTraverse( T->rchild); cout << T->data;}return OK}Status leOrderTraverse( BiTree T){std:: queuevBiTree > Q;if ( T == NULI) return ERRQRelse {Q.push( T);while (!Q.empty()){T = Q.fron t();Q.pop()；NULI) cout << T->data;if ( T->lchild != NULLQ.push(T->lchild);if ( T->rchild != NULLQ.push( T->rchild);}}return OK}Status change( BiTree T){BiTree temp = NULLif ( T->lchild == NULL&& T->rchild ==return OKelse {temp = T->lchild;T->lchild = T->rchild;T->rchild = temp;if ( T->lchild)cha nge(「>lchild);if ( T->rchild)cha nge(「>rchild);return OK}:rchilddeep + 1; int FindTreeDeep( BiTree T){int deep = 0;if ( T){int lchilddeep = FindTreeDeep( T->lchild);int rchilddeep = FindTreeDeep( T->rchild);deep = lchilddeep >= rchilddeep ? lchilddeep + 1 }return deep;}int main(){BiTree T;CreateBiTree(T);cout << "先序遍历顺序为：";PreOrderTraverse(T);cout << en dl;cout << "中序遍历顺序为：”；InO rderTraverse(T);cout << en dl;cout << "后序遍历顺序为：”；PostOrderTraverse(T);cout << en dl;cout << "层序遍历顺序为：";leOrderTraverse(T);cout << en dl;cout << "二叉树深度为："<< Fi ndTreeDeep(T)«e ndl;cout << "左右子树交换后：";cha nge(T);cout << "先序遍历顺序为：";PreOrderTraverse(T); |cout << en dl;return 0;}。

二叉树实验报告1. 引言二叉树是一种常用的数据结构，广泛应用于计算机科学和信息技术领域。

本实验旨在通过对二叉树的理解和实现，加深对数据结构与算法的认识和应用能力。

本报告将介绍二叉树的定义、基本操作以及实验过程中的设计和实现。

2. 二叉树的定义二叉树是一个有序树，其每个节点最多有两个子节点。

树的左子节点和右子节点被称为二叉树的左子树和右子树。

3. 二叉树的基本操作3.1 二叉树的创建在实验中，我们通过定义一个二叉树的节点结构来创建一个二叉树。

节点结构包含一个数据域和左右指针，用于指向左右子节点。

创建二叉树的过程可以通过递归或者迭代的方式来完成。

3.2 二叉树的插入和删除二叉树的插入操作是将新节点插入到树中的合适位置。

插入时需要考虑保持二叉树的有序性。

删除操作是将指定节点从树中删除，并保持二叉树的有序性。

在实验中，我们可以使用递归或者循环的方式实现这些操作。

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

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

前序遍历先访问根节点，然后按照左孩子-右孩子的顺序递归遍历左右子树。

中序遍历按照左孩子-根节点-右孩子的顺序递归遍历左右子树。

后序遍历按照左孩子-右孩子-根节点的顺序递归遍历左右子树。

3.4 二叉树的查找查找操作是指在二叉树中查找指定的值。

可以通过递归或者循环的方式实现二叉树的查找操作。

基本思路是从根节点开始，通过比较节点的值和目标值的大小关系，逐步向左子树或者右子树进行查找，直到找到目标节点或者遍历到叶子节点。

4. 实验设计和实现在本实验中，我们设计并实现了一个基于Python语言的二叉树类。

具体实现包括二叉树的创建、插入、删除、遍历和查找操作。

在实验过程中，我们运用了递归和迭代的方法实现了这些操作，并进行了测试和验证。

4.1 二叉树类的设计我们将二叉树的节点设计为一个类，其中包括数据域和左右子节点的指针。

另外，我们设计了一个二叉树类，包含了二叉树的基本操作方法。

⼆叉树基本操作--实验报告实验三⼆叉树的基本操作学院:物理与电⼦学院班级:电信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.测试和验证二叉树的基本操作的正确性在完成二叉树的基本操作后，我们可以编写测试代码来验证操作的正确性。

通过创建二叉树，并进行插入、删除和遍历操作，观察输出结果是否符合预期。

五、实验结果与分析在完成二叉树的基本操作后，我们可以进行测试和验证。

通过输出二叉树的遍历结果，比对预期结果来判断操作是否正确。

同时，我们还可以观察二叉树的结构和特性，如是否满足平衡二叉树或二叉树的条件。

实验3：二叉树的建立及应用1、实验目的∙熟练掌握二叉树的二叉链表存储结构∙掌握二叉树的非线性和递归性特点∙熟练掌握二叉树的递归遍历操作的实现方法∙加深对二叉树结构和性质的理解，逐步培养解决实际问题的编程能力2、实验内容a)按先序序列输入字符序列，建立二叉链表。

如ABC□□DE□G□□F□□□（□表示空格）b)中序遍历二叉树：递归算法。

c)后序遍历二叉树：递归算法。

d)求二叉树的高度、深度。

e)求二叉树的叶子个数。

f)应用训练: 建立表达树,并计算表达式2^(1+3)的值。

提示：若求表达式4+5的值，则输入其表达树的先序字符序列：+4□□5□□3、实验指导a)首先将二叉树的链式存储结构定义放在一个头文件：如取名为BinTreeDef.h。

b)将二叉树的基本操作算法也集中放在一个文件之中，如取名为BinTreeAlgo.h。

包含关于二叉树的链式结构操作的一些基本算法，如：InitBiTree、DestroyBiTree、CreateBiTree、BiTreeEmpty、BiTreeDepth、Root、PreOrderTraverse、InOrderTraverse 等。

c)将函数的测试和主函数组合成一个文件，如取名为BinTreeUse.cpp。

4、参考程序#include"pubuse.h" /* 与实验一的意义相同*/typedef char TElemType;TElemType Nil=' ';#include"BinTreeDef.h" /* 二叉树链式存储结构定义*/#include"BinTreeAlgo.h" /* 二叉树基本算法和扩展算法定义*/ double eValue(BiTree t)// 求表达树值{if(t!=NULL){if(isdigit(t->data)) //如果遍历到的是数字return t->data-'0';else //如果遍历到的是运算符结点{char op=t->data; //获取运算符double x=eValue(t->lchild);//求左表达树的值double y=eValue(t->rchild); //求左表达树的值double res;switch(op) //根据不同的运算符对数据进行计算{case '+':res=x+y;break;case '-':res=x-y;break;case '*':res=x*y;break;case '/':res=x/y;break;case '^':res=pow(x,y);break;case '%':res=int(x)%int(y);break;};return res;};}elsereturn 0;}void main(){BiTree T,et;char s;//加一个接收回车的字符TElemType e1;InitBiTree(T);printf("请先序输入二叉树:(如:AB 三个空格表示A为根结点,B为左子树的二叉树)\n");CreateBiTree(T); //创建二叉树e1=Root(T);if(e1!=Nil)printf("二叉树的根为: %c\n",e1);elseprintf("树空，无根\n");printf("中序递归遍历二叉树:");InOrderTraverse(T); //中序遍历二叉树printf("\n");printf("后序递归遍历二叉树:");PostOrderTraverse(T); //后序遍历二叉树printf("\n");printf("二叉树的结点数=%d\n",Nodes(T));printf("二叉树的叶子结点数=%d\n",LeafNodes(T));printf("按竖向树状打印的二叉树:\n");PrintTree(T,0);scanf("%c",&s); //加上这一句，对数字输入没有影响，只接收回车//fflush(stdin); //清空输入缓冲区；printf("请先序输入表达式2^(1+3)的二叉树：)\n");InitBiTree(et);CreateBiTree(et);printf("后缀表达式：");PostOrderTraverse(et);printf("=%f\n",eV alue(et));}5、实验结果6、实验分析本次试验是对二叉树的进一步考察，首先试验前必须清楚各种遍历：(1)先序遍历：访问根；按先序遍历左子树；按先序遍历右子树(2)中序遍历：按中序遍历左子树；访问根；按中序遍历右子树(3)后序遍历：按后序遍历左子树；按后序遍历右子树；访问根(4)层次遍历：即按照层次访问，通常用队列来做。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

数据结构二叉树的建立和遍历数据结构实验三二叉树的建立和遍历一、实验目的1、掌握二叉树链式存储的类型定义及实现。

2、掌握二叉树链式存储的各类基本运算方法。

如二叉树的创建、遍历、查找等运算。

3、掌握二叉树用不同方法表示所对应的不同输入形式。

4、掌握二叉树中个重要性质在解决实际问题中的应用。

二、实验内容建立二叉树并实现各种遍历：1、创建二叉树2、用递归方法实现二叉树的各种遍历3、求二叉树的深度、结点数目、叶子结点数目在算法实现上，从算法的效率看，递归方法书写形式较为简洁，更为直观，一般具有较好的空间效率。

附加要求：采用先\中\后序用非递归的方法遍历二叉树。

重点：理解遍历二叉树的过程.三、算法实现（读懂程序，并进行程序填空）#include"stdio.h"#include"string.h"#include#include#define Max 20 //结点的最大个数using namespace std;typedef struct node{char data;struct node *lchild,*rchild;}BinTNode; //自定义二叉树的结点类型typedef BinTNode *BinTree; //定义二叉树的指针int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数BinTree CreatBinTree(void){//==========基于先序遍历算法创建二叉树==============//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========BinTree T;char ch;if((ch=getchar())=='#')return(NULL); //读入#，返回空指针else{T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点T->data=ch;T->lchild=CreatBinTree(); //构造左子树T->rchild=CreatBinTree(); //构造右子树return(T);}}void Preorder(BinTree bt){//========NLR 先序遍历=============if(bt!=NULL) {printf("%c",bt->data); //访问结点Preorder(bt->lchild); //先序遍历左子树Preorder(bt->rchild); //先序遍历右子树}}void Inorder(BinTree bt){//========LNR 中序遍历===============}void Postorder(BinTree bt){//==========LRN 后序遍历============}int TreeDepth(BinTree bt){//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========int hl,hr,max;if(bt){hl=TreeDepth(bt->lchild); //求左深度hr=TreeDepth(bt->rchild); //求右深度max=hl>hr? hl:hr; //取左右深度的最大值NodeNum=NodeNum+1; //求结点数if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。

实验三二叉排序树的建立和查找一、实验目的1．掌握二叉排序树的建立算法2．掌握二叉排序树查找算法。

二、实验环境操作系统和C语言系统三、预习要求复习二叉排序树的生成及查找算法，编写完整的程序。

四、实验内容实现二叉排序树上的查找算法。

具体实现要求：用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。

五、参考算法#include <stdio.h>#include <stdlib.h>typedef int InfoType;typedef int KeyType; /*假定关键字类型为整数*/typedef struct node /*结点类型*/{KeyType key; /*关键字项*/InfoType otherinfo; /*其它数据域，InfoType视应用情况而定，下面不处理它*/struct node *lchild,*rchild; /*左右孩子指针*/}BSTNode;typedef BSTNode *BSTree; /*BSTree是二叉排序树的类型*/BSTNode *SearchBST(BSTree T,KeyType key){ /*在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NULL*/if(T==NULL||key==T->key) /*递归的终结条件*/return T; /*若T为空，查找失败；否则成功，返回找到的结点位置*/if(key<T->key)return SearchBST(T->lchild,key);elsereturn SearchBST(T->rchild,key); /*继续在右子树中查找*/}void InsertBST(BSTree *T,int key){ /*插入一个值为key的节点到二叉排序树中*/BSTNode *p,*q;if((*T)==NULL){ /*树为空树*/(*T)=(BSTree)malloc(sizeof(BSTNode));(*T)->key=key;(*T)->lchild=(*T)->rchild=NULL;}else{p=(*T);while(p){q=p;if(p->key>key)p=q->lchild;else if(p->key<key)p=q->rchild;else{printf("\n 该二叉排序树中含有关键字为%d的节点!\n",key);return;}}p=(BSTree)malloc(sizeof(BSTNode));p->key=key;p->lchild=p->rchild=NULL;if(q->key>key)q->lchild=p;elseq->rchild=p;}}BSTree CreateBST(void){ /*输入一个结点序列，建立一棵二叉排序树，将根结点指针返回*/BSTree T=NULL; /*初始时T为空树*/KeyType key;scanf("%d",&key); /*读入一个关键字*/while(key){ /*假设key=0是输入结束标志*/ InsertBST(&T,key); /*将key插入二叉排序树T*/scanf("%d",&key); /*读入下一关键字*/}return T; /*返回建立的二叉排序树的根指针*/ }void ListBinTree(BSTree T) /*用广义表示二叉树*/{if(T!=NULL){printf("%d",T->key);if(T->lchild!=NULL||T->rchild!=NULL){printf("(");ListBinTree(T->lchild);if(T->rchild!=NULL)printf(",");ListBinTree(T->rchild);printf(")");}}}void main(){BSTNode *SearchBST(BSTree T,KeyType key);void InsertBST(BSTree *Tptr,KeyType key);BSTree CreateBST();void ListBinTree(BSTree T);BSTree T;BSTNode *p;int key;printf("请输入关键字（输入0为结束标志）：\n");T=CreateBST();ListBinTree(T);printf("\n");printf("请输入欲查找关键字:");scanf("%d",&key);p=SearchBST(T,key);if(p==NULL)printf("没有找到%d！\n",key);elseprintf("找到%d！\n",key);ListBinTree(p);printf("\n");}实验中出现的问题及对问题的解决方案输入数据时，总是不能得到结果，原因是在建立二叉树函数定义中，是对指针的值进行了修改。

二叉树的建立与基本操作二叉树是一种重要的数据结构，它由节点以及节点之间的链接组成。

每个节点最多有两个子节点，被称为左子节点和右子节点。

二叉树的建立和操作是学习数据结构的基础内容，对于计算机科学和算法设计非常重要。

本文将介绍二叉树的建立和一些基本操作，包括插入节点、删除节点、查找节点以及遍历二叉树。

一、二叉树的建立要建立一个二叉树，我们需要先定义一个节点类，并指定节点的左子节点和右子节点。

节点类一般包含一个值以及左子节点和右子节点的指针。

下面是一个示例的节点类的定义：class Nodepublic:int value;Node* left;Node* right;};接下来，我们可以通过创建节点对象并将它们连接起来来构建一棵二叉树。

下面是一个示例的建立二叉树的函数：Node* buildTreNode* root = new Node(;root->value = 1;Node* node1 = new Node(;node1->value = 2;Node* node2 = new Node(;node2->value = 3;Node* node3 = new Node(;node3->value = 4;Node* node4 = new Node(;node4->value = 5;root->left = node1;root->right = node2;node1->left = node3;node1->right = node4;return root;在这个示例中，我们创建了一个根节点root，然后创建了四个子节点node1、node2、node3和node4，并将它们连接到正确的位置上。

二、二叉树的基本操作1.插入节点要插入一个节点，我们首先需要找到插入的位置。

如果节点要插入的位置为null，则直接将节点赋值给该位置；否则，继续找到合适的位置插入节点。

六 运行结果
图（1）
图表1
else if(a==4)
{
printf("层序遍历:");
howmuch(T,2);
}
else if(a==5)
{
printf("总节点数：");
howmuch(T,0);
}
else if(a==6)
{
printf("总叶子数：");
howmuch(T,1);
}
else if(a==7)
{
printf("树的深度：");
二 概要设计
功能实现
1.int CreatBiTree(BiTree &T)用递归的方法先序建立二叉树, 并用链表储存该二叉树
2.int PreTravel(BiTree &T)前序遍历
3.intMidTravel(BiTree &T)中序遍历
4.intPostTravel(BiTree &T)后序遍历
实验三 二叉树的基本运算
一、实验目的
1、使学生熟练掌握二叉树的逻辑结构和存储结构。
2、熟练掌握二叉树的各种遍历算法。
二、实验内容
[问题描述]
建立一棵二叉树，试编程实现二叉树的如下基本操作：
1. 按先序序列构造一棵二叉链表表示的二叉树T；
2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；
5.int Depth(BiTree &T) //计算树的深度
6.inthowmuch(BiTree T,int h)采用树节点指针数组，用于存放遍历到的元素地址，如果有左孩子，存入地址，j加一 ，否则没操作，通过访问数组输出层次遍历的结果。k计算叶子数，j为总节点。