二叉树的建立及其遍历实验报告

二叉树的建立与遍历实验报告（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，程序运行了一段时间没有结果，经过检查，发现了这个错误。

【二叉树的建立和遍历实验报告】二叉树的遍历实验心得[题目] 建立二叉树并求指定结点路径、深度、叶子个数和左右子树交换。

[问题描述]要求能够按先序遍历次序输入二叉树中结点的值来构造二叉树T；然后用递归和非递归算法实现二叉树T 的中序遍历；接着编写算法实现求二叉树T中指定结点的路径，即从键盘输入二叉树T 的任一结点，可以输出从根结点到该结点所经历的结点；最后编写二叉树的三个应用算法（求二叉树的深度、求二叉树的叶子结点个数、将二叉树左右子树交换）。

[基本要求]分别建立二叉树存储结构的输入输出函数、输出中序遍历函数、指定节点路径函数、求深度函数、求叶子个数函数和将二叉树左右子树交换函数一、需求与规格说明1、定义二叉树的存储结构，每个结点中设置三个域，即值域、左指针域、右指针域。

要建立二叉树T的链式存储结构，即建立二叉链表。

根据输入二叉树结点的形式不同，建立的方法也不同，本系统采用先序序列递归建立二叉树，建立如下图所示的二叉树。

应该在程序运行窗口的主控菜单后，先选择“1”并回车，紧接着在程序运行窗口中提示信息“输入二叉树的先序序列结点值:”之后，采用以下字符序列：abc@@de@g@@f@@@ （以@替代空格，但是程序中直接输入空格就是，详细见代码注释）作为建立二叉树T的输入字符序列并回车，窗口出现：二叉树的链式存储结构建立完成!图1 二叉树的图形结构2、二叉树的遍历。

本系统采用非递归中序遍历算法进行中序遍历，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。

需要在程序运行窗口的主控菜单中选择“2”并回车，程序运行窗口会出现以下中序遍历序列：该二叉树的中序遍历序列是: cbegdfa3、求二叉树的指定结点路径。

在程序运行窗口的主控菜单中选择“3”并回车，在程序运行窗口中提示信息“输入要求路径的结点值:”输入“g”并回车，会得到结果为：→a→b→d→e→g如果输入“i”并回车，会得到结果为：没有要求的结点！4、求二叉树的深度。

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

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

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

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

三、实验环境本实验使用的环境如下：●操作系统: 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、算法#include <stdio.h>#include <stdlib.h>#define OVERFLOW 0#define OK 1#define ERROR 0typedef struct BiTNode {char data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;BiTree CreateBiTree(BiTree T){scanf("%c",&e);if(e==' ') T=NULL;else {if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=e;T->lchild=CreateBiTree(T->lchild);T->rchild=CreateBiTree(T->rchild);}return T; }/************************前序遍历***********************/ char PreOrderTraverse(BiTree T,char (* Visit)(char e)){if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit)) return OK;return ERROR;}else return OK;}char Visit(char e){printf("%5c",e);return OK;}main(){printf("请输入一颗二叉树，按回车结束：\n");T=CreateBiTree(T);printf("先序遍历的结果：");PreOrderTraverse(T,Visit);}三、调试分析在调这个程序是并没有遇到很大的困难，就是在输入一颗二叉树时，遇到了一点麻烦。

二叉树的建立和遍历的实验报告篇一：二叉树的建立及遍历实验报告实验三：二叉树的建立及遍历【实验目的】（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. 调用后序遍历函数，输出遍历结果。

1．实验题目二叉树的建立与遍历[问题描述]建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。

2．需求分析（1）输入的形式和输入值的范围：以字符形式按先序遍历输入（2）输出的形式：依次按递归先序、中序、后序遍历，非递归先序、中序、后序遍历结果输出(3) 程序所能达到的功能：从键盘接受输入（先序）进行遍历（先序、中序、后序），将遍历结果打印输。

