C++二叉树基本操作实验报告

二叉树的建立与遍历实验报告（c语言编写,附源代码）二叉树的建立与遍历实验报告级班年月日姓名学号_1．实验题目建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。

2．需求分析本程序用VC编写，实现建立一棵二叉树的功能，并对其进行遍历（先序、中序、后序），并且打印输出遍历结果。

①输入的形式和输入值的范围：输入二叉树的先序，当其结点为空时，需要输入#。

（输入的先序仅含字母和#）②输出的形式：输出二叉树的先序、中序、后序。

③程序所能达到的功能：实现建立一棵二叉树的功能，并对其进行遍历（先序、中序、后序），并且打印输出遍历结果。

④测试数据：输入数据：输入ABC##DE#G##F###输出结果：二叉树的先序遍历为：ABCDEGF二叉树的中序遍历为：CBEGDFA二叉树的后序遍历为：CGEFDBA3．概要设计1)为了实现上述程序功能，需要定义二叉链表的抽象数据类型：typedef struct BinaryTreeNode{TElemType data;//二叉树结点中的数据域struct BinaryTreeNode *lchild , *rchild; //二叉树结点的左孩子和右孩子指针}BinaryTreeNode ,*BiTree;基本操作：A.void CreateBinaryTree (BiTree &T)初始条件：无操作结果：建立了二叉树。

B. void PreOrder(BiTree T)初始条件：存在一棵二叉树操作结果：先序遍历二叉树，并且输出先序遍历的结果。

C. void MidOrder(BiTree T)初始条件：存在一棵二叉树操作结果：中序遍历二叉树，并且输出中序遍历的结果。

D. void PostOrder(BiTree T)初始条件：存在一棵二叉树操作结果：后序遍历二叉树，并且输出后序遍历的结果。

程序包含5个函数：○1主函数main()○2先序建立二叉树 void CreateBinaryTree (BiTree &T)○3先序遍历二叉树，并且输出先序遍历的结果void PreOrder(BiTree T);○4中序遍历二叉树，并且输出中序遍历的结果void MidOrder(BiTree T);○5序遍历二叉树，并且输出后序遍历的结果void PostOrder(BiTree T); 各函数间关系如下：主函数main()CreateBinaryTree PreOrder MidOrder PostOrder4．详细设计1)二叉链表的定义typedef struct BinaryTreeNode{定义一个树结点的数据域;定义一个该结点的左孩子指针和右孩子指针;}2)void CreateBinaryTree (BiTree &T)//先序建立二叉树{输入一个字符量;if(输入字符== '#') T指针置值为NULL;else{动态申请一个指向二叉树结构体的指针把输入字符赋值给新指针的数据域data;调用CreateBinaryTree(新指针的lchild成员);调用CreateBinaryTree(新指针的rchild成员);}}3)void PreOrder(BiTree T) //先序遍历二叉树{if(T指针不为NULL){输出T的data域;先序遍历左子树;先序遍历右子树;}}4)void MidOrder(BiTree T) //中序遍历二叉树{if(T指针不为NULL){中序遍历左子树;输出T的data域;中序遍历右子树;}}5)void PostOrder(BiTree T) //中序遍历二叉树{if(T指针不为NULL){后序遍历左子树;后序遍历右子树;输出T的data域;}}5．调试分析在编写程序过程中，我将scanf（”%c”,&ch）中的%c写成%d，程序运行了一段时间没有结果，经过检查，发现了这个错误。

实验报告：二叉树第一篇：实验报告：二叉树实验报告二叉树一实验目的1、进一步掌握指针变量，动态变量的含义；2、掌握二叉树的结构特性以及各种存储结构的特点及适用范围。

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

4、熟悉各种存储结构的特征以及如何应用树结构解决具体问题。

二实验原理树形结构是一种应用十分广泛和重要的非线性数据结构，是一种以分支关系定义的层次结构。

在这种结构中，每个数据元素至多只有一个前驱，但可以有多个后继；数据元素之间的关系是一对多的层次关系。

树形结构主要用于描述客观世界中具有层次结构的数据关系，它在客观世界中大量存在。

遍历二叉树的实质是将非线性结构转为线性结构。

三使用仪器，材料计算机 2 Wndows xp 3 VC6.0四实验步骤【问题描述】建立一个二叉树，请分别按前序，中序和后序遍历该二叉树。

【基本要求】从键盘接受输入（按前序顺序），以二叉链表作为存储结构，建立二叉树（以前序来建立），并采用递归算法对其进行前序，中序和后序遍历，将结果输出。

【实现提示】按前序次序输入二叉树中结点的值（一个整数），0表示空树，叶子结点的特征是其左右孩子指针为空。

五实验过程原始记录基本数据结构描述； 2 函数间的调用关系；用类C语言描述各个子函数的算法；附录：源程序。

六试验结果分析将实验结果分析、实验中遇到的问题和解决问题的方法以及关于本实验项目的心得体会，写在实验报告上。

