实验报告-二叉树的中序遍历

实验报告一，实验目的：·掌握二叉树的链式存储结构；·掌握构造二叉树的方法；·加深对二叉树的中序遍历的理解；二，实验方法：·用递归调用算法中序遍历二叉树。

三，实验步骤：·通过链式存储建立一颗二叉树。

·设计一个算法实现中序遍历二叉树。

四，具体实验步骤：#include<stdio.h>#include<stdlib.h>#define LEFT 0#define RIGHT 1#define TRUE 1#define FALSE 0typedef struct _BTNODE{char c;struct _BTNODE *lchild;struct _BTNODE *rchild;}BTNODE,*PBTNODE;void PrintBTree(PBTNODE p,int depth);void ConstructBTree(PBTNODE p);void InorderTraverse(PBTNODE p);void main(){PBTNODE p;p=(PBTNODE)calloc(1,sizeof(BTNODE));printf("Input the data:");ConstructBTree(p);PrintBTree(p,0);printf("Now InorderTraverse:");InorderTraverse(p);printf("\nPress any key to continue...");getchar();}void PrintBTree(PBTNODE p,int depth){int i;if(p==NULL){return;}else{for(i=0;i<depth;i++){printf("--");}printf(">");printf("%c\n",p->c);PrintBTree(p->lchild,depth+1);PrintBTree(p->rchild,depth+1);}}void ConstructBTree(PBTNODE p){int side;char c;side=LEFT;while(TRUE){scanf("%c",&c);if(c=='\n'){//printf("EOF\n");return;}// printf("%d\n",c);switch(c){case '|':break;case')':return;case',':side=RIGHT;break;case'(':if(side==LEFT){if(p->lchild==NULL){p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE));}ConstructBTree(p->lchild);}else{if(p->rchild==NULL){p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE));}ConstructBTree(p->rchild);}break;default:if(side==LEFT){p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE));p->lchild->c=c;}else{p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE));p->rchild->c=c;}}}}void InorderTraverse(PBTNODE p){if(p==NULL){return;}else{InorderTraverse(p->lchild);printf("[%c] ",p->c);InorderTraverse(p->rchild);}return;}五，实验过程：·输出：Input the date;·输入：1(2(3,4),5(6,7));·输出：Now InorderTraverse:【3】【2】【4】【1】【6】【5】【7】;六，上机实验体会：·体会到熟练掌握各种程序算法的重要性；·通过上机练习，充分理解了链式建立二叉树的算法；·形象的了解二叉树的结构，能够熟练的进行先序，中序，后序遍历二叉树。

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

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

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

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

三、实验环境本实验使用的环境如下：●操作系统: 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、说明：输入数据：1,2,3,0,0,4,5,0,0,6,7,0,0,0,8,9,0,0,10,11,12,0,0,13,0,0,14,0,0其中“0”表示空子树。

输出数据：先序：1,2,3,4,5,6,7,8,9,10,11,12,13,14。

中序：3,2,5,4,7,6,1,9,8,12,11,13,10,14。

后序：3,5,7,6,4,2,9,12,13,11,14,10,8,1。

五、实验仪器与设备计算机，ＪＤＫ，记事本六、实验原理建立一个二叉树，利用递归的方法实现对该二叉树的前序，中序，后序的遍历，并输出遍历结果。

七、实验程序及结果#include<iostream>#include<>#include<>using namespace std;typedef struct btnode{int data;btnode *Lchild,*Rchild;}*Btnode;void Creat(Btnode & t){int ch;cin>>ch;if(ch==0)t=NULL;else{btnode *p=new btnode;p->data=ch;t=p;Creat(t->Lchild);Creat(t->Rchild);}}void Preorder(Btnode & p) {if(p!=NULL){cout<<p->data<<"，";Preorder(p->Lchild);Preorder(p->Rchild);}}void Midorder(Btnode & p) {if(p!=NULL){Midorder(p->Lchild);cout<<p->data<<"，";Midorder(p->Rchild);}}void Folorder(Btnode & p) {if(p!=NULL){Folorder(p->Lchild);Folorder(p->Rchild);cout<<p->data<<"，";}}void main(){btnode *head=new btnode;cout<<"请输入数据：";Creat(head);cout<<"前序遍历：";Preorder(head);cout<<endl;cout<<"中序遍历：";Midorder(head);cout<<endl;cout<<"后序遍历：";Folorder(head);getch();}八、实验体会通过本次试验，让我更深刻的理解了二叉树的性质，在上机的操作过场中，发现了自己平时疏忽的细节，以后再学习过程中会注意。

