实验报告二叉树.docx

实验报告二叉树.docx

《实验报告二叉树.docx》由会员分享，可在线阅读，更多相关《实验报告二叉树.docx（5页珍藏版）》请在冰点文库上搜索。

实验报告二叉树

实验报告二叉树

篇一：

二叉树实验报告　　山东工商学院　　《数据结构》实验指导及报告书　　XX/XX学年　　姓名：

学号：

班级：

指导教师：

　　Xx学院　　XX年11月25日　　第一学期　　实验三二叉树　　一、实验目的　　一、把握二叉树的大体特性　　二、把握二叉树的先序、中序、后序的递归遍历算法3、明白得二叉树的先序、中序、后序的非递归遍历算法　　4、通过求二叉树的深度、叶子结点数和层序遍历等算法，明白得二叉树的大体特性　　二、实验预习　　说明以下概念　　一、二叉树：

是另一种树型结构，它的特点是每一个结点最多只有两棵子树，而且二叉树有左右之分，第二序不能任意倒置。

二、递归遍历：

　　一、非递归遍历：

　　4、层序遍历：

　　三、实验内容和要求　　一、阅读并运行下面程序，依照输入写出运行结果，并画出二叉树的形态。

#include#include　　#defineMAX20　　typedefstructBTNode{/*节点结构声明*/　　chardata;/*节点数据*/structBTNode*lchild;　　structBTNode*rchild;/*指针*/}*BiTree;　　BiTreecreateBiTree（BiTreet）{/*先序遍历创建二叉树*/chars;　　printf（"\npleaseinputdata:

（exitfor#）"）;s=getche（）;　　if（s=='#'）{t=NULL;returnt;}　　t=（BiTree）malloc（sizeof（structBTNode））;　　if（t==NULL）{printf（"Memoryallocfailure!

"）;exit（0）;}t->data=s;　　t->lchild=createBiTree（t->lchild）;/*递归成立左子树*/t->rchild=createBiTree（t->rchild）;/*递归成立右子树*/returnt;}　　voidPreOrder（BiTreep）{/*先序遍历二叉树*/if（p!

