二叉树的遍历(先序遍历、中序遍历、后序遍历全)实验报告

一 、实验目的和要求(1)掌握树的相关概念，包括树、节点的度、树的度、分支节点、叶子节点、孩子节点、双亲节 点、树的深度、森林等定义。

(2)掌握树的表示，包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。

(3)掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义。

(4)掌握二叉树的性质。

(5)重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。

(6)重点掌握二叉树的基本运算和各种遍历算法的实现。

(7)掌握线索二叉树的概念和相关算法的实现。

(8)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码的产生方法。

(9)掌握并查集的相关概念和算法。

(10)灵活运用二叉树这种数据结构解决一些综合应用问题。

二、实验内容注：二叉树b 为如图7-123所示的一棵二叉树图7-123+实验7.1 编写一个程序algo7-1.cpp,实现二叉树的各种运算，并在此基础上设计一个程序exp7-1.cpp 完成如下功能：(1)输出二叉树b ;(2)输出H 节点的左、右孩子节点值； (3)输出二叉树b 的深度； (4)输出二叉树b 的宽度； (5)输出二叉树b 的节点个数；(6)输出二叉树b 的叶子节点个数。

实验7.2设计一个程序exp7-2.cpp,实现二叉树的先序遍历、中序遍历和后序遍历和非递归算法， 以及层次变量里的算法。

并对图7-123所示的二叉树b 给出求解结果。