实验四二叉树运算与遍历实验报告学号-姓名实验时间 2010 年05月24日诚信声明本实验及实验报告所写内容为本人所做，没有抄袭。

实验题目与实验目的题目一：二叉树的遍历运算。

基本要求：在二叉树的二叉链表存储结构基础上，实现二叉树的以下运算：（1）创建二叉树的二叉树链表表示；（2）实现二叉树的先序遍历运算，输出先序遍历运算序列；（3）实现二叉树的中序遍历运算，输出中序遍历运算序列；（4）实现二叉树的后续遍历运算，输出后续遍历运算序列。

实验过程中遇到的主要问题1.根结点忘记申请内存；2.没有添加if(ch=='.')T=NULL;这个作为条件来创造一棵二叉树；3.遍历时没有弄清楚顺序，搞混了先序和中序的顺序。

实验小结1.对结构体的进一步的掌握；2.对递归算法的进一步认识与运用；3.对二叉树的理解由思想到代码实现；4.代码实现思想就是我们应该把问题循环化。

数据结构（自定义数据类型）typedef struct BiTnode{int date;struct BiTnode *lchild, *rchild;}BiTnode,*Bitree; //二叉树链式存储定义主要算法（或算法说明）int createbitree(Bitree &T){char ch;scanf("%c",&ch);if(ch=='.')T=NULL; //条件的判定else{ if(!(T=(Bitree)malloc(sizeof(BiTnode)))) return -1;T->date=ch;createbitree(T->lchild);createbitree(T->rchild);}return 0;} //建立一棵二叉树int preordertraverse(Bitree T){if(T==NULL)return -1;printf("%c",T->date);preordertraverse(T->lchild);preordertraverse(T->rchild);} //先序遍历。

二叉树的建立和遍历的实验报告篇一：二叉树的建立及遍历实验报告实验三：二叉树的建立及遍历【实验目的】（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);}【实验心得】这次实验主要是通过先序序列建立二叉树，和二叉树的先序、中序、后续遍历算法。

实验目的编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历。

实验内容编程序并上机调试运行。

编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历。

编写程序/***********二叉树的遍历**************/#include<stdio.h>#include<stdlib.h>typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;/*************************************************///按先序次序构建的二叉树链表void CreatBiTree(BiTree *T){char ch;if((ch=getchar())==' ')*T=NULL;else{*T=(BiTNode*)malloc(sizeof(BiTNode));if(!(*T))exit(1);(*T)->data=ch;CreatBiTree(&(*T)->lchild);CreatBiTree(&(*T)->rchild);}}/*************************************************/ //先序遍历--递归算法void PreOrderTraverse(BiTree T){if(T){printf("%c",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}/*************************************************/ //中序遍历--递归算法void InOrderTraverse(BiTree T){if(T){InOrderTraverse(T->lchild);printf("%c",T->data);InOrderTraverse(T->rchild);}}/*************************************************/ //后序遍历--递归算法void PostOrderTraverse(BiTree T){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c",T->data);}}/*************************************************/ //main函数void main(){BiTree T;printf("请按先序次序输入二叉树中结点的值，空格字符表示空树:\n" );CreatBiTree(&T);printf("\n");printf("先序遍历为:\n");PreOrderTraverse(T);printf("\n\n");printf("中序遍历为:\n");InOrderTraverse(T);printf("\n\n");printf("后序遍历为:\n");PostOrderTraverse(T);printf("\n\n");getchar();}运行程序：结果分析：按先序输入的二叉树为ABC^^DE^G^^F^^^（^为空格）该二叉树画成树形为：其先序遍历为：ABCDEGF其中序遍历为：CBEGDFA其后序遍历为：CGEFDBA可以看出运行结果是正确的。

二叉树的遍历算法实验报告二叉树的遍历算法实验报告引言：二叉树是计算机科学中常用的数据结构之一，它是由节点组成的层次结构，每个节点最多有两个子节点。

在实际应用中，对二叉树进行遍历是一项重要的操作，可以帮助我们理解树的结构和节点之间的关系。

