2012《数据结构》上机实验报告 二叉树遍历
- 格式：doc
- 大小：200.00 KB
- 文档页数：10
下载文档原格式
合集下载
数据结构二叉树遍历实验报告
数据结构二叉树遍历实验报告数据结构二叉树遍历实验报告一、引言本文档旨在详细介绍二叉树遍历的实验过程和结果。
二叉树是一种在计算机科学领域常用的数据结构，通过遍历二叉树可以获取树中的所有节点数据。
本实验将分别介绍前序遍历、中序遍历和后序遍历这三种常见的遍历方法。
二、实验目的本实验的目的是通过实际操作，加深对二叉树遍历方法的理解，并验证这些遍历方法的正确性和效率。
三、实验环境本实验使用的环境如下：●操作系统: 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数据]六、实验分析通过实验结果可以看出，不同的遍历顺序得到的节点顺序也不同。
前序遍历先访问根节点，中序遍历先遍历左子树，后序遍历先遍历右子树。
根据需要，可以选择合适的遍历方法来处理二叉树的节点数据。
七、结论本实验验证了前序遍历、中序遍历和后序遍历的正确性，并且对比了它们的不同。
数据结构实验报告二叉树
return s;
}
void dispbtnode1(btnode *b)
{
btnode *st[maxsize],*p;
int level[maxsize][2],top=-1,n,i,width=4;
char type;
if(b!=NULL)
{
top++;
st[top]=b;
level[top][0]=width;
level[top][0]=n+width;
level[top][1]=1;
}
if(p->lchild!=NULL)
{
top++;
st[top]=p->lchild;
level[top][0]=n+width;
level[top][1]=0;
}
}
}
}
2）先序，中序、后序遍历功能实现，因为想自己更能读懂理解程序，没有使用递归算法。
}
btnode *rchildnode(btnode *p)
{
return p->rchild ;
}
btnode * revers(btnode *b)//交换左右子树
{
if(b!=NULL)
{
if(b->rchild !=NULL||b->lchild !=NULL)
{
btn;lchild );
（3）根据二叉树的基本运算，设计先序遍历和中序遍历（或者中序遍历和后序遍历），确定二叉树的算法。
（4）在不改变原有二叉树结构的条件下，将二叉树左右孩子进行交换，并采用凹入表示法和括号表示法输出原有二叉树及交换子树后的二叉树。
}
void dispbtnode1(btnode *b)
{
btnode *st[maxsize],*p;
int level[maxsize][2],top=-1,n,i,width=4;
char type;
if(b!=NULL)
{
top++;
st[top]=b;
level[top][0]=width;
level[top][0]=n+width;
level[top][1]=1;
}
if(p->lchild!=NULL)
{
top++;
st[top]=p->lchild;
level[top][0]=n+width;
level[top][1]=0;
}
}
}
}
2）先序，中序、后序遍历功能实现，因为想自己更能读懂理解程序，没有使用递归算法。
}
btnode *rchildnode(btnode *p)
{
return p->rchild ;
}
btnode * revers(btnode *b)//交换左右子树
{
if(b!=NULL)
{
if(b->rchild !=NULL||b->lchild !=NULL)
{
btn;lchild );
（3）根据二叉树的基本运算，设计先序遍历和中序遍历（或者中序遍历和后序遍历），确定二叉树的算法。
（4）在不改变原有二叉树结构的条件下，将二叉树左右孩子进行交换，并采用凹入表示法和括号表示法输出原有二叉树及交换子树后的二叉树。
数据结构二叉树实验报告总结
数据结构二叉树实验报告总结一、实验目的本次实验的主要目的是通过对二叉树的学习和实践，掌握二叉树的基本概念、性质和遍历方式，加深对数据结构中树形结构的理解。
二、实验内容1. 二叉树的基本概念和性质在本次实验中，我们首先学习了二叉树的基本概念和性质。
其中，二叉树是由节点组成的有限集合，并且每个节点最多有两个子节点。
同时，我们还学习了二叉树的高度、深度、层数等概念。
2. 二叉树的遍历方式在了解了二叉树的基本概念和性质之后，我们开始学习如何遍历一个二叉树。
在本次实验中，我们主要学习了三种遍历方式：前序遍历、中序遍历和后序遍历。
其中，前序遍历指先访问节点自身再访问左右子节点；中序遍历指先访问左子节点再访问自身和右子节点；后序遍历指先访问左右子节点再访问自身。
3. 二叉搜索树除了以上内容之外，在本次实验中我们还学习了一种特殊的二叉树——二叉搜索树。
二叉搜索树是一种特殊的二叉树，它的每个节点都满足左子节点小于该节点，右子节点大于该节点的性质。
由于这个性质，二叉搜索树可以被用来进行快速查找、排序等操作。
三、实验过程1. 实现二叉树的遍历方式为了更好地理解和掌握二叉树的遍历方式，我们首先在编程环境中实现了前序遍历、中序遍历和后序遍历。
在代码编写过程中，我们需要考虑如何递归地访问每个节点，并且需要注意访问顺序。
2. 实现二叉搜索树为了更好地理解和掌握二叉搜索树的特性和操作，我们在编程环境中实现了一个简单的二叉搜索树。
在代码编写过程中，我们需要考虑如何插入新节点、删除指定节点以及查找目标节点等操作。
3. 实验结果分析通过对代码运行结果进行分析，我们可以清晰地看到每个遍历方式所得到的结果以及对应的顺序。
同时，在对二叉搜索树进行操作时，我们也可以看到不同操作所产生的不同结果。
四、实验总结通过本次实验，我们进一步加深了对二叉树的理解和掌握，学习了二叉树的遍历方式以及二叉搜索树的特性和操作。
同时，在编程实践中，我们也进一步熟悉了代码编写和调试的过程。
数据结构实验报告(二叉树的基本操作)
else if((root->LChild==NULL)&&(root->RChild==NULL)) LeafNum=1;
else LeafNum=LeafCount(root->LChild)+LeafCount(root->RChild);
//叶子数为左右子树数目之和
return LeafNum;
printf("\n菜单选择\n\n");
printf(" 1.树状输出二叉树2.先序遍历二叉树\n");
printf(" 3.中序遍历二叉树4.后序遍历二叉树\n");
printf(" 5.输出叶子结点6.输出叶子结点的个数\n");
printf(" 7.输出二叉树的深度8.退出\n");
printf("\n----------------------------------------------------------------------\n");
{
printf("\n\n");
j=j+1; k=0;
while(k<nlocate)
{
printf(" ");
k++;
}
}
while(k<(nlocate-1))
{
printf(" ");
k++;
}
printf("%c",bt->data );
q.front=q.front+1;
if(bt->LChild !=NULL)//存在左子树，将左子树根节点入队列
else LeafNum=LeafCount(root->LChild)+LeafCount(root->RChild);
//叶子数为左右子树数目之和
return LeafNum;
printf("\n菜单选择\n\n");
printf(" 1.树状输出二叉树2.先序遍历二叉树\n");
printf(" 3.中序遍历二叉树4.后序遍历二叉树\n");
printf(" 5.输出叶子结点6.输出叶子结点的个数\n");
printf(" 7.输出二叉树的深度8.退出\n");
printf("\n----------------------------------------------------------------------\n");
{
printf("\n\n");
j=j+1; k=0;
while(k<nlocate)
{
printf(" ");
k++;
}
}
while(k<(nlocate-1))
{
printf(" ");
k++;
}
printf("%c",bt->data );
q.front=q.front+1;
if(bt->LChild !=NULL)//存在左子树，将左子树根节点入队列
数据结构实习报告---二叉树
数据结构实习报告---二叉树二叉树一、需求分析1、设计任务建立一棵二叉树，数据以字符串形式从键盘输入。
在此二叉树上完成：（1）前序、中序、后序遍历（2）求出叶子数（3）求树高（4）左右子树交换，输出交换后的前序、中序遍历序列选做：（1）给出非递归的后序遍历（2）扩充为中序线索树，写出非递归的中序遍历（3）在两个数组中分别有前序和中序遍历序列，试建立该二叉树2、输入的形式和输出值的范围二叉树的建立：本程序的二叉树的建立函数时根据二叉树的前序排列生成的，但是其中子树为空地方用特殊符号“＊”代替。
二叉树的输出值的范围：二叉树的输出是把二叉树各节点的值按遍历顺序输出的，本程序各节点的数据类型为字符型(可以在编译预处理修改)。
3、输出的形式二叉树的输出是根据二叉树的遍历顺序输出的（包括前序、中序和后序三种）把各节点地值输出。
4、程序所能达到的功能本程序能够实现对二叉树的一些简单操作，例如二叉树的各种遍历(包括二叉树的前序、中序和后序的递归遍历以及非递归遍历)、求二叉树的叶子数和高以及二叉树的左右子树交换。
5、测试数据(1)当为二叉树一时：(2)当为二叉树二时：二、概要设计1、树结点结构体typedef char DataType; struct TreeNode{DataType data;TreeNode *lchild,*rchild;};2、棧结点结构体struct StackNode{TreeNode* T_N;int Flag;};3、主程序流程主程序开始；调用CreateBiTree(TreeNode *&Tree)函数建立二叉树；依次调用前序、中序和后序递归及非递归遍历二叉树；计算二叉树的树叶和树高；交换二叉树的左右子树；依次用前序、中序和后序的递归和非递归方法遍历二叉树；主程序结束；三、详细设计(1)递归遍历的实现(以前序为例)；算法为：先访问根结点，然后递归的访问左子树和右子树。
数据结构二叉树遍历实验报告
数据结构二叉树遍历实验报告正文：1.实验目的本实验旨在实现二叉树的四种遍历方式：前序遍历、中序遍历、后序遍历和层次遍历，并对其进行验证和性能评估。
2.实验原理2.1 二叉树的定义二叉树是一种特殊的树状结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。
2.2 二叉树的遍历方式2.2.1 前序遍历前序遍历的顺序是先访问根节点，然后递归地遍历左子树和右子树。
2.2.2 中序遍历中序遍历的顺序是先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。
2.2.3 后序遍历后序遍历的顺序是先递归地遍历左子树和右子树，最后访问根节点。
2.2.4 层次遍历层次遍历按照二叉树的层次从上到下、从左到右的顺序遍历节点。
3.实验内容3.1 实现二叉树的数据结构首先，我们需要定义二叉树的数据结构。
二叉树节点应包含键值和左右子节点的指针。
3.2 实现二叉树的各种遍历方式接下来，我们实现四种遍历方式：前序遍历、中序遍历、后序遍历和层次遍历。
针对每种遍历方式，编写相应的算法实现逻辑。
3.3 实验验证和性能评估使用已实现的算法，对一棵二叉树进行各种遍历方式操作，并将结果输出。
验证输出结果与预期结果是否一致。
同时，记录每种遍历方式的算法时间复杂度和空间复杂度，并进行性能评估。
4.实验结果与分析对于给定的二叉树，分别进行了前序遍历、中序遍历、后序遍历和层次遍历操作，并得到了相应的输出结果。
结果与预期相符。
通过对算法的时间复杂度和空间复杂度的计算和分析，可以看出各种遍历方式的效率和资源消耗情况。
5.结论本实验成功实现了二叉树的四种遍历方式，并验证了其正确性。
同时，对这些遍历方式的性能进行了评估，为后续使用二叉树进行数据操作提供了参考。
附件：无法律名词及注释：- N/A。
数据结构二叉树实验报告
实验三二叉树的遍历一、实验目的１、熟悉二叉树的结点类型和二叉树的基本操作。
２、掌握二叉树的前序、中序和后序遍历的算法。
3、加深对二叉树的理解，逐步培养解决实际问题的编程能力。
二、实验环境运行Ｃ或VC++的微机。
三、实验内容1、依次输入元素值，以链表方式建立二叉树，并输出结点的值。
2、分别以前序、中序和后序遍历二叉树的方式输出结点内容。
四、设计思路1. 对于这道题，我的设计思路是先做好各个分部函数，然后在主函数中进行顺序排列，以此完成实验要求2．二叉树采用动态数组3.二叉树运用9个函数，主要有主函数、构建空二叉树函数、建立二叉树函数、访问节点函数、销毁二叉树函数、先序函数、中序函数、后序函数、范例函数，关键在于访问节点五、程序代码#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define OK 1#define ERROR 0typedef struct TNode//结构体定义{-int data; //数据域struct TNode *lchild,*rchild; // 指针域包括左右孩子指针}TNode,*Tree;void CreateT(Tree *T)//创建二叉树按,依次输入二叉树中结点的值{int a;scanf("%d",&a);if(a==00) // 结点的值为空*T=NULL;else // 结点的值不为空{*T=(Tree)malloc(sizeof(TNode));if(!T){printf("分配空间失败！！TAT");exit(ERROR);}(*T)->data=a;CreateT(&((*T)->lchild)); // 递归调用函数，构造左子树CreateT(&((*T)->rchild)); // 递归调用函数，构造右子树}}void InitT(Tree *T)//构建空二叉树{T=NULL;}void DestroyT(Tree *T)//销毁二叉树{if(*T) // 二叉树非空{DestroyT(&((*T)->lchild)); // 递归调用函数，销毁左子树DestroyT(&((*T)->rchild)); // 递归调用函数，销毁右子树free(T);T=NULL;}}void visit(int e)//访问结点{printf("%d ",e);}-void PreOrderT(Tree *T,void(*visit)(int))//先序遍历T{if(*T) // 二叉树非空{visit((*T)->data); // 先访问根结点PreOrderT(&((*T)->lchild),visit); // 递归调用函数，先序遍历左子树PreOrderT(&((*T)->rchild),visit); // 递归调用函数，先序遍历右子树}}void InOrderT(Tree *T,void(*visit)(int)){if(*T){InOrderT(&((*T)->lchild),visit); // 递归调用函数，中序遍历左子树visit((*T)->data); // 访问根结点InOrderT(&((*T)->rchild),visit); // 递归调用函数，中序遍历右子树}}void PostOrderT(Tree *T,void(*visit)(int)){if(*T){PostOrderT(&((*T)->lchild),visit); // 递归调用函数,后序遍历左子树PostOrderT(&((*T)->rchild),visit); // 递归调用函数,序遍历右子树visit((*T)->data); // 访问根结点}}void example(){int i;printf("如果你想建立如图所示的二叉树\n");printf("\n");printf(" 1 \n");printf(" / \\ \n");printf(" 3 3 \n");printf(" / \\ \\ \n");printf(" 4 5 7 \n");printf("\n");printf("请输入：1 3 4 00 00 5 00 00 3 00 7 00 00\n");printf("\n按先序次序输入二叉树中结点的值(输入00表示节点为空)\n");for(i=0;i<71;i++)printf("*");printf("\n");}int main (){Tree T;printf("**************欢迎使用！**************潘俊达\n"); example();printf("\n请输入所要建立的二叉树:\n");CreateT(&T);InitT(&T);int i;printf("先序遍历二叉树：\n");PreOrderT(&T,visit);printf("\n");printf("\n中序遍历二叉树：\n");InOrderT(&T,visit);printf("\n");printf("\n后序遍历二叉树：\n");PostOrderT(&T,visit);printf("\n");system("PAUSE");return 0;}六、程序截图1.范例函数显示，并输入先序二叉树节点值2．先序遍历二叉树3.中序遍历二叉树3.后序遍历二叉树。
数据结构实验报告-二叉树的实现与遍历
《数据结构》第六次实验报告学生姓名学生班级学生学号指导老师一、实验内容1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。
2) 输出树的深度，最大元，最小元。
二、需求分析遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。
递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。
直到递归全部结束。
下面重点来讲述非递归方法：首先介绍先序遍历：先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。
具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。
再次介绍中序遍历：中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。
具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。
如此循环直至结点指针和栈均为空，遍历结束。
最后介绍后序遍历：后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。
数据结构实验报告-线索二叉树的遍历
线索二叉树的遍历--《数据结构实验报告》1.基本思想对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。
线索二叉树的建立就是在二叉树的基础上进行线索化。
本次实验建立了前序线索二叉树，中序线索二叉树，和后序线索二叉树，并分别对前中序线索二叉树进行了前序，中序，后序遍历，对后序线索二叉树进行了后序遍历。
2.用到的数据结构定义节点元素：Left, right为普通二叉树的左右孩子，value为该节点元素的值，Ltag, Rtag为左右线索化指向节点。
在某些遍历中会用到栈结构，用来存储当前可以路过，但是在以后却访问不到的点。
3.基本操作实现1.前，中，后序二叉树的线索化：线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，前驱和后继的信息是在遍历过程中才能得到，故线索化的过程即为在遍历过程中修改空指针的过程。
前，中，序线索化的过程相似，只是修改NULL和递归遍历左右孩子的顺序导致产生不同。
2.前序线索二叉树的前序遍历：因为前序线索二叉树建立的过程就是按照前序遍历的思想线索化的，所以按照一直向左走，直到左边的指向为线索时停止，开始向右指(不管是线索还是树枝)，依次递归得到答案。
3.前序线索二叉树的中序遍历：根据前序线索化的二叉树在中序遍历时如果按照前序遍历的方式会出现上面的一些点永远无法被访问到，所以，增加一个数据结构—栈。
在一直向左遍历的时候，将这些节点入栈，在回访时，依次取出这些点，在进入到取出点的右孩子，实现中序遍历。
4.前序线索二叉树的后序遍历：思想和中序遍历差不多，但是是将栈中元素的右孩子遍历完成后在输出该元素的值，实现后序遍历。
5.中序线索二叉树的前序遍历：中序的前序遍历比较简单，和前序线索的前序遍历很像，但是在判断左右孩子是否是线索时，需进行循环遍历判断，不是简单的if。
数据结构二叉树遍历实验报告简版
数据结构二叉树遍历实验报告数据结构二叉树遍历实验报告1. 实验目的本实验旨在通过实现二叉树的前序、中序和后序遍历算法，加深对二叉树遍历的理解，并验证算法的正确性。
2. 实验原理2.1 二叉树二叉树是一种特殊的树状数据结构，它的每个节点最多只能有两个子节点。
二叉树可以为空树，也可以是由根节点、左子树和右子树组成的非空树。
2.2 遍历算法二叉树的遍历算法包括前序遍历、中序遍历和后序遍历。
- 前序遍历：先访问根节点，然后依次递归访问左子树和右子树。
- 中序遍历：先递归访问左子树，然后访问根节点，最后递归访问右子树。
- 后序遍历：先递归访问左子树，然后递归访问右子树，最后访问根节点。
3. 实验过程3.1 数据结构设计首先，我们需要设计表示二叉树的数据结构。
在本次实验中，二叉树的每个节点包含三个成员变量：值、左子节点和右子节点。
我们可以使用面向对象编程语言提供的类来实现。
具体实现如下：```pythonclass TreeNode:def __init__(self, val=0, left=None, right=None): self.val = valself.left = leftself.right = right```3.2 前序遍历算法前序遍历算法的实现主要包括以下步骤：1. 若二叉树为空，则返回空列表。
2. 创建一个栈，用于存储遍历过程中的节点。
3. 将根节点入栈。
4. 循环执行以下步骤，直到栈为空：- 弹出栈顶节点，并将其值添加到结果列表中。
- 若当前节点存在右子节点，则将右子节点压入栈。
- 若当前节点存在左子节点，则将左子节点压入栈。
具体实现如下：```pythondef preorderTraversal(root):if not root:return []stack = []result = []stack.append(root)while stack:node = stack.pop()result.append(node.val)if node.right:stack.append(node.right)if node.left:stack.append(node.left)return result```3.3 中序遍历算法中序遍历算法的实现主要包括以下步骤：1. 若二叉树为空，则返回空列表。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
西华数学与计算机学院上机实践报告课程名称：数据结构年级：2011上机实践成绩：指导教师：唐剑梅姓名：蒋俊上机实践日期：2012-11-20上机实践名称：学号：312011*********上机实践编号：2上机实践时间：8:00-9:30一、实验目的1.熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：先序递归遍历、中序递归和非递归遍历、后序递归遍历。
了解二叉树的按层遍历、先序非递归遍历及后序非递归遍历。
2.用树解决实际问题，如哈夫曼编码等。
加深对“数据结构+算法=程序”的理解和认识，提高编写较复杂程序的能力。
二、实验内容建立一棵二叉树，分别用“先根非递归”方法、“按层遍历”的方法遍历。
三、实验环境硬件: 微型计算机P4软件: Windows XP+Microsoft Visual C++6.0四、程序源码及调试过程#include <iostream.h>#include "2.h"#include "3.h"typedef int ElemType;struct NodeType //定义结点结构体{ ElemType data;NodeType *lch,*rch;};class BiTree //定义二叉树类{public:BiTree(){root=NULL;}; //构造函数~BiTree(){destroy(root) ;} //析构函数void inorder() //中序遍历{ inorder(root); }void preordertswap() //利用先序遍历方法交换左右子树{ preorderswap(root); }int theight() //求二叉树高度{ return height(root); }void creat0();void preoder(); //先根遍历非递归void levelorder(); //按层遍历二叉树private:NodeType *root; //数据成员，树根NodeType *creat(); //建立二叉树递归方法void inorder(NodeType *p); //中序遍历void preorderswap(NodeType *p); //利用先序遍历方法交换左右子树int height(NodeType *p); //求二叉树高度递归算法void destroy(NodeType* &p); //删除二叉树所有结点};void BiTree::creat0() //建立树函数，{ cout<<"请按照树的先序遍历顺序组织数据"<<endl;cout<<"若结点信息是int，把每个结点的空孩子以0输入;"<<endl;cout<<"例如一个结点的二叉树11，输入：11 0 0;"<<endl;root=creat(); //调用私有creat();}NodeType * BiTree::creat() //递归建立二叉树算法{ NodeType *p; ElemType x;cout<<"\n 输入数据："; cin>>x;if( x==0) p=NULL;else { p=new NodeType; p->data=x;p->lch=creat(); //递归调用自身p->rch=creat();}return p;}void BiTree::preoder() //先根遍历非递归{NodeType *q;SqStack<NodeType*> s;q=root;int boo=1;cout<<"先根非递归遍历"<<endl;do{while(q!=NULL){cout<<q->data;s.push(q);q=q->lch;}if(s.IsEmpty())boo=0;else{q=s.pop();q=q->rch;}}while(boo);cout<<endl;}void BiTree::inorder(NodeType *p) //中根遍历{ if(p != NULL){ inorder(p->lch);cout<<p->data<<" ";inorder(p->rch);}}void BiTree::preorderswap(NodeType *p) //利用先序遍历方法交换左右子树{ if(p != NULL){ NodeType *r;r=p->lch;p->lch=p->rch; p->rch=r;//上面几条语句可以认为对结点的访问（交换左右孩子）//替换了原来的：cout<<p->data<<" "; 语句preorderswap(p->lch);preorderswap(p->rch);}}void BiTree::destroy(NodeType* &p) //删除二叉树所有结点{ if(p != NULL){ destroy(p->lch);destroy(p->rch);delete p;p = NULL;}}int BiTree::height(NodeType *p) //求二叉树高度(递归){ if(p == NULL) return 0;else{ int hl=height(p->lch);int hr=height(p->rch);return 1 + (hl>hr?hl:hr); //1加上hl和hr的较大值}}void BiTree::levelorder() //按层遍历{SqQueue<NodeType*>q;NodeType *p;p=root;if(p!=NULL) q.EnQueue(p);while(!q.IsEmpty()){p=q.DeQueue();cout<<p->data<<" ";if(p->lch!=NULL) q.EnQueue(p->lch);if(p->rch!=NULL) q.EnQueue(p->rch);}}//---------------------------------------------------------------------------int main(){ int k; BiTree root0; //声明创建二叉树对象，调用构造函数do{ cout<<"\n\n";cout<<"\n\n 1. 建立二叉树";cout<<"\n\n 2. 交换左右子树";cout<<"\n\n 3. 求二叉树深度";cout<<"\n\n 4.先根非递归遍历";cout<<"\n\n 5.按层遍历二叉树";cout<<"\n\n 6. 结束程序运行";cout<<"\n======================================";cout<<"\n 请输入您的选择(1,2,3,4):"; cin>>k;switch(k){ case 1:{ cout<<"\n 建立二叉树：";root0.creat0();cout<<"\n 中根遍历结果：";root0.inorder();} break;case 2:{ root0.preordertswap();cout<<"\n 交换左右子树后中根遍历结果：";root0.inorder();} break;case 3:{ int deep;deep=root0.theight();cout<<"\n 树的深度是："<<deep;} break;case 4:{cout<<"\n 先根遍历的结果：";root0.preoder();}break;case 5:{cout<<"\n 按层遍历二叉树的结果：";root0.levelorder();}break;case 6: break;}cout<<"\n ----------------";} while(k>=1 && k<6);return 0;}//栈的顺序存储结构，顺序栈类#include<iostream.h>#include <iomanip.h>//------------------------------栈的顺序存储结构-----------------------------//typedef int ElemType; // 数据元素的类型//const int MAXSIZE=100; // 数组的容量template <class T>class SqStack{ private:T *elem;int maxSize;int top;public:SqStack(int s=30);~SqStack(){delete[]elem;}void push(T item);T pop();void PrintOut();int IsEmpty(){return top==-1;}int IsFull(){return top==maxSize-1;}};//------------------------------------------------------------- template<class T>SqStack<T>::SqStack(int s){ top=-1;maxSize=s;elem=new T[maxSize];for(int i=0;i<maxSize;i++)elem[i]=0;}template<class T>void SqStack<T>::push(T item) { if(!IsFull()){top++;elem[top]=item;}}template<class T>T SqStack<T>::pop(){T x;if(!IsEmpty()) {x=elem[top];top--;}return x;}template<class T>void SqStack<T>::PrintOut() {int t;if(!IsEmpty())cout<<"栈已空"<<endl;else{i=top;while(i!=-1){cout<<"data="<<elem[i];i--;}}}队列的顺序存储结构#include<iostream.h>template<class T>class SqQueue{public:SqQueue(int sz=30);~SqQueue(){delete[]elem;}void EnQueue(T item);T DeQueue();T GetFront();int IsEmpty(){return front==rear;}int IsFull(){return (rear+1)%maxSize==front;}int Length(){return (rear-front+maxSize)%maxSize;}void PrintOut();private:int front,rear;T*elem;int maxSize;};template<class T>SqQueue<T>::SqQueue(int sz){front=rear=0;maxSize=sz;elem=new T[maxSize];for(int i=0;i<maxSize;i++)elem[i]=0;}template<class T>void SqQueue<T>::EnQueue(T item){if(!IsFull()){rear=(rear+1)%maxSize;elem[rear]=item;}}template<class T>T SqQueue<T>::DeQueue(){if(!IsEmpty()){front=(front+1)%maxSize;return elem[front];}}template<class T>T SqQueue<T>::GetFront(){if(!IsEmpty())return elem[(front+1)%maxSize];}template<class T>void SqQueue<T>::PrintOut(){int i;if(!IsEmpty())cout<<"队列已空"<<endl;else{ i=rear;while(i!=front){cout<<"data="<<elem[i];i=(i-1)%maxSize;}}}五、总结通过本次实验，我熟悉了二叉树遍历的操作，巩固了队列的顺序存储结构和栈的顺序存储结构的知识，同时也掌握了类模板的操作，本次上机实践基本完成了实验内容，但完成的不是很好，以后需要更加努力地掌握基本的知识。