(4) 测试数据：ABCффDEфGффFффф（其中ф表示空格字符）则输出结果为先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA3．概要设计（1）struct btnode{char data; 数据struct btnode *Lchild;左子数指针struct btnode *Rchild; 右子数指针};struct btnode *createbt(struct btnode *bt )初始条件：空二叉树存在操作结果：先序建立二叉树void preOrder(struct btnode *bt)初始条件：二叉树存在递归先序遍历二叉树void preOrder1(struct btnode *bt)初始条件：二叉树存在操作结果：非递归先序遍历void midOrder(struct btnode *bt)初始条件：二叉树存在操作结果：递归中序遍历void midOrder1(struct btnode *bt)初始条件：二叉树存在操作结果：非递归中序遍历void postOrder(struct btnode *bt)初始条件：二叉树存在操作结果：递归后序遍历void postOrder1 (struct btnode *bt)初始条件：二叉树存在操作结果：非递归后序遍历void main() 主函数（2）void main() 主函数{*createbtpreOrderpreOrder1midOrdermidOrder1postOrderpostOrder1}4．详细设计struct btnode{char data;struct btnode *Lchild;struct btnode *Rchild;};struct btnode *createbt(struct btnode *bt ){ 输入结点数据c检查存储空间将c赋给结点参数p递归建立左子树递归建立右子树}void preOrder(struct btnode *bt){判断树是否为空输出根结点数data递归遍历左子树递归遍历右子树}void preOrder1(struct btnode *bt){定义栈，结点参数pWhile(栈或p是否为空){While(p!=null){输出根结点数data将根结点压栈遍历左子树}提取栈顶元素值栈顶元素出栈访问右子树}void midOrder(struct btnode *bt){判断树是否为空递归遍历左子树输出根结点数data递归遍历右子树}void midOrder1(struct btnode *bt){定义栈，结点参数pWhile(栈或p是否为空){While(p!=null){将根结点压栈遍历左子树}提取栈顶元素值输出根结点数data栈顶元素出栈访问右子树}void postOrder(struct btnode *bt){判断树是否为空递归遍历左子树递归遍历右子树输出根结点数data}void postOrder1 (struct btnode *bt){定义栈，结点参数p,prebt入栈While(栈或p是否为空){提取栈顶元素值if判断p是否为空或是pre的根结点输出根结点数data栈顶元素出栈栈顶元素p赋给pre记录else if右结点非空将右结点压栈if左结点将左结点压栈}}void main(){struct btnode *root=NULL;root=createbt(root);preOrder(root); midOrder(root); postOrder(root);preOrder1(root); midOrder1(root)；postOrder1(root);}5.调试分析（1）先序建立二叉树时，虽用到递归建左右子树，但没有把他们赋值给根节点的左右指针，造成二叉树脱节。

二叉树的建立与遍历一、实验目的进一步理解二叉树的逻辑结构和存储结构，掌握二叉树的建立与遍历算法。

二、实验内容1、用二叉链表创建二叉树①输入根结点值；②若左子树不空，则输入左子树，否则输入一个结束符；③若右子树不空，则输入右子树，否则输入一个结束符。

例如：FCA▲▲DB▲▲▲E▲GH▲▲P▲▲其中▲表示结束符2、遍历该二叉树(1) 先序遍历(DLR)若二叉树为空，则结束返回。

否则：①访问根结点；②先序遍历左子树；③先序遍历右子树。

(2) 中序遍历(LDR)若二叉树为空，则结束返回。

否则：①中序遍历左子树；②访问根结点；③中序遍历左子树。

(3) 后序遍历(LRD)若二叉树为空，则结束返回。

否则：①后序遍历左子树；②后序遍历左子树；③访问根结点。

实验思想：根据要求，输入二叉树各结点对应的编号和数值，建立一棵空树，存储相应数值并使左子树和右子树均为空树，根据计算，若编号为偶数则为左子树，若为奇数则为右子树。

最后遍历二叉树。

三、实验算法流程图与程序清单（一）二叉树的建立与先序遍历：1、算法流程图：2、实验清单：{char data;struct node1 *lchild,*rchild;}BTCHINALR;BTCHINALR * createbt( ){ BTCHINALR *q;struct node1 *s[30];int j,i,x;printf("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\n\n");printf("i,x = ");scanf("%d,%c",&i,&x);while(i != 0 && x != '$'){q = (BTCHINALR*)malloc(sizeof(BTCHINALR));q->data = x; q->lchild = NULL; q->rchild = NULL;s[i] = q;if(i != 1){j = i / 2;if(i % 2 == 0) s[j]->lchild = q;else s[j]->rchild = q;}printf("i,x = ");scanf("%d,%c",&i,&x);}return s[1];}void inorder(BTCHINALR *bt){if(bt != NULL){ inorder(bt->lchild);printf("%c ",bt->data);inorder(bt->rchild); }}main( ){ BTCHINALR *bt;char ch;int i;bt = createbt(); i = 1;while(i) {printf("\n先序遍历二叉树(递归按y键，): ");fflush(stdin);scanf("%c",&ch);if(ch == 'y') inorder(bt);printf("\n");}3、实验结果：建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开i,x = 1,li,x = 2,ki,x = 3,yi,x = 4,bi,x =5,si,x = 7,ci,x =11,vi,x = 15,ri,x = 0,$先序遍历二叉树(递归按y键，): yl k b s v y c r（二）、二叉树的建立与中序遍历:1、算法流程图：2、实验清单：{char data;struct node1 *lchild,*rchild;}BTCHINALR;BTCHINALR * createbt( ){ BTCHINALR *q;struct node1 *s[30];int j,i,x;printf("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\n\n");printf("i,x = ");scanf("%d,%c",&i,&x);while(i != 0 && x != '$'){q = (BTCHINALR*)malloc(sizeof(BTCHINALR));q->data = x; q->lchild = NULL; q->rchild = NULL;s[i] = q;if(i != 1){j = i / 2;if(i % 2 == 0) s[j]->lchild = q;else s[j]->rchild = q;}printf("i,x = ");scanf("%d,%c",&i,&x);}return s[1];}void inorder(BTCHINALR *bt){if(bt != NULL){ inorder(bt->lchild);printf("%c ",bt->data);inorder(bt->rchild); }}main( ){ BTCHINALR *bt;char ch;int i;bt = createbt(); i = 1;while(i) {printf("\n先序遍历二叉树(递归按y键，): ");fflush(stdin);scanf("%c",&ch);if(ch == 'y') inorder(bt);printf("\n");}3、实验结果：建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开i,x = 1,li,x = 2,ki,x = 3,yi,x = 4,bi,x =5,si,x = 7,ci,x =11,vi,x = 15,ri,x = 0,$先序遍历二叉树(递归按y键，): yl k b s v y c r四、实验心得体会通过这次实验，锻炼了自己编程的能力，加深了自己对有关知识的理解。

实验四二叉树的建立与遍历【实验目的】掌握二叉树的定义、性质及存储方式，各种遍历算法。

【实验内容】１．采用二叉树链表作为存储构造，完成二叉树的建立，先序、中序和后序遍历的递归操作。

２．分别求所有叶子结点及结点总数的操作。

提示：设计一颗二叉树，输入完全二叉树的先序序列，用#代表虚结点〔空指针〕，如ABD###CE##F##，建立二叉树，求出先序、中序和后序遍历序列，求所有叶子及结点总数。

【程序源代码】#include<stdio.h>#include<stdlib.h>typedef char TElemType;typedef int Status;#define OK 1#define ERROR 0#define OVERFLOW 0typedef struct BiTNode {TElemType data;struct BiTNode *lchild, *rchild;}BiTNode , *BiTree;Status CreateBiTree(BiTree &BT);void CountLeaves(BiTree BT, int &count);int NodeCount(BiTree BT);void PreOrder(BiTree BT);void InOrder(BiTree BT);void PostOrder(BiTree BT);int main(){BiTree BT;int choice,cho;int logo = 1;printf("输入二叉树结点，以'#'为空指针\n"); CreateBiTree(BT);do{printf("\t 1:遍历二叉树\n");printf("\t 2：二叉树总结点数及叶子节点数\n"); printf("\t 3：退出程序\n ");printf("\t 输入选项: ");scanf("%2d",&choice);switch(choice){case 1:printf("1:先序遍历\n");printf("2:中序遍历\n");printf("3:后序遍历\n");scanf("%2d",&cho);switch(cho){case 1:PreOrder(BT);printf("\n");break;case 2:InOrder(BT);printf("\n");break;case 3:PostOrder( BT);printf("\n");break;default:printf("输入错误!\n");}break;case 2:int count;printf("总结点数为:%2d\n", NodeCount(BT)); CountLeaves(BT, count);printf("叶子结点数为:%2d\n", count);break;case 3 :e*it(0);break;default:printf("输入错误!\n");}} while(logo==1);return 0;}Status CreateBiTree(BiTree &BT){char ch;scanf("%c", &ch);if (ch == '#')BT = NULL;else{if (!(BT = (BiTree)malloc(sizeof(BiTNode))))e*it(OVERFLOW); BT->data = ch;CreateBiTree(BT->lchild);CreateBiTree(BT->rchild);}return OK;}void PreOrder(BiTree BT){if (BT != NULL){printf("%c ", BT->data);PreOrder(BT->lchild);PreOrder(BT->rchild);}}void InOrder(BiTree BT){if (BT != NULL){PreOrder(BT->lchild);printf("%c ", BT->data);PreOrder(BT->rchild);}}void PostOrder(BiTree BT){if (BT != NULL){PreOrder(BT->lchild);PreOrder(BT->rchild);printf("%c ", BT->data);}}void CountLeaves(BiTree BT,int &count) {if (BT){if (!BT->lchild && !BT->rchild)count++;CountLeaves(BT->lchild, count); CountLeaves(BT->rchild, count);}}int NodeCount(BiTree BT)//统计总结点数{if (BT == NULL)return 0;elsereturn (NodeCount(BT->lchild) + NodeCount(BT->rchild) + 1);}【运行结果分析】【实验收获与心得】在本次实验中，我对递归这个概念有了较为深刻的认识，对二叉树的建立、遍历也掌握得较为透彻，通过对书本上知识的运用，我对本章的局部知识的掌握程度得到了提高，通过将各个算法运用到编程中，也使我对原本不是太懂的算法的理解有了质的提高。

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

在实际应用中，对二叉树进行遍历是一项重要的操作。

本实验旨在通过实际操作，探索二叉树的遍历算法，并分析其时间复杂度和空间复杂度。

一、实验目的通过实际操作，掌握二叉树的前序遍历、中序遍历和后序遍历算法，并分析它们的特点和适用场景。

二、实验环境本实验使用C++语言进行编程，运行环境为Windows操作系统。

三、实验过程1. 创建二叉树首先，我们需要创建一个二叉树作为实验的基础数据结构。

在本实验中，我们选择手动创建一个简单的二叉树，以便更好地理解遍历算法的实现过程。

2. 前序遍历前序遍历是一种深度优先遍历算法，它的遍历顺序是先访问根节点，然后递归地遍历左子树和右子树。

通过实际操作，我们可以发现前序遍历的结果是根节点在最前面。

3. 中序遍历中序遍历也是一种深度优先遍历算法，它的遍历顺序是先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。

通过实际操作，我们可以发现中序遍历的结果是根节点在中间。

4. 后序遍历后序遍历同样是一种深度优先遍历算法，它的遍历顺序是先递归地遍历左子树和右子树，最后访问根节点。

通过实际操作，我们可以发现后序遍历的结果是根节点在最后面。

5. 分析与总结通过对前序遍历、中序遍历和后序遍历的实际操作，我们可以得出以下结论：- 前序遍历适合于需要先处理根节点的场景，例如树的构建和复制。

- 中序遍历适合于需要按照节点值的大小顺序进行处理的场景，例如搜索二叉树的构建和排序。

- 后序遍历适合于需要先处理叶子节点的场景，例如树的销毁和内存释放。

四、实验结果通过实际操作，我们成功实现了二叉树的前序遍历、中序遍历和后序遍历算法，并得到了相应的遍历结果。

这些结果验证了我们对遍历算法的分析和总结的正确性。

五、实验总结本实验通过实际操作，深入探索了二叉树的遍历算法，并分析了它们的特点和适用场景。

二叉树的创建与遍历的实验总结一、实验目的二叉树是一种重要的数据结构，本实验旨在通过编写程序实现二叉树的创建和遍历，加深对二叉树的理解，并掌握二叉树相关算法。

二、实验原理1. 二叉树的定义：每个节点最多有两个子节点的树结构。

2. 二叉树的遍历方式：前序遍历、中序遍历、后序遍历和层次遍历。

3. 二叉树的创建方式：递归创建和非递归创建。

三、实验内容1. 实现递归创建二叉树：通过输入节点值，按照前序遍历方式逐个创建节点，直到输入结束符号为止。

2. 实现非递归创建二叉树：通过输入节点值，按照层次遍历方式逐个创建节点，直到输入结束符号为止。

3. 实现前序遍历、中序遍历、后序遍历和层次遍历函数，并输出结果。

四、实验步骤1. 定义节点结构体Node，包含数据域和左右子节点指针域。

2. 实现递归创建函数createTreeRecursion()：读入一个字符，如果是结束符号，则返回NULL；否则新建一个节点，并依次读入左右子节点值并分别递归调用createTreeRecursion()函数，将左右子节点指针指向返回值。

3. 实现非递归创建函数createTreeNonRecursion()：读入一个字符，如果是结束符号，则返回NULL；否则新建一个节点，并将其加入队列中。

在队列不为空的情况下，取出队首元素并分别读入左右子节点值并新建节点加入队列中，将左右子节点指针指向新建的节点。

4. 实现前序遍历函数preorderTraversal()：输出当前节点数据，递归调用preorderTraversal()函数遍历左子树和右子树。

5. 实现中序遍历函数inorderTraversal()：递归调用inorderTraversal()函数遍历左子树，输出当前节点数据，再递归调用inorderTraversal()函数遍历右子树。

6. 实现后序遍历函数postorderTraversal()：递归调用postorderTraversal()函数遍历左子树和右子树，输出当前节点数据。

二叉树的遍历实验报告一、需求分析在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就是二叉树的遍历问题。

对二叉树的数据结构进行定义，建立一棵二叉树，然后进行各种实验操作。

二叉树是一个非线性结构，遍历时要先明确遍历的规则，先访问根结点还时先访问子树，然后先访问左子树还是先访问有右子树，这些要事先定好，因为采用不同的遍历规则会产生不同的结果。

本次实验要实现先序、中序、后序三种遍历。

基于二叉树的递归定义，以及遍历规则，本次实验也采用的是先序遍历的规则进行建树的以及用递归的方式进行二叉树的遍历。

二、系统总框图三、各模块设计分析（1）建立二叉树结构建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则来建立的。

本实验用的是先序遍历的规则进行建树。

二叉树用链表存储来实现，因此要先定义一个二叉树链表存储结构。

因此要先定义一个结构体。

此结构体的每个结点都是由数据域data 、左指针域Lchild 、右指针域Rchild 组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。

最后，还需要一个链表的头指针指向根结点。

要注意的是，第一步的时候一定要先定义一个结束标志符号，例如空格键、＃等。

当它遇到该标志时，就指向为空。

建立左右子树时，仍然是调用create（）函数，依此递归进行下去，直到遇到结束标志时停止操作。

（2）输入二叉树元素输入二叉树时，是按上面所确定的遍历规则输入的。

最后，用一个返回值来表示所需要的结果。

（3）先序遍历二叉树当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。

（4）中序遍历二叉树当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。

（5）后序遍历二叉树当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。

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

二叉树的遍历是指按照一定的规则访问二叉树中的所有节点。

本实验旨在通过实际操作，探索二叉树的三种遍历方式：前序遍历、中序遍历和后序遍历，并分析它们的应用场景和性能特点。

二、实验方法1. 实验环境本实验使用Python编程语言进行实现，并在Jupyter Notebook中运行代码。

2. 实验步骤（1）定义二叉树节点类首先，我们定义一个二叉树节点类，该类包含节点值、左子节点和右子节点三个属性。

（2）构建二叉树在主函数中，我们手动构建一个二叉树，包含多个节点，并将其保存为根节点。

（3）实现三种遍历方式通过递归的方式，实现二叉树的前序遍历、中序遍历和后序遍历。

具体实现过程如下：- 前序遍历：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。

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

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

（4）测试遍历结果在主函数中，我们调用实现的三种遍历方式，对构建的二叉树进行遍历，并输出结果。

三、实验结果与分析经过实验，我们得到了二叉树的前序遍历、中序遍历和后序遍历的结果。

以下是我们的实验结果及分析：1. 前序遍历结果前序遍历结果为：A - B - D - E - C - F - G前序遍历的应用场景包括：复制整个二叉树、计算二叉树的深度和宽度等。

前序遍历的时间复杂度为O(n)，其中n为二叉树的节点数。

2. 中序遍历结果中序遍历结果为：D - B - E - A - F - C - G中序遍历的应用场景包括：二叉搜索树的中序遍历可以得到有序的节点序列。

中序遍历的时间复杂度为O(n)，其中n为二叉树的节点数。

3. 后序遍历结果后序遍历结果为：D - E - B - F - G - C - A后序遍历的应用场景包括：计算二叉树的高度、判断二叉树是否对称等。

竭诚为您提供优质文档/双击可除二叉树的建立和遍历的实验报告篇一：二叉树遍历实验报告数据结构实验报告报告题目：二叉树的基本操作学生班级：学生姓名：学号：一．实验目的1、基本要求：深刻理解二叉树性质和各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算；熟练掌握二叉树的遍历算法；。

2、较高要求:在遍历算法的基础上设计二叉树更复杂操作算法；认识哈夫曼树、哈夫曼编码的作用和意义;掌握树与森林的存储与便利。

二.实验学时：课内实验学时：3学时课外实验学时：6学时三．实验题目1．以二叉链表为存储结构，实现二叉树的创建、遍历（实验类型：验证型）1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能：1…建立树2…前序遍历树3…中序遍历树4…后序遍历树5…求二叉树的高度6…求二叉树的叶子节点7…非递归中序遍历树0…结束2）实验要求：在程序中定义下述函数，并实现要求的函数功能：createbinTree(binTreestructnode*lchild,*rchild;}binTnode;元素类型：intcreatebinTree(binTreevoidpreorder(binTreevoidInorder(binTreevoidpostorder(binTreevoidInordern(binTreeintleaf(bi nTreeintpostTreeDepth(binTree2、编写算法实现二叉树的非递归中序遍历和求二叉树高度。

1）问题描述：实现二叉树的非递归中序遍历和求二叉树高度2）实验要求：以二叉链表作为存储结构3)实现过程：1、实现非递归中序遍历代码：voidcbiTree::Inordern(binTreeinttop=0;p=T;do{while(p!=nuLL){stack[top]=p;;top=top+1;p=p->lchild;};if(top>0){top=top-1;p=stack[top];printf("%3c",p->data);p=p->rchild;}}while(p!=nuLL||top!=0);}2、求二叉树高度：intcbiTree::postTreeDepth(binTreeif(T!=nuLL){l=postTreeDepth(T->lchild);r=postTreeDepth(T->rchil d);max=l>r?l:r;return(max+1);}elsereturn(0);}实验步骤：1）新建一个基于consoleApplication的工程，工程名称biTreeTest；2）新建一个类cbiTree二叉树类。

数据结构课内实验报告书一、实验题目：二叉树的创建与遍历二、实验目的：通过本次实验，熟练掌握二叉树的存储结构定义及其遍历算法的实现，学会利用栈编写非递归的遍历算法。

三、实验要求：建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。

要求：从键盘接受扩展先序序列，以二叉链表作为存储结构，建立二叉树，并将遍历结果打印输出。

采用递归和非递归两种方法实现。

四、设计与实现过程（1）存储结构定义typedefcharelemtype;typedefstructNode{elemtypedata;structNode*lchild;structNode*rchild;}BitNode;（2）算法描述Node*creat(Node*pre){chare;Node*head;e=getchar();if(e!=''){head=(Node*)malloc(sizeof(Node));head->data=e;head->Lchild=creat(head);if(head->Lchild==NULL){head->Lflag=1;head->Lchild=pre;}head->Rchild=creat(head);if(pre!=NULL&&pre->Rchild==NULL){ pre->Rflag=1;pre->Rchild=head;}returnhead;}else{returnNULL;}}Node*InPre(Node*root){Node*p;if(root->Lflag==1){p=root->Lchild;}else{for(p=root->Lchild;p->Rflag==0;p=p->Rchild); }returnp;}Node*InNext(Node*root){Node*p;if(root->Rflag==1){p=root->Rchild;}else{for(p=root->Rchild;p->Lflag==0;p=p->Lchild);}returnp;}Node*Infirst(Node*root){Node*p;p=root;if(!p){fprintf(stdout,"n");returnNULL;}while(p->Lflag==0){p=p->Lchild;}returnp;}voidTInOrder(Node*root){Node*p;p=Infirst(root);while(p!=NULL){fprintf(stdout,"%c",p->data);p=InNext(p);}printf("\n");}五、运行结果输入ABECD输出BEADC六、技巧与体会通过实验，锻炼了自己的能力，加深了自己对有关知识的理解。

二叉树的建立和遍历实验报告一、引言（100字）二叉树是一种常见的数据结构，它由根节点、左子树和右子树组成，具有递归性质。

本次实验的目的是了解二叉树的建立过程和遍历算法，以及熟悉二叉树的相关操作。

本实验采用C语言进行编写。

二、实验内容（200字）1.二叉树的建立：通过输入节点的值，逐个建立二叉树的节点，并通过指针连接起来。

2.二叉树的遍历：实现二叉树的三种常用遍历算法，即前序遍历、中序遍历和后序遍历。

三、实验过程（400字）1.二叉树的建立：首先，定义二叉树的节点结构，包含节点值和指向左右子树的指针；然后，通过递归的方式，依次输入节点的值，创建二叉树节点，建立好节点之间的连接。

2.二叉树的前序遍历：定义一个函数，实现前序遍历的递归算法，先输出当前节点的值，再递归遍历左子树和右子树。

3.二叉树的中序遍历：同样，定义一个函数，实现中序遍历的递归算法，先递归遍历左子树，再输出当前节点的值，最后递归遍历右子树。

4.二叉树的后序遍历：同样，定义一个函数，实现后序遍历的递归算法，先递归遍历左子树和右子树，再输出当前节点的值。

四、实验结果（300字）通过实验，我成功建立了一个二叉树，并实现了三种遍历算法。

对于建立二叉树来说，只要按照递归的思路，先输入根节点的值，再分别输入左子树和右子树的值，即可依次建立好节点之间的连接。

建立好二叉树后，即可进行遍历操作。

在进行遍历算法的实现时，我首先定义了一个函数来进行递归遍历操作。

在每一次递归调用中，我首先判断当前节点是否为空，若为空则直接返回；若不为空，则按照特定的顺序进行遍历操作。

在前序遍历中，我先输出当前节点的值，再递归遍历左子树和右子树；在中序遍历中，我先递归遍历左子树，再输出当前节点的值，最后递归遍历右子树；在后序遍历中，我先递归遍历左子树和右子树，再输出当前节点的值。

通过运行程序，我成功进行了二叉树的建立和遍历，并得到了正确的结果。

可以看到，通过不同的遍历顺序，可以获得不同的遍历结果，这也是二叉树遍历算法的特性所在。

问题一：二叉树遍历1.问题描述设输入该二叉树的前序序列为：ABC##DE#G##F##HI##J#K##〔#代表空子树〕请编程完成以下任务：⑴请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列；⑵按层次遍历的方法来输出该二叉树按层次遍历的序列；⑶求该二叉树的高度。

2. 设计描述〔 1 〕二叉树是一种树形构造，遍历就是要让树中的所有节点被且仅被一次，即按一定规律罗列成一个线性队列。

二叉〔子〕树是一种递归定义的构造，包含三个局部：根结点〔 N〕、左子树〔 L〕、右子树〔 R〕。

根据这三个局部的次序对二叉树的遍历发展分类，总共有 6种遍历方案： NLR 、LNR 、LRN 、NRL 、RNL和 LNR 。

研究二叉树的遍历就是研究这 6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即 NLR与 NRL 、LNR与 RNL 、LRN与 RLN ，分别相类似，于是只需研究 NLR 、LNR和 LRN 三种即可，分别称为先序遍历〞、中序遍历〞和后序遍历〞。

采用递归方式就可以容易的实现二叉树的遍历，算法简单且直观。

〔2〕此外，二叉树的层次遍历即按照二叉树的层次构造发展遍历，按照从上到下，同一层从左到右的次序各节点。

遍历算法可以利用队列来实现，开场时将整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的摆布子树入队，当队列完毕时算法完毕。

〔3〕计算二叉树高度也是利用递归来实现：假设一颗二叉树为空，则它的深度为 0 ，否则深度等于摆布子树的最大深度加一。

3 ．源程序1 #include <stdio.h>2 #include <stdlib.h>3 #include <malloc.h>4 #define ElemType char5 struct BTreeNode {6 ElemType data;7 struct BTreeNode* left;8 struct BTreeNode* right;9 };10 void CreateBTree(struct BTreeNode** T)11 {12 char ch;1314 if (ch == '#') *T = NULL;15 else {16 (*T) = malloc(sizeof(struct BTreeNode));17 (*T)->data = ch;18 CreateBTree(&((*T)->left));19 CreateBTree(&((*T)->right));20 }21 }22 void Preorder(struct BTreeNode* T)23 {24 if (T != NULL) {2526 Preorder(T->left);27 Preorder(T->right);28 }29 }30 void Inorder(struct BTreeNode* T)31 {32 if (T != NULL) {33 Inorder(T->left);3435 Inorder(T->right);36 }37 }38 void Postorder(struct BTreeNode* T)39 {40 if (T != NULL) {41 Postorder(T->left);42 Postorder(T->right);4344 }45 }46 void Levelorder(struct BTreeNode* BT)47 {48 struct BTreeNode* p;49 struct BTreeNode* q[30];50 int front=0,rear=0;51 if(BT!=NULL) {52 rear=(rear+1)% 30;53 q[rear]=BT;54 }55 while(front!=rear) {56 front=(front+1)% 30;57 p=q[front];5859 if(p->left!=NULL) {60 rear=(rear+1)% 30;61 q[rear]=p->left;62 }63 if(p->right!=NULL) {64 rear=(rear+1)% 30;65 q[rear]=p->right;66 }67 }68 }69 int getHeight(struct BTreeNode* T)70 {71 int lh,rh;72 if (T == NULL) return 0;73 lh = getHeight(T->left);74 rh = getHeight(T->right);7576 }77 void main(void)78 {79 struct BTreeNode* T;80 CreateBTree(&T);81 前序序列：82 Preorder(T);8384 中序序列：85 Inorder(T);-4.运行结果问题二：哈夫曼编码、译码系统1. 问题描述 对一个ASCII 编码的文本文件中的字符发展哈夫曼编码，生成编码文件； 反过来，可将编码文件译码复原为一个文本文件〔选做〕 。

二叉树的创建与遍历的实验总结引言二叉树是一种重要的数据结构，在计算机科学中有着广泛的应用。

了解二叉树的创建和遍历方法对于数据结构的学习和算法的理解至关重要。

本文将对二叉树的创建和遍历进行实验，并总结相应的经验和思考。

二叉树的定义在开始实验之前，我们首先需要了解二叉树的定义和基本概念。

二叉树是一种每个节点最多拥有两个子节点的树形结构。

每个节点包含一个值和指向其左右子节点的指针。

根据节点的位置，可以将二叉树分为左子树和右子树。

创建二叉树二叉树的创建可以采用多种方法，包括手动创建和通过编程实现。

在实验中，我们主要关注通过编程方式实现二叉树的创建。

1. 递归方法递归是一种常用的创建二叉树的方法。

通过递归，我们可以从根节点开始，逐层创建左子树和右子树。

具体步骤如下：1.创建一个空节点作为根节点。

2.递归地创建左子树。

3.递归地创建右子树。

递归方法的代码实现如下所示：class TreeNode:def __init__(self, value):self.value = valueself.left = Noneself.right = Nonedef create_binary_tree(values):if not values:return None# 使用队列辅助创建二叉树queue = []root = TreeNode(values[0])queue.append(root)for i in range(1, len(values)):node = TreeNode(values[i])# 当前节点的左子节点为空，则将新节点作为左子节点if not queue[0].left:queue[0].left = node# 当前节点的右子节点为空，则将新节点作为右子节点elif not queue[0].right:queue[0].right = node# 当前节点的左右子节点已经齐全，可以从队列中删除该节点queue.pop(0)# 将新节点添加到队列中，下一次循环时可以使用该节点queue.append(node)return root2. 非递归方法除了递归方法，我们还可以使用非递归方法创建二叉树。