=NULL）{　　printf（"%c",

p->data）;PreOrder（p->lchild）;PreOrder（p->rchild）;}}　　voidInOrder（BiTreep）{/*中序遍历二叉树*/if（p!

=NULL）{　　InOrder（p->lchild）;printf（"%c",p->data）;InOrder（p->rchild）;}}　　voidPostOrder（BiTreep）{/*后序遍历二叉树*/if（p!

=NULL）{　　PostOrder（p->lchild）;PostOrder（p->rchild）;printf（"%c",p->data）;}}　　voidPreorder_n（BiTreep）{/*先序遍历的非递归算法*/BiTreestack[MAX],q;inttop=0,i;　　for（i=0;i　　while（q!

=NULL）{　　printf（"%c",q->data）;　　if（q->rchild!

=NULL）stack[top++]=q->rchild;if（q->lchild!

=NULL）q=q->lchild;else　　if（top>0）q=stack[--top];elseq=NULL;}}　　voidrelease（BiTreet）{/*释放二叉树空间*/if（t!

=NULL）{　　release（t->lchild）;release（t->rchild）;

　　free（t）;}}　　intmain（）{　　BiTreet=NULL;inte,m,g;　　t=createBiTree（t）;　　printf（"\n\nPreOrderthetreeis:

"）;PreOrder（t）;　　printf（"\n\nInOrderthetreeis:

"）;InOrder（t）;　　printf（"\n\nPostOrderthetreeis:

"）;PostOrder（t）;　　printf（"\n\n先序遍历序列（非递归）:

"）;　　Preorder_n（t）;　　printf（"\n\n输出结点总数:

"）;e=PreOrder_num（t）;printf（"%d",e）;　　printf（"\n\n输出树的深度:

"）;m=BTNodeDepth（t）;printf（"%d\n",m）;　　printf（"\n\n输出树叶子总数:

"）;g=LeafNodes（t）;printf（"%d\n",g）;release（t）;return0;}　　?

　　运行程序　　输入：

　　ABC##DE#G##F###运行结果：

　　画出该二叉树的形态：

　　二、在上题中补充求二叉树中求结点总数算法（提示：

可在某种遍历进程中统计遍历的结点数），并在主函数中补充相应的挪用验证正确性。

算法代码：

　　intPreOrder_num（BiTreep）{intj=0;　　BiTreestack[MAX],q;inttop=0,i;　　for（i=0;i篇二：

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

　　2．需求分析　　

（1）输入的形式和输入值的范围：

以字符形式按先序遍历输入　　

（2）输出的形式：

依次按递归先序、中序、后序遍历，非递归先序、中序、后序遍历结果输出　　（3）程序所能达到的功能：

从键盘同意输入（先序）进行遍历（先序、中序、后序），将遍历结果打印输。

　　（4）测试数据：

　　ABCффDEфGффFффф（其中ф表示空格字符）　　那么输出结果为先序：

ABCDEGF　　中序：

CBEGDFA　　后序：

CGBFDBA　　3．概要设计

（1）structbtnode{　　chardata;数据　　structbtnode*Lchild;左子数指针　　structbtnode*Rchild;右子数指针　　};　　structbtnode*createbt（structbtnode*bt）　　初始条件：

空二叉树存在　　操作结果：

先序成立二叉树　　voidpreOrder（structbtnode*bt）　　初始条件：

二叉树存在　　递归先序遍历二叉树　　voidpreOrder1（structbtnode*bt）　　初始条件：

二叉树存在　　操作结果：

非递归先序遍历　　voidmidOrder（structbtnode*bt）　　初始条件：

二叉树存在　　操作结果：

递归中序遍历　　voidmidOrder1（structbtnode*bt）　　初始条件：

二叉树存在　　操作结果：

非递归中序遍历　　voidpostOrder（structbtnode*bt）　　初始条件：

二叉树存在

　　操作结果：

递归后序遍历　　voidpostOrder1（structbtnode*bt）　　初始条件：

二叉树存在　　操作结果：

非递归后序遍历　　voidmain（）主函数　　

（2）voidmain（）主函数　　{　　*createbt　　preOrder　　preOrder1　　midOrder　　midOrder1　　postOrder　　postOrder1　　}　　4．详细设计　　structbtnode{　　chardata;　　structbtnode*Lchild;　　structbtnode*Rchild;　　};　　structbtnode*createbt（structbtnode*bt）{

　　输入结点数据c　　检查存储空间　　将c赋给结点参数p　　递归成立左子树　　递归成立右子树　　}　　voidpreOrder（structbtnode*bt）{　　判定树是不是为空　　输出根结点数data　　递归遍历左子树　　递归遍历右子树　　}　　voidpreOrder1（structbtnode*bt）{　　概念栈，结点参数p　　While（栈或p是不是为空）{　　While（p!

=null）{　　输出根结点数data　　将根结点压栈　　遍历左子树　　}　　提取栈顶元素值　　栈顶元素出栈

　　访问右子树　　}　　voidmidOrder（structbtnode*bt）　　{判定树是不是为空　　递归遍历左子树　　输出根结点数data　　递归遍历右子树}　　voidmidOrder1（structbtnode*bt）{　　概念栈，结点参数p　　While（栈或p是不是为空）{　　While（p!

=null）{　　将根结点压栈　　遍历左子树　　}　　提取栈顶元素值　　输出根结点数data　　栈顶元素出栈　　访问右子树　　}　　voidpostOrder（structbtnode*bt）{　　判定树是不是为空　　递归遍历左子树

　　递归遍历右子树　　输出根结点数data　　}　　voidpostOrder1（structbtnode*bt）{　　概念栈，结点参数p,pre　　bt入栈　　While（栈或p是不是为空）{　　提取栈顶元素值　　if判定p是不是为空或是pre的根结点　　输出根结点数data　　栈顶元素出栈　　栈顶元素p赋给pre记录　　elseif右结点非空将右结点压栈　　if左结点将左结点压栈}　　}　　voidmain（）{　　structbtnode*root=NULL;　　root=createbt（root）;　　preOrder（root）;midOrder（root）;postOrder（root）;　　preOrder1（root）;midOrder1（root）；postOrder1（root）;

　　}　　5.调试分析　　

（1）先序成立二叉树时，虽用到递归建左右子树，但没有把他们赋值给根节点的左右指针，造成二叉树脱节。

（2）非递归后序遍历时，未考虑到所有条件，只考虑节点的左右结点是不是为空，而未考虑结点是不是是前一个遍历结点的根节点且不为空。

　　（3）用栈实现非递归遍历。

　　6.用户利用说明　　运行环境为vc6.0　　程序执行后在命令窗口中输入测试数据　　然后enter　　7.测试结果　　八、附录　　#include　　#include　　#include　　#include　　#include　　usingnamespacestd;　　structbtnode{　　chardata;

　　structbtnode*Lchild;　　structbtnode*Rchild;　　};　　structbtnode*createbt（structbtnode*bt）//先序成立二叉树　　{　　charc;　　c=getchar（）;　　if（c==''）//若是输入为空，那么子树为空　　{　　bt=NULL;　　}　　else　　{　　if（!

（bt=（structbtnode*）malloc（sizeof（structbtnode））））//查验bt空间分派是不是成功printf（"error!

"）;　　bt->data=c;　　bt->Lchild=createbt（bt->Lchild）;//递归成立左子树　　bt->Rchild=createbt（bt->Rchild）;//递归成立右子树　　}　　return（bt）;

　　}　　voidpreOrder（structbtnode*bt）//递归先序遍历{　　if（bt!

=NULL）　　{　　printf（"%c",bt->data）;　　preOrder（bt->Lchild）;　　preOrder（bt->Rchild）;　　}　　}　　voidpreOrder1（structbtnode*bt）//非递归先序遍历{　　inti=0;　　structbtnode*p;　　stacks;概念栈　　p=bt;　　while（p!

=NULL||!

s.empty（））　　{　　while（p!

=NULL）　　{　　printf（（转载自：

xiaocaOfaNWen小草范文网:

实验报告二叉树）"%c",p->data）;　　s.push（p）;//将根结点压栈

p=p->Lchild;//遍历左子树}　　if（!

s.empty（））　　{　　p=s.top（）;//提取栈顶元素值s.pop（）;//栈顶元素出栈　　p=p->Rchild;//访问右子树}　　}　　}　　voidmidOrder（structbtnode*bt）//递归中序遍历{　　if（bt!

=NULL）　　{　　midOrder（bt->Lchild）;　　printf（"%c",bt->data）;　　midOrder（bt->Rchild）;　　}篇三：

数据结构C二叉树实验报告　　北京林业大学　　12学年—13学年第1学期数据结构实验报告书　　专业：

自动化班级：

11－1姓名：

宁友菊学号：

111044120实验地址：

B2机房任课教师：

孟伟　　实验题目：

二叉树的大体操作实验环境：

VisualC++实验目的：

　　1．把握二叉树的概念；　　2．把握二叉树的大体操作，如成立、前序遍历、中序遍历和后序遍历、结点个数的统计等；　　实验内容：

　　用递归的方式实现以下算法：

　　1．以二叉链表表示二叉树，成立一棵二叉树；2．输出二叉树的前序遍历结果；3．输出二叉树的中序遍历结果；4．输出二叉树的后序遍历结果；5．统计二叉树的叶结点个数；6．统计二叉树的结点个数；　　7．计算二叉树的深度。

　　8．互换二叉树每一个结点的左小孩和右小孩；　　实现方式、实验结果及结论分析等：

（一）实现方式　　1.所用数据结构的概念及其相关说明（相关结构体或类的概念及其含义）　　实验采纳二叉树的数据结构，以二叉链表存储，主程序中采纳switch函数挪用各个子程序以实现各个功能。

0终止程序，输入错误时返回主函数从头输入。

　　2.自概念函数的名称及其功能说明

（1）voidCreateBiTree以二叉链表表示二叉树，成立一棵二叉树；　　

（2）voidPreOrderTraverse输出二叉树的前序遍历结果；

　　（3）voidInOrderTraverse输出二叉树的中序遍历结果；（4）voidPostOrderTraverse输出二叉树的后序遍历结果；（5）intLeafNodeCount统计二叉树的叶结点个数；　　（6）intNodeCount统计二叉树的结点个数；　　（7）intDepth计算二叉树的深度。

　　（8）intSwap互换二叉树每一个结点的左小孩和右小孩；　　3.要紧功能算法voidPreOrderTraverse的时刻复杂度　　O（n）=O（n1）×O（n2）×O（n3）×O（n4）×O（n5）×O（n6）×O（n7）xO（n8）O（n1）——voidCreateBiTree函数算法时刻复杂度O（n）O（n2）——voidPreOrderTraverse函数算法时刻复杂度O（n）O（n3）——voidInOrderTraverse函数算法时刻复杂度O（n）O（n4）——voidPostOrderTraverse函数算法时刻复杂度O（n）O（n5）——intLeafNodeCount函数算法时刻复杂度O（n）O（n6）——intNodeCount函数算法时刻复杂度O（n）O（n7）——intDepth函数算法时刻复杂度O（n）O（n8）——intSwap函数算法时刻复杂度O（n）　　4.实验流程图　　

（二）实验结果一、选择操作一：

　　二、创建二叉树　　3、前序遍历结果　　4、中序遍历结果　　五、后序遍历结果　　六、总结点数　　7、叶节点数　　八、二叉树深度　　九、对换左右小孩　　10、退出　　1一、输入错误检测