竭诚为您提供优质文档/双击可除二叉树的建立和遍历的实验报告
篇一：二叉树遍历实验报告
数据结构实验报告
报告题目：二叉树的基本操作学生班级：
学生姓名：学号：
一．实验目的
1、基本要求：深刻理解二叉树性质和各种存储结构的特点及适用范围；掌握用指针类型描述、访问和处理二叉树的运算；熟练掌握二叉树的遍历算法；。
2、较高要求:在遍历算法的基础上设计二叉树更复杂操作算法；认识哈夫曼树、哈夫曼编码的作用和意义;掌握树与森林的存储与便利。
二.实验学时：
课内实验学时：3学时课外实验学时：6学时三．实验题目
1．以二叉链表为存储结构，实现二叉树的创建、遍历
（实验类型：验证型）1）问题描述：在主程序中设计一个简单的菜单，分别调用相应的函数功能：1…建立树2…前序遍历树3…中序遍历树4…后序遍历树5…求二叉树的高度6…求二叉树的叶子节点7…非递归中序遍历树0…结束2）实验要求：在程序中定义下述函数，并实现要求的函数功能：createbinTree(binTree
structnode*lchild,*rchild;
}binTnode;元素类型：
intcreatebinTree(binTree
voidpreorder(binTreevoidInorder(binTree
voidpostorder(binTreevoidInordern(binTreeintleaf(bi nTree
intpostTreeDepth(binTree
2、编写算法实现二叉树的非递归中序遍历和求二叉树高度。
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二叉树类。
3）在类cbiTree的头文件上方定义二叉链表存储数据类型结构体biTnode。
4）在类cbiTree中定义函数createbinTree（）；preorder()；Inorder()；
postorder();postTreeDepth();Inordern()；
5）实现函数createbinTree（）；preorder()；Inorder()；
postorder();postTreeDepth();Inordern()；
6）在主函数中定义对象，通过对象调用函数，实现各个函数的操作。
运行结果：
篇二：数据结构实验报告-二叉树的实现与遍历
《数据结构》第六次实验报告
学生姓名学生班级学生学号指导老师
重庆邮电大学计算机学院
一、实验内容
1)采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。
2)输出树的深度，最大元，最小元。
二、需求分析
遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。
递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。
直到递归全部结束。
下面重点来讲述非递归方法：
首先介绍先序遍历：
先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。
具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问
结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。
再次介绍中序遍历：
中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。
具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。
如此循环直至结点指针和栈均为空，遍历结束。
最后介绍后序遍历：
后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。
如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。
三、详细设计
源代码：
#include
#definemAx100//表示栈的最大容量
#defineFuLL99//表示栈满
#defineempTY-1//表示栈空
typedefstructTnode//定义结点
{
chardata;//存储结点数据structTnode*left;//定义结点左子指针structTnode*right;//定义右子指针}Tnode,*pnode;//声明Tnode类型的变量和指针
typedefstructstack//定义栈
{
pnodepnode[mAx];//存放数据intp;//栈顶指针
}stack,*pstack;//定义stack类型的变量和指针
voidpush(pstackpstack,pnodepnode)//入栈
{
}
pnodepop(pstackpstack)//出栈
{
}
pnodeTop(pstackpstack)//看栈顶元素
{
}
intIsempty(pstackpstack)//栈判空
{
}
intIsfull(pstackpstack)//栈满
{
}
voidInitstack(pstackpstack)//初始化栈
if(pstack->p==FuLL)elsereturn0;return1;if(pstack->p ==empTY)elsereturn0;;return1;returnpstack->pnode[ps tack->p];returnpstack->pnode[pstack->p--];pstack->p ++;pstack->pnode[pstack->p]=pnode;//赋值
}
voidInittnode(pnoderoot,pnodeleft,pnoderight,charda ta)//初始化结点{
}
voidpreorderR(pnodeproot)//递归先序遍历算法
{
}
voidInorderR(pnodeproot)//递归中序遍历算法。