b+ACF GIKL+NM+E+HdJD₄B臣1607-1.CPPif(b?-HULL)re3P4+;Qu[rear]-p-b;Qu[rear].1no=1;while(reart=front){Front++;b=Qu[front]-P;lnum-Qu[front].1no;if(b->Ichildt=NULL)rpar+t;Qu[rear]-p=b->1child;Qu[rear].Ino-lnun+1;if(D->rch11d?=NULL)1/根结点指针入队//根结点的层次编号为1 1/队列不为空1/队头出队1/左孩子入队1/右孩子入队redr+t;qu[rear]-p=b->rchild;Qu[rear].1no-lnun*1;}}nax-0;lnun-1;i-1;uhile(i<=rear){n=0;whdle(i<=rear ge Qu[1].1no==1num)n+t;it+;Inun-Qu[i].1n0;if(n>max)nax=n;}return max;田1607-1.CPPreturn max;}elsereturn o;口×int Modes(BTNode *D) //求二叉树D的结点个数int nun1,nun2;if(b==NULL)returng,else if(b->ichild==NULL&D->rchild==NULL)return 1;else{num1-Hodes(b->Ichild);num2=Nodes(b->rchild);return(num1+nun2+1);LeafNodes(BINode *D) //求二叉树p的叶子结点个数int num1,num2;1f(D==NULL)return 0;else if(b->1chi1d==NULLc& b->rch11d==NULL)return 1;else{num1-LeafModes(b->lchild);num2=LeafNodes(b->rchild);return(nun1+nun2);int程序执行结果如下：xCProrn FlslirosfViu l SudiollyPrjecslro7 LJebuglFoj7 ex<1)输出二叉树：A<B<D,E<H<J,K<L,M<,N>>>>),C<F,G<,I>>)<2)'H’结点：左孩子为J石孩子为K(3)二叉树b的深度：7<4)二叉树b的宽度：4(5)二叉树b的结点个数：14(6)二叉树b的叶子结点个数：6<?>释放二叉树bPress any key to continue实验7 . 2程序exp7-2.cpp设计如下：坠eTPT-2.EPP#include<stdio.h》winclude<malloc.h>deFn Masie 00typde chr ElemTyetypede sruct nde{ElemType data;stuc node *lclldstruct node rchild;》BTHode;extern vod reaeBNodeBTNode extrn void DispBTHode(BTNodeuoid ProrderBTNode *b)if(b?-NULL)- 回1 / 数据元素1 / 指向左孩子1 / 指向右孩子*eb car *str)xb1 / 先序遍历的递归算法1 / 访问根结点/ / 递归访问左子树1 7 递归访问右子树/ / 根结点入栈//栈不为空时循环/ / 退栈并访问该结点/ / 右孩子入栈{》v oidprintf(*c“,b->data); Preorder(b->lchild); Pre0rder(b->rchild);Preorder1(BTNode *b)BTNode xSt[Maxsize],*p;int top=-1;if(b!-HULL)top++;St[top]-b;uhle (op>-)p-St[top];top--;printf("%c“,p->data);if(p->rchild?-HULL)A约e程p7-2.CPPprintF(”后序逅历序列：\n");printf(" 递归算法=");Postorder(b);printf("\n");printf(“非递归算法：“);Postorder1(b);printf("\n");序执行结果如下：xCAPrograFleicsoftVisal SudlyrjecsProj 2Debuzlroj72ex"二叉树b:A(B(D,ECH<J,K(L,M<,N)>))),C(F,GC.I>))层次遍历序列：A B C D E F G H I J K L M N先序遍历序列：递归算法：A B D E H J K L M N C F G I非归算法：A B D E H J K L M N C F G I中序遍历序列：递归算法： D B J H L K M N E A F C G I非递归算法：D B J H L K M N E A F C G I后序遍历序列：递归算法： D J L N M K H E B F I G C A非递归算法：D J L N H K H E B F I G C APress any key to continue臼p7-3.CPP15Pp a t h[p a t h l e n]-b->d a t a;//将当前结点放入路径中p a t h l e n t+;/7路任长度培1Al1Path1(b->ichild,patn,pathlen);1/递归扫描左子树Al1Path1(b->rchild,path,pathlen); //递归扫描右子树pathlen-- ; //恢复环境uoid Longpath(BTNode *b,Elemtype path[1,int pathlen,Elemtype longpath[],int elongpatnien) int i;1f(b==NULL){if(pathlen>longpatnlen) //若当前路径更长，将路径保存在1ongpatn中for(i-pathlen-1;i>-8;i--)longpath[i]=path[1];longpathlen-pathlen;elsepath[pathlen]=b->data; pathlen4; //将当前结点放入路径中//路径长度增1iongPath(b->lchild,path₇pathlen,langpath,longpathien);//递归扫描左子树LongPath(b->rchiid,path,pathien,longpath,longpathien);//递归扫描石子树pathlen--; /7饮其环境oid DispLeaf(BTNode xb)- 口凶uoid DispLeaf(BTNode xb)iE(D!=NULL){ if(b->1child--HULL B& b->rchild--HULL)printf("3c“,b->data);elsepispLeaf(b->ichild);DispLeaf(b->rchild);oid nain()8TNodexb;ElenType patn[Maxsize],longpath[Maxsize];int i.longpathien-U;CreateBTNode(b,"A(B(D,E(H(J,K(L,H(,N))))),C(F,G(,I)))");printf("\n二灾树b:");DispBTNode(b);printf("\n\n*);printf(”b的叶子结点：");DispLeaf(b);printf("\n\n");printf("A11Path:");A11Path(b);printf("m");printf("AiiPath1:n");AliPath1(b.path.);printf("");LongPath(b,path,8,longpath,longpathlen);printf(”第一条量长路径长度=d\n”,longpathlen);printf(”"第一茶最长路径：");for(i=longpathlen;i>=0;i--)printf("c",longpatn[1]);printf("\n\n");。

/*一下总结一些二叉树的常见操作：包括建立二叉树先/中/后序遍历二叉树求二叉树的叶子节点个数求二叉树的单分支节点个数计算二叉树双分支节点个数计算二叉树的高度计算二叉树的所有叶子节点数*/#include<stdio.h> //c语言的头文件#include<stdlib.h>//c语言的头文件stdlib.h千万别写错了#define Maxsize 100/*创建二叉树的节点*/typedef struct BTNode //结构体struct 是关键字不能省略结构体名字可以省略（为无名结构体）//成员类型可以是基本型或者构造形，最后的为结构体变量。

{char data;struct BTNode *lchild,*rchild;}*Bitree;/*使用先序建立二叉树*/Bitree Createtree() //树的建立{char ch;Bitree T;ch=getchar(); //输入一个二叉树数据if(ch==' ') //' '中间有一个空格的。

T=NULL;else{ T=(Bitree)malloc(sizeof(Bitree)); //生成二叉树(分配类型*)malloc(分配元素个数*sizeof(分配类型))T->data=ch;T->lchild=Createtree(); //递归创建左子树T->rchild=Createtree(); //地柜创建右子树}return T;//返回根节点}/*下面先序遍历二叉树*//*void preorder(Bitree T) //先序遍历{if(T){printf("%c-",T->data);preorder(T->lchild);preorder(T->rchild);}} *//*下面先序遍历二叉树非递归算法设计*/void preorder(Bitree T) //先序遍历非递归算法设计{Bitree st[Maxsize];//定义循环队列存放节点的指针Bitree p;int top=-1; //栈置空if(T){top++;st[top]=T; //根节点进栈while(top>-1) //栈不空时循环{p=st[top]; //栈顶指针出栈top--;printf("%c-",p->data );if(p->rchild !=NULL) //右孩子存在进栈{top++;st[top]=p->rchild ;}if(p->lchild !=NULL) //左孩子存在进栈{top++;st[top]=p->lchild ;}}printf("\n");}}/*下面中序遍历二叉树*//*void inorder(Bitree T) //中序遍历{if(T){inorder(T->lchild);printf("%c-",T->data);inorder(T->rchild);}}*//*下面中序遍历二叉树非递归算法设计*/void inorder(Bitree T) //中序遍历{Bitree st[Maxsize]; //定义循环队列，存放节点的指针Bitree p;int top=-1;if(T){p=T;while (top>-1||p!=NULL) //栈不空或者*不空是循环{while(p!=NULL) //扫描*p的所有左孩子并进栈{top++;st[top]=p;p=p->lchild ;}if(top>-1){p=st[top]; //出栈*p节点，它没有右孩子或右孩子已被访问。

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

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

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

四，具体实验步骤：#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】;六，上机实验体会：·体会到熟练掌握各种程序算法的重要性；·通过上机练习，充分理解了链式建立二叉树的算法；·形象的了解二叉树的结构，能够熟练的进行先序，中序，后序遍历二叉树。

⼆叉树遍历（前序、中序、后序、层次、⼴度优先、深度优先遍历）⽬录转载：⼆叉树概念⼆叉树是⼀种⾮常重要的数据结构，⾮常多其他数据结构都是基于⼆叉树的基础演变⽽来的。

对于⼆叉树，有深度遍历和⼴度遍历，深度遍历有前序、中序以及后序三种遍历⽅法，⼴度遍历即我们寻常所说的层次遍历。

由于树的定义本⾝就是递归定义，因此採⽤递归的⽅法去实现树的三种遍历不仅easy理解并且代码⾮常简洁，⽽对于⼴度遍历来说，须要其他数据结构的⽀撑。

⽐⽅堆了。

所以。

对于⼀段代码来说，可读性有时候要⽐代码本⾝的效率要重要的多。

四种基本的遍历思想前序遍历：根结点 ---> 左⼦树 ---> 右⼦树中序遍历：左⼦树---> 根结点 ---> 右⼦树后序遍历：左⼦树 ---> 右⼦树 ---> 根结点层次遍历：仅仅需按层次遍历就可以⽐如。

求以下⼆叉树的各种遍历前序遍历：1 2 4 5 7 8 3 6中序遍历：4 2 7 5 8 1 3 6后序遍历：4 7 8 5 2 6 3 1层次遍历：1 2 3 4 5 6 7 8⼀、前序遍历1）依据上⽂提到的遍历思路：根结点 ---> 左⼦树 ---> 右⼦树，⾮常easy写出递归版本号：public void preOrderTraverse1(TreeNode root) {if (root != null) {System.out.print(root.val+" ");preOrderTraverse1(root.left);preOrderTraverse1(root.right);}}2）如今讨论⾮递归的版本号：依据前序遍历的顺序，优先訪问根结点。

然后在訪问左⼦树和右⼦树。

所以。

对于随意结点node。

第⼀部分即直接訪问之，之后在推断左⼦树是否为空，不为空时即反复上⾯的步骤，直到其为空。

若为空。

则须要訪问右⼦树。

注意。

在訪问过左孩⼦之后。

数据结构实验报告二叉树数据结构实验报告：二叉树引言：数据结构是计算机科学中的重要基础，它为我们提供了存储和组织数据的方式。

二叉树作为一种常见的数据结构，广泛应用于各个领域。

本次实验旨在通过实践，深入理解二叉树的概念、性质和操作。

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

二叉树可以为空树，也可以是由根节点和左右子树组成的非空树。

1.2 基本性质（1）每个节点最多有两个子节点；（2）左子树和右子树是有顺序的，不能颠倒；（3）二叉树的子树仍然是二叉树。

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

在实际应用中，前序遍历常用于复制一颗二叉树或创建二叉树的副本。

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

中序遍历的结果是一个有序序列，因此在二叉搜索树中特别有用。

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

后序遍历常用于计算二叉树的表达式或释放二叉树的内存。

三、二叉树的实现与应用3.1 二叉树的存储结构二叉树的存储可以使用链式存储或顺序存储。

链式存储使用节点指针连接各个节点，而顺序存储则使用数组来表示二叉树。

3.2 二叉树的应用（1）二叉搜索树：二叉搜索树是一种特殊的二叉树，它的左子树上的节点都小于根节点，右子树上的节点都大于根节点。

二叉搜索树常用于实现查找、插入和删除等操作。

（2）堆：堆是一种特殊的二叉树，它满足堆序性质。

堆常用于实现优先队列，如操作系统中的进程调度。

（3）哈夫曼树：哈夫曼树是一种带权路径最短的二叉树，常用于数据压缩和编码。

四、实验结果与总结通过本次实验，我成功实现了二叉树的基本操作，包括创建二叉树、遍历二叉树和查找节点等。

在实践中，我进一步理解了二叉树的定义、性质和应用。

二叉树作为一种重要的数据结构，在计算机科学中有着广泛的应用，对于提高算法效率和解决实际问题具有重要意义。

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

二叉树实验心得(优秀5篇)二叉树实验心得篇1二叉树实验心得在进行二叉树实验的过程中，我不仅掌握了一个重要的数据结构——二叉树，还从中体验到了深入理解一个数据结构的魅力和乐趣。

在实验开始时，我首先学习了二叉树的基本概念，如节点、左子树、右子树等。

我明白了二叉树是一种重要的数据结构，它具有层次结构，每个节点最多有两个子节点，且没有祖先节点的左或右子树中的任何一个节点。

接下来，我学习了二叉树的遍历，包括前序遍历、中序遍历和后序遍历。

通过实验，我明白了这些遍历方式的实现原理，并能够灵活地应用它们。

此外，我还学习了递归和迭代两种方法来实现这些遍历方式，这两种方法各有优点和缺点，我深入了解了它们之间的差异。

在进行实验的过程中，我遇到了一些问题，如递归方法导致的栈溢出，以及中序遍历中的栈和队列的使用。

我通过查阅资料和讨论，解决了这些问题，并从中获得了宝贵的经验。

通过这次实验，我更加深入地理解了二叉树的结构和遍历方式，并能够在实际应用中灵活使用。

我明白了数据结构的重要性，以及深入理解数据结构的过程中的乐趣。

同时，我也学会了如何解决问题，并从中获得了宝贵的经验。

总的来说，这次实验是一个非常有意义的经历，我不仅掌握了新的知识，还锻炼了自己的解决问题的能力。

我相信，这次实验将对我未来的学习和工作产生积极的影响。

二叉树实验心得篇2二叉树实验心得这次实验我们了解了二叉树的基本概念，包括二叉树、结点、左子树、右子树、祖先节点等概念。

通过实验，我们对二叉树的性质有了更深刻的理解，比如二叉树只有左子树或右子树，没有左右子树的情况，即空子树。

在实现二叉树时，我们了解了二叉树节点的定义和插入节点的多种方法，包括先插法、后插法等。

我们还学会了利用二叉树来解决实际问题，比如快速查找等问题。

在实验过程中，我们对二叉树的知识进行了深入探究，收获颇丰。

通过这次实验，我对二叉树有了更深刻的认识，明白了二叉树在计算机科学中的重要性。

同时，我对自己的编程能力也有了新的认识，发现自己可以在理解算法的基础上更好地实现它们。

⼆叉树遍历（前中后序遍历，三种⽅式）⽬录刷题中碰到⼆叉树的遍历，就查找了⼆叉树遍历的⼏种思路，在此做个总结。

对应的LeetCode题⽬如下：，，，接下来以前序遍历来说明三种解法的思想，后⾯中序和后续直接给出代码。

⾸先定义⼆叉树的数据结构如下：//Definition for a binary tree node.struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};前序遍历，顺序是“根-左-右”。

使⽤递归实现：递归的思想很简单就是我们每次访问根节点后就递归访问其左节点，左节点访问结束后再递归的访问右节点。

代码如下：class Solution {public:vector<int> preorderTraversal(TreeNode* root) {if(root == NULL) return {};vector<int> res;helper(root,res);return res;}void helper(TreeNode *root, vector<int> &res){res.push_back(root->val);if(root->left) helper(root->left, res);if(root->right) helper(root->right, res);}};使⽤辅助栈迭代实现：算法为：先把根节点push到辅助栈中，然后循环检测栈是否为空，若不空，则取出栈顶元素，保存值到vector中，之后由于需要想访问左⼦节点，所以我们在将根节点的⼦节点⼊栈时要先经右节点⼊栈，再将左节点⼊栈，这样出栈时就会先判断左⼦节点。

代码如下：class Solution {public:vector<int> preorderTraversal(TreeNode* root) {if(root == NULL) return {};vector<int> res;stack<TreeNode*> st;st.push(root);while(!st.empty()){//将根节点出栈放⼊结果集中TreeNode *t = st.top();st.pop();res.push_back(t->val);//先⼊栈右节点，后左节点if(t->right) st.push(t->right);if(t->left) st.push(t->left);}return res;}};Morris Traversal⽅法具体的详细解释可以参考如下链接：这种解法可以实现O(N)的时间复杂度和O(1)的空间复杂度。

实验四二叉树的操作班级：计算机1002班姓名：唐自鸿学号：201003010207 完成日期：2010.6.14 题目：对于给定的一二叉树，实现各种约定的遍历。

一、实验目的：（1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；（2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想，并学会遍历算法的递归实现和非递归实现。

二、实验内容：构造二叉树，再实现二叉树的先序、中序、后序遍历，最后统计二叉树的深度。

三、实验步骤：(一) 需求分析1. 二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。

因为树的每一个左右子树又是一颗二叉树，所以用递归的方法来建立其左右子树。

二叉树的遍历是一种把二叉树的每一个节点访问并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句来实现。

2．程序的执行命令为：1）构造结点类型，然后创建二叉树。

2）根据提示，从键盘输入各个结点。

3）通过选择一种方式（先序、中序或者后序）遍历。

4）输出结果，结束。

(二)概要设计1.二叉树的二叉链表结点存储类型定义typedef struct Node{DataType data;struct Node *LChild;struct Node *RChild;}BitNode,*BitTree;2.建立如下图所示二叉树：void CreatBiTree(BitTree *bt)用扩展先序遍历序列创建二叉树，如果是当前树根置为空，否则申请一个新节点。

3.本程序包含四个模块1) 主程序模块：2)先序遍历模块3)中序遍历模块4)后序遍历模块4.模块调用关系：主程序模块（三）详细设计1.建立二叉树存储类型//==========构造二叉树=======void CreatBiTree(BitTree *bt)//用扩展先序遍历序列创建二叉树，如果是当前树根置为空，否则申请一个新节点//{char ch;ch=getchar();if(ch=='.')*bt=NULL;else{*bt=(BitTree)malloc(sizeof(BitNode));//申请一段关于该节点类型的存储空间(*bt)->data=ch; //生成根结点CreatBiTree(&((*bt)->LChild)); //构造左子树CreatBiTree(&((*bt)->RChild)); //构造右子树}}2. 编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列1）先序遍历二叉树的递归算法如下：void PreOrder(BitTree root){if (root!=NULL){Visit(root ->data);PreOrder(root ->LChild); //递归调用核心PreOrder(root ->RChild);}}2）中序遍历二叉树的递归算法如下：void InOrder(BitTree root){if (root!=NULL){InOrder(root ->LChild);Visit(root ->data);InOrder(root ->RChild);}}3）后序遍历二叉树的递归算法如下：void PostOrder(BitTree root){if(root!=NULL){PostOrder(root ->LChild);PostOrder(root ->RChild);Visit(root ->data);}}4）计算二叉树的深度算法如下：int PostTreeDepth(BitTree bt) //求二叉树的深度{int hl,hr,max;if(bt!=NULL){hl=PostTreeDepth(bt->LChild); //求左子树的深度hr=PostTreeDepth(bt->RChild); //求右子树的深度max=hl>hr?hl:hr; //得到左、右子树深度较大者return(max+1); //返回树的深度}else return(0); //如果是空树，则返回0}四、调试分析及测试结果1. 进入演示程序后的显示主界面：请输入二叉树中的元素；先序、中序和后序遍历分别输出结果。

《数据结构》实验报告题目: 树和二叉树一、用二叉树来表示代数表达式（一）需求分析输入一个正确的代数表达式, 包括数字和用字母表示的数, 运算符号+ - * / ^ =及括号。

系统根据输入的表达式建立二叉树, 按照先括号里面的后括号外面的, 先乘后除的原则, 每个节点里放一个数字或一个字母或一个操作符, 括号不放在节点里。

分别先序遍历, 中序遍历, 后序遍历此二叉树, 并输出表达式的前缀式, 中缀式和后缀式。

（二）系统设计1.本程序中用到的所有抽象数据类型的定义；typedef struct BiNode //二叉树的存储类型{char s[20];struct BiNode *lchild,*rchild;}BiTNode,*BiTree;2.主程序的流程以及各程序模块之间的层次调用关系, 函数的调用关系图:3. 列出各个功能模块的主要功能及输入输出参数void push(char cc)初始条件: 输入表达式中的某个符号操作结果: 将输入的字符存入buf数组中去BiTree Create_RTree()初始条件: 给出二叉树的定义表达式操作结果：构造二叉树的右子树, 即存储表达式等号右侧的字符组BiTree Create_RootTree()初始条件: 给出二叉树的定义表达式操作结果：构造存储输入表达式的二叉树, 其中左子树存储‘X’, 根节点存储‘：=’void PreOrderTraverse(BiTree T)初始条件: 二叉树T存在操作结果：先序遍历T, 对每个节点调用函数Visit一次且仅一次void InOrderTraverse(BiTree T)初始条件: 二叉树T存在操作结果：中序遍历T, 对每个节点调用函数Visit一次且仅一次void PostOrderTraverse(BiTree T)初始条件: 二叉树T存在操作结果：后序遍历T, 对每个节点调用函数Visit一次且仅一次int main()主函数, 调用各方法, 操作成功后返回0（三）调试分析调试过程中还是出现了一些拼写错误, 经检查后都能及时修正。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

实验5：树（二叉树）（采用二叉链表存储）一、实验项目名称二叉树及其应用二、实验目的熟悉二叉树的存储结构的特性以及二叉树的基本操作。

三、实验基本原理之前我们都是学习的线性结构，这次我们就开始学习非线性结构——树。

线性结构中结点间具有唯一前驱、唯一后继关系，而非线性结构中结点的前驱、后继的关系并不具有唯一性。

在树结构中，节点间关系是前驱唯一而后继不唯一，即结点之间是一对多的关系。

直观地看，树结构是具有分支关系的结构（其分叉、分层的特征类似于自然界中的树）。

四、主要仪器设备及耗材Window 11、Dev-C++5.11五、实验步骤1.导入库和预定义2.创建二叉树3.前序遍历4.中序遍历5.后序遍历6.总结点数7.叶子节点数8.树的深度9.树根到叶子的最长路径10.交换所有节点的左右子女11.顺序存储12.显示顺序存储13.测试函数和主函数对二叉树的每一个操作写测试函数，然后在主函数用while+switch-case的方式实现一个带菜单的简易测试程序，代码见“实验完整代码”。

实验完整代码：#include <bits/stdc++.h>using namespace std;#define MAX_TREE_SIZE 100typedef char ElemType;ElemType SqBiTree[MAX_TREE_SIZE];struct BiTNode{ElemType data;BiTNode *l,*r;}*T;void createBiTree(BiTNode *&T){ElemType e;e = getchar();if(e == '\n')return;else if(e == ' ')T = NULL;else{if(!(T = (BiTNode *)malloc(sizeof (BiTNode)))){cout << "内存分配错误!" << endl;exit(0);}T->data = e;createBiTree(T->l);createBiTree(T->r);}}void createBiTree2(BiTNode *T,int u) {if(T){SqBiTree[u] = T->data;createBiTree2(T->l,2 * u + 1);createBiTree2(T->r,2 * u + 2); }}void outputBiTree2(int n){int cnt = 0;for(int i = 0;cnt <= n;i++){cout << SqBiTree[i];if(SqBiTree[i] != ' ')cnt ++;}cout << endl;}void preOrderTraverse(BiTNode *T) {if(T){cout << T->data;preOrderTraverse(T->l);preOrderTraverse(T->r);}}void inOrderTraverse(BiTNode *T) {if(T){inOrderTraverse(T->l);cout << T->data;inOrderTraverse(T->r);}}void beOrderTraverse(BiTNode *T){if(T){beOrderTraverse(T->l);beOrderTraverse(T->r);cout << T->data;}}int sumOfVer(BiTNode *T){if(!T)return 0;return sumOfVer(T->l) + sumOfVer(T->r) + 1;}int sumOfLeaf(BiTNode *T){if(!T)return 0;if(T->l == NULL && T->r == NULL)return 1;return sumOfLeaf(T->l) + sumOfLeaf(T->r);}int depth(BiTNode *T){if(!T)return 0;return max(depth(T->l),depth(T->r)) + 1;}bool LongestPath(int dist,int dist2,vector<ElemType> &ne,BiTNode *T) {if(!T)return false;if(dist2 == dist)return true;if(LongestPath(dist,dist2 + 1,ne,T->l)){ne.push_back(T->l->data);return true;}else if(LongestPath(dist,dist2 + 1,ne,T->r)){ne.push_back(T->r->data);return true;}return false;}void swapVer(BiTNode *&T){if(T){swapVer(T->l);swapVer(T->r);BiTNode *tmp = T->l;T->l = T->r;T->r = tmp;}}//以下是测试程序void test1(){getchar();cout << "请以先序次序输入二叉树结点的值，空结点用空格表示:" << endl; createBiTree(T);cout << "二叉树创建成功!" << endl;}void test2(){cout << "二叉树的前序遍历为:" << endl;preOrderTraverse(T);cout << endl;}void test3(){cout << "二叉树的中序遍历为:" << endl;inOrderTraverse(T);cout << endl;}void test4(){cout << "二叉树的后序遍历为:" << endl;beOrderTraverse(T);cout << endl;}void test5(){cout << "二叉树的总结点数为：" << sumOfVer(T) << endl;}void test6(){cout << "二叉树的叶子结点数为：" << sumOfLeaf(T) << endl; }void test7(){cout << "二叉树的深度为：" << depth(T) << endl;}void test8(){int dist = depth(T);vector<ElemType> ne;cout << "树根到叶子的最长路径:" << endl;LongestPath(dist,1,ne,T);ne.push_back(T->data);reverse(ne.begin(),ne.end());cout << ne[0];for(int i = 1;i < ne.size();i++)cout << "->" << ne[i];cout << endl;}void test9(){swapVer(T);cout << "操作成功!" << endl;}void test10(){memset(SqBiTree,' ',sizeof SqBiTree);createBiTree2(T,0);cout << "操作成功!" << endl;}void test11(){int n = sumOfVer(T);outputBiTree2(n);}int main(){int op = 0;while(op != 12){cout << "-----------------menu--------------------" << endl;cout << "--------------1：创建二叉树--------------" << endl;cout << "--------------2：前序遍历----------------" << endl;cout << "--------------3：中序遍历----------------" << endl;cout << "--------------4：后序遍历----------------" << endl;cout << "--------------5：总结点数----------------" << endl;cout << "--------------6：叶子节点数--------------" << endl;cout << "--------------7：树的深度----------------" << endl;cout << "--------------8：树根到叶子的最长路径----" << endl;cout << "--------------9：交换所有节点左右子女----" << endl;cout << "--------------10：顺序存储---------------" << endl;cout << "--------------11：显示顺序存储-----------" << endl;cout << "--------------12：退出测试程序-----------" << endl;cout << "请输入指令编号:" << endl;if(!(cin >> op)){cin.clear();cin.ignore(INT_MAX,'\n');cout << "请输入整数!" << endl;continue;}switch(op){case 1:test1();break;case 2:test2();break;case 3:test3();break;case 4:test4();break;case 5:test5();break;case 6:test6();break;case 7:test7();break;case 8:test8();break;case 9:test9();break;case 10:test10();break;case 11:test11();break;case 12:cout << "测试结束!" << endl;break;default:cout << "请输入正确的指令编号!" << endl;}}return 0;}六、实验数据及处理结果测试用例：1.创建二叉树（二叉链表形式）2.前序遍历3.中序遍历4.后序遍历5.总结点数6.叶子结点数7.树的深度8.树根到叶子的最长路径9.交换所有左右子女10.顺序存储七、思考讨论题或体会或对改进实验的建议通过这次实验，我掌握了二叉树的顺序存储和链式存储，体会了二叉树的存储结构的特性，掌握了二叉树的树上相关操作。

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

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

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

二、实验方法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．掌握二叉树的删除节点操作，了解节点删除的细节和方法；4．熟练掌握二叉树的查找节点操作；5．掌握二叉树的遍历方法，能够实现对二叉树的前序、中序、后序、层次遍历。

三、实验原理1．二叉树的创建方法：通过递归的方式，先创建根节点，再依次创建左子树和右子树；2．二叉树的插入节点操作：从根节点开始，根据节点值的大小关系，将待插入节点放到适当的位置；3．二叉树的删除节点操作：首先查找待删除的节点，然后根据其子节点的情况，进行相应的删除处理；4．二叉树的查找节点操作：从根节点开始遍历，根据节点值的大小关系，在左子树或右子树中继续查找，直到找到目标节点或遍历到叶子节点；5．二叉树的遍历方法：前序遍历先访问根节点，再遍历左子树和右子树；中序遍历先遍历左子树，再访问根节点和右子树；后序遍历先遍历左子树和右子树，再访问根节点；层次遍历按层次逐个访问节点。

四、实验过程1．创建二叉树：首先，定义二叉树的节点类，包含节点值和左右子节点；然后，通过递归的方式创建根节点、左子树和右子树。

2．插入节点：要插入一个节点，首先需要找到插入位置。

如果待插入节点大于当前节点的值，则插入到右子树中，否则插入到左子树中。

如果节点为空，则表示找到了插入位置。

3．删除节点：删除节点有以下几种情况：(1) 待删除节点为叶子节点：直接删除即可；(2) 待删除节点只有一个子节点：用子节点替换待删除节点的位置；(3) 待删除节点有两个子节点：找到待删除节点的后继节点（右子树的最左下角节点），用后继节点替换待删除节点的位置。

竭诚为您提供优质文档/双击可除二叉树的建立和遍历的实验报告篇一：二叉树遍历实验报告数据结构实验报告报告题目：二叉树的基本操作学生班级：学生姓名：学号：一．实验目的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二叉树类。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

二叉树的遍历实验报告一、实验目的1.了解二叉树的基本概念和性质；2.理解二叉树的遍历方式以及它们的实现方法；3.学会通过递归和非递归算法实现二叉树的遍历。

二、实验内容1.二叉树的定义在计算机科学中，二叉树是一种重要的数据结构，由节点及它们的左右儿子组成。

没有任何子节点的节点称为叶子节点，有一个子节点的节点称为一度点，有两个子节点的节点称为二度点。

二叉树的性质：1.每个节点最多有两个子节点；2.左右子节点的顺序不能颠倒，左边是父节点的左子节点，右边是父节点的右子节点；3.二叉树可以为空，也可以只有一个根节点；4.二叉树的高度是从根节点到最深叶子节点的层数；5.二叉树的深度是从最深叶子节点到根节点的层数；6.一个深度为d的二叉树最多有2^(d+1) -1个节点，其中d>=1；7.在二叉树的第i层上最多有2^(i-1)个节点，其中i>=1。

2.二叉树的遍历方式二叉树的遍历是指从根节点出发，按照一定的顺序遍历二叉树中的每个节点。

常用的二叉树遍历方式有三种：前序遍历、中序遍历和后序遍历。

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

递归算法：利用函数调用，递归实现二叉树的遍历；非递归算法：利用栈或队列，对二叉树进行遍历。

三、实验步骤1.创建二叉树数据结构并插入节点；2.实现二叉树的前序遍历、中序遍历、后序遍历递归算法；3.实现二叉树的前序遍历、中序遍历、后序遍历非递归算法；4.测试算法功能。

四、实验结果1.创建二叉树数据结构并插入节点为了测试三种遍历方式的算法实现，我们需要创建一个二叉树并插入节点，代码如下：```c++//定义二叉树节点struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};递归算法是实现二叉树遍历的最简单方法，代码如下：```c++//前序遍历非递归算法vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> s;vector<int> res;if (!root) return res;s.push(root);while (!s.empty()) {TreeNode* tmp = s.top();s.pop();res.push_back(tmp->val);if (tmp->right) s.push(tmp->right);if (tmp->left) s.push(tmp->left);}return res;}4.测试算法功能return 0;}```测试结果如下：preorderTraversal: 4 2 1 3 6 5 7inorderTraversal: 1 2 3 4 5 6 7postorderTraversal: 1 3 2 5 7 6 4preorderTraversalNonRecursive: 4 2 1 3 6 5 7inorderTraversalNonRecursive: 1 2 3 4 5 6 7postorderTraversalNonRecursive: 1 3 2 5 7 6 4本次实验通过实现二叉树的递归和非递归遍历算法，加深了对二叉树的理解，并熟悉了遍历算法的实现方法。