本文将介绍二叉树的三种遍历算法：前序遍历、中序遍历和后序遍历，并通过实验验证其正确性和效率。

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

具体的实现可以通过递归或者使用栈来实现。

我们以递归方式实现前序遍历算法，并进行实验验证。

实验步骤：1. 创建一个二叉树，并手动构造一些节点和它们之间的关系。

2. 实现前序遍历算法的递归函数，函数的输入为根节点。

3. 在递归函数中，首先访问当前节点，然后递归调用函数遍历左子树，最后递归调用函数遍历右子树。

4. 调用前序遍历函数，输出遍历结果。

实验结果：经过实验，我们得到了正确的前序遍历结果。

这证明了前序遍历算法的正确性。

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

同样，我们可以使用递归或者栈来实现中序遍历算法。

在本实验中，我们选择使用递归方式来实现。

实验步骤：1. 继续使用前面创建的二叉树。

2. 实现中序遍历算法的递归函数，函数的输入为根节点。

3. 在递归函数中，首先递归调用函数遍历左子树，然后访问当前节点，最后递归调用函数遍历右子树。

4. 调用中序遍历函数，输出遍历结果。

实验结果：通过实验，我们得到了正确的中序遍历结果。

这证明了中序遍历算法的正确性。

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

同样，我们可以使用递归或者栈来实现后序遍历算法。

在本实验中，我们选择使用递归方式来实现。

实验步骤：1. 继续使用前面创建的二叉树。

2. 实现后序遍历算法的递归函数，函数的输入为根节点。

3. 在递归函数中，首先递归调用函数遍历左子树，然后递归调用函数遍历右子树，最后访问当前节点。

4. 调用后序遍历函数，输出遍历结果。

二叉树实验报告09信管石旭琳 20091004418一、实验目的：1、理解二叉树的遍历算法及应用2、理解哈夫曼树及其应用。

3、掌握哈夫曼编码思想。

二、实验内容：1、建立二叉树二叉链表2、实现二叉树递归遍历算法（中序、前序、后序）3、求二叉树高度4、求二叉树结点个数5、求二叉树叶子个数6、将序号为偶数的值赋给左子树三、主要程序：#include<stdio.h>#include<stdlib.h>typedef int ElemType;struct BiTNode{ElemType data;struct BiTNode *lch,*rch;}BiTNode,*BiTree;struct BiTNode *creat_bt1();struct BiTNode *creat_bt2();void preorder (struct BiTNode *t);void inorder (struct BiTNode *t);void postorder (struct BiTNode *t);void numbt (struct BiTNode *t);int n,n0,n1,n2;void main(){int k;printf("\n\n\n");printf("\n\n 1.建立二叉树方法1(借助一维数组建立)"); printf("\n\n 2.建立二叉树方法2(先序递归遍历建立)"); printf("\n\n 3.先序递归遍历二叉树");printf("\n\n 4.中序递归遍历二叉树");printf("\n\n 5.后序递归遍历二叉树");printf("\n\n 6.计算二叉树结点个数");printf("\n\n 7.结束程序运行");printf("\n==================================="); do{printf("\n请输入你要执行的操作(1,2,3,4,5,6,7)");scanf("%d",&k);printf("\n");switch(k){case 1:{printf("你选择的是操作1，现用方法1进行建立二叉树\n");BiTree=creat_bt1(); /* 调用性质5建立二叉树算法*/break;}case 2:{printf("你选择的是操作2，现用方法2进行建立二叉树\n");BiTree=creat_bt2(); /* 调用递归建立二叉树算法*/break;}case 3:{printf("你选择的是操作3，现进行先序递归遍历二叉树\n结果为:");preorder(BiTree);break;}case 4:{printf("你选择的是操作4，现进行中序递归遍历二叉树\n结果为:");inorder(BiTree);break;}case 5:{printf("你选择的是操作5，现进行后序递归遍历二叉树\n结果为:");postorder(BiTree);break;}case 6:{ n=0,n0=0,n1=0,n2=0; /*全局变量置0 */printf("你选择的是操作6，现进行计算二叉树结点个数\n结果为:");numbt(BiTree);printf("\n 二叉树结点总数是：%d",n);printf("\n 二叉树叶子结点数是：%d",n0);printf("\n 度为1的结点数是：%d",n1);printf("\n 度为2的结点数是：%d",n2);break;}case 7:{printf("你选择的是操作8，将结束本程序运行，谢谢你的使用，再见！\n");break;}}}while(k>=1&&k<7);}struct BiTNode *creat_bt1(){struct BiTNode *v[50],*p,*t;int i,j;ElemType e; /*输入结点的序号i、结点的数据e */printf("\n i,data=");scanf("%d,%d",&i,&e);while(i!=0&&e!=0){p=(struct BiTNode *)malloc(sizeof(struct BiTNode));p->data=e;p->lch=NULL;p->rch=NULL;v[i]=p;if (i==1) /*序号为1的结点是根*/t=p;else{j=(i+1)/2;if(i%2==0) /*序号为偶数，做左孩子*/v[j]->lch=p;elsev[j]->rch=p;}printf("\n i,data=");scanf("%d,%d",&i,&e);}return t;}struct BiTNode *creat_bt2(){struct BiTNode *t;int e;printf("\n data=");scanf("%d",&e);if(e==0) t=NULL; /*对于0值，不分配新结点*/else{t=(struct BiTNode *)malloc(sizeof(struct BiTNode));t->data=e;t->lch=creat_bt2(); /*左孩子获得新指针值*/t->rch=creat_bt2();}return (t);}void preorder (struct BiTNode *t){if(t){printf("%d ",t->data);preorder(t->lch);preorder(t->rch);}}void inorder (struct BiTNode *t){if(t){inorder(t->lch);printf("%d ",t->data);inorder(t->rch);}}void postorder(struct BiTNode *t){if(t){postorder(t->lch);postorder(t->rch);printf("%d ",t->data);}}void numbt(struct BiTNode *t){if(t){numbt(t->lch);{n++;if(t->lch==NULL&&t->rch==NULL)n0++;if((t->lch==NULL&&t->rch!=NULL)||(t->lch!=NULL&&t->rch==NUL L))n1++;if(t->lch!=NULL&&t->rch!=NULL)n2++;}numbt(t->rch);}}四、测试结果：五、小结：实操后还是会搞不清楚数据域及指针域的定义类型的不同。