第二篇：数据结构-二叉树的遍历实验报告实验报告课程名：数据结构（C语言版）实验名：二叉树的遍历姓名：班级：学号：时间：2014.11.03一实验目的与要求1.掌握二叉树的存储方法2.掌握二叉树的三种遍历方法3.实现二叉树的三种遍历方法中的一种二实验内容• 接受用户输入一株二叉树• 输出这株二叉树的前根, 中根, 后根遍历中任意一种的顺序三实验结果与分析//*********************************************************** //头文件#include #include //*********************************************************** //宏定义#define OK 1 #define ERROR 0 #define OVERFLOW 0//*********************************************************** typedef struct BiTNode { //二叉树二叉链表存储结构char data;struct BiTNode *lChild,*rChild;}BiTNode,*BiTree;//******************************** *************************** int CreateBiTree(BiTree &T){ //按先序次序输入二叉中树结点的值，空格表示空树//构造二叉链表表示的二叉树T char ch;fflush(stdin);scanf(“%c”,&ch);if(ch==' ')T=NULL;else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))return(OVERFLOW);T->data=ch;Creat eBiTree(T->lChild);CreateBiTree(T->rChild);} return(OK);} //********************************************************* void PreOrderTraverse(BiTree T){ //采用二叉链表存储结构，先序遍历二叉树的递归算法if(T){ printf(“%c”,T->data);PreOrderTraverse(T->lChild);PreOrd erTraverse(T->rChild);} } /***********************************************************/ void InOrderTraverse(BiTree T){ //采用二叉链表存储结构，中序遍历二叉树的递归算法if(T){ InOrderTraverse(T->lChild);printf(“%c”,T->data);InOrderT raverse(T->rChild);} }//*********************************************************** void PostOrderTraverse(BiTree T){ //采用二叉链表存储结构，后序遍历二叉树的递归算法if(T){ PostOrderTraverse(T->lChild);PostOrderTraverse(T->rChild) ;printf(“%c”,T->data);} }//*********************************************************** void main(){ //主函数分别实现建立并输出先、中、后序遍历二叉树printf(“please input your tree follow the PreOrder:n”);BiTNode *Tree;CreateBiTree(Tree);printf(“n先序遍历二叉树:”);PreOrderTraverse(Tree);printf(“n中序遍历二叉树:”);InOrderTraverse(Tree);printf(“n后序遍历二叉树:”);PostOrderTraverse(Tree);}图1:二叉树的遍历运行结果第三篇：数据结构二叉树操作验证实验报告班级：计算机11-2 学号：40 姓名：朱报龙成绩：_________实验七二叉树操作验证一、实验目的⑴ 掌握二叉树的逻辑结构；⑵ 掌握二叉树的二叉链表存储结构；⑶ 掌握基于二叉链表存储的二叉树的遍历操作的实现。

实验七二叉树的基本操作一、【实验目的】1、掌握二叉树的链式存储结构2、掌握二叉树的基本操作（如左结点插入、右结点插入、左子树删除、右子树删除操作）3、掌握二叉树的三种遍历算法。

二、【实验内容】实现二叉树的插入操作，利用先序遍历实现叔的结点打印，并求出二叉树结点个数。

打印的结果为：ABCDFGE以下是部分代码：BiTree.htypedef struct Node{DataType data; /*数据域*/struct Node *leftChild; /*左子树指针*/struct Node *rightChild; /*右子树指针*/}BiTreeNode; /*结点的结构体定义*//*初始化创建二叉树的头结点*/void Initiate(BiTreeNode **root){*root = (BiTreeNode *)malloc(sizeof(BiTreeNode));(*root)->leftChild = NULL;(*root)->rightChild = NULL;}void Destroy(BiTreeNode **root){if((*root) != NULL && (*root)->leftChild != NULL)Destroy(&(*root)->leftChild);if((*root) != NULL && (*root)->rightChild != NULL)Destroy(&(*root)->rightChild);free(*root);}/*若当前结点curr非空，在curr的左子树插入元素值为x的新结点*/ /*原curr所指结点的左子树成为新插入结点的左子树*//*若插入成功返回新插入结点的指针，否则返回空指针*/ BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x){独立完成}/*若当前结点curr非空，在curr的右子树插入元素值为x的新结点*/ /*原curr所指结点的右子树成为新插入结点的右子树*//*若插入成功返回新插入结点的指针，否则返回空指针*/BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x) {}/*若curr非空，删除curr所指结点的左子树*//*若删除成功返回删除结点的双亲结点指针，否则返回空指针*/ BiTreeNode *DeleteLeftTree(BiTreeNode *curr){if(curr == NULL || curr->leftChild == NULL) return NULL;Destroy(&curr->leftChild);curr->leftChild = NULL;return curr;}/*若curr非空，删除curr所指结点的右子树*//*若删除成功返回删除结点的双亲结点指针，否则返回空指针*/ BiTreeNode *DeleteRightTree(BiTreeNode *curr){if(curr == NULL || curr->rightChild == NULL) return NULL;Destroy(&curr->rightChild);curr->rightChild = NULL;return curr;}void PreOrder(BiTreeNode *t, void visit(DataType item)) /*使用visit()函数前序遍历二叉树t*/{}void visit(DataType item){printf("%c ", item);}主程序：#include <stdlib.h>#include <stdio.h>typedef char DataType;#include "BiTree.h"void main(void){ //插入操作，独立完成printf("前序遍历：");//遍历Destroy(&root); }三、【实验源代码】四、【实验结果】五、【实验心得】。

数据结构实验报告二叉树《数据结构与算法》实验报告专业班级姓名学号实验项目实验三二叉树。

实验目的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）编写主函数，调用各个函数，以实现二叉树遍历的基本操作。

[精品]【数据结构】二叉树实验报告二叉树实验报告一、实验目的：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、二叉树的三种遍历算法以及基于遍历的几种操作的实现。

三、实验要求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 # # #。

实验二二叉树的基本操作
一、实验目的与基本要求
掌握二叉树的结构特性，以及存储结构的特点。

掌握在链式存储结构上实现二叉树的基本操作的编程技术。

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

二、实验准备
硬件：一台微机
软件：操作系统和Microsoft VC++ 6.0
三、实验内容
1、编写算法实现完全二叉树的性质5
设对一完全二叉树（含有15个结点个数）有如下说明：
int bt[16]，i；/* 结点编号从1开始*/
任意给定结点i，验证关于完全二叉树的性质，即i的两个子结点为2*i和2*i+1，i的双亲结点为i/2。

2、编写算法实现二叉树三种遍历
（1）功能
建立二叉树，并进行遍历。

（2）输入要求
使用按数组标号法输入的方法构造二叉链表即构造二叉树。

二叉树结点中的数据为字符型，输入元素序号与值顺序为1A，2B，3C，4D，6F, 7G , 输入的两个数据都为0时，结束输入。

（3）测试数据
用三种递归方法输出遍历结果。

概要设计：
模块划分为5个，即（1）用数组表示输入法构造二叉链表,即编写建立二叉树的函数create （2）递归先序、中序、后序遍历3个模块；
（3）主函数。

调用create函数，建立一颗二叉树；然后分别调用先序、中序、后序遍历函数，将二叉树的先序、中序和后序遍历序列输出到屏幕上。

四、实验要求
1．用C完成算法设计和程序设计并上机调试通过。

2．撰写实验报告，提供实验结果和数据。

五、程序实现
写出每个操作的算法（操作过程）
六、程序运行情况
写出输入数据及运行结果
1。

二叉树实验报告二叉树是数据结构中最常见且重要的一种类型。

它由节点组成，每个节点最多有两个子节点，分别称为左节点和右节点。

通过连接这些节点，可以构建一个有序且具有层次结构的树形结构。

本实验报告将介绍二叉树的概念、特点以及常见的操作，同时介绍二叉树在实际应用中的一些典型案例。

一、二叉树的定义和特点二叉树是一种树形结构，它的每个节点至多只有两个子节点。

它的定义可以使用递归的方式进行描述：二叉树要么是一棵空树，要么由根节点和两棵分别称为左子树和右子树的二叉树组成。

二叉树的特点是每个节点最多只有两个子节点。

二、二叉树的创建和操作1.创建二叉树：二叉树可以通过两种方式来创建，一种是使用树的节点类来手动构建二叉树；另一种是通过给定的节点值列表，使用递归的方式构建二叉树。

2.遍历二叉树：二叉树的遍历有三种方式，分别是前序遍历、中序遍历和后序遍历。

a.前序遍历：先遍历根节点，再遍历左子树，最后遍历右子树。

b.中序遍历：先遍历左子树，再遍历根节点，最后遍历右子树。

c.后序遍历：先遍历左子树，再遍历右子树，最后遍历根节点。

3.查找节点：可以根据节点的值或者位置来查找二叉树中的节点。

4.插入节点：可以通过递归的方式在指定位置上插入一个新节点。

5.删除节点：可以通过递归的方式删除二叉树中的指定节点。

三、二叉树的应用案例二叉树在实际应用中有很多重要的用途，下面介绍几个典型的案例。

1.表示文件系统结构：文件系统可以使用二叉树来进行表示，每个文件或文件夹都可以看作是树中一个节点，节点之间的父子关系可以通过左右子树建立连接。

2.实现二叉树：二叉树是一种特殊的二叉树，它要求左子树上的节点值小于根节点的值，右子树上的节点值大于根节点的值。

这种树结构可以快速实现元素的插入、删除和查找等操作。

3.表达式求值：二叉树可以用来表示数学表达式，并且可以通过遍历来对表达式进行求值。

四、实验总结通过本次实验，我们深入了解了二叉树的定义和特点，学会了二叉树的创建和操作方法，以及了解了二叉树在实际应用中的一些典型案例。