实习报告实习内容：二叉树遍历实习时间：2023实习单位：某高校计算机实验室一、实习目的本次实习的主要目的是通过实现二叉树的遍历，加深对二叉树数据结构的理解，掌握二叉树的常见操作，提高编程能力。

二、实习内容1. 理解二叉树的基本概念和性质，包括节点之间的关系、树的深度、高度等。

2. 掌握二叉树的存储结构，包括顺序存储和链式存储。

3. 实现二叉树的前序遍历、中序遍历和后序遍历。

4. 通过实际编程，验证二叉树遍历的正确性。

三、实习过程1. 二叉树的基本概念和性质：二叉树是一种非线性的数据结构，每个节点最多有两个子节点。

节点之间的关系包括父子关系、兄弟关系等。

树的深度是指从根节点到最远叶子节点的最长路径上的边数，高度是指从根节点到最远叶子节点的最长路径上的边数加1。

2. 二叉树的存储结构：二叉树可以用顺序存储结构或链式存储结构表示。

顺序存储结构使用数组来实现，每个节点存储在数组的一个位置中，节点之间的父子关系通过数组下标来表示。

链式存储结构使用链表来实现，每个节点包含数据域和两个指针域，分别指向左子节点和右子节点。

3. 二叉树的遍历：二叉树的遍历是指按照一定的顺序访问树中的所有节点。

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

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

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

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

4. 编程实现：根据二叉树的存储结构和遍历方法，编写C语言程序实现二叉树的前序遍历、中序遍历和后序遍历。

程序中使用递归函数来实现遍历操作，通过建立链式存储结构，验证遍历的正确性。

四、实习心得通过本次实习，我对二叉树的数据结构有了更深入的了解，掌握了二叉树的存储方式和常见操作。

在实现二叉树遍历的过程中，我学会了如何使用递归函数解决问题，提高了编程能力。

同时，通过实际编程验证了二叉树遍历的正确性，增强了对算法理解的信心。

[精品]【数据结构】二叉树实验报告二叉树实验报告一、实验目的：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通过本次实验，我深入理解了二叉树的性质和遍历方式，并掌握了二叉树的基本操作。