二叉树遍历--实验报告

1、数据结构实验报告报告题目：一叉树的基本操作学生班级:学生姓名：学号:.实验目的1、基本要求：深刻理解二叉树性质和各种存储结构的特点及适用范围；掌 握用指针类型描述、访问和处理二叉树的运算；熟练掌握二叉树的遍历算 法；。2、 较高要求 : 在遍历算法的基础上设计二叉树更复杂操作算法；认识哈夫曼树、哈夫曼编码的作用和意义 ; 掌握树与森林的存储与便利。二 . 实验学时：课内实验学时： 3 学时课外实验学时： 6 学时三实验题目1 以二叉链表为存储结构，实现二叉树的创建、遍历(实验类型：验证型)1) 问题描述： 在主程序中设计一个简单的菜单， 分别调用相应的函数功能： 1建立树2前序遍历树3中序遍历

2、树4后序遍历树5求二叉树的高度6求二叉树的叶子节点7非递归中序遍历树0结束2) 实验要求：在程序中定义下述函数，并实现要求的函数功能：CreateBinTree(BinTree &T):按从键盘输入的前序序列，创建树Preorder(BinTree &T) ：前序遍历树(递归)Inorder(BinTree &T) ：中序 ( 递归 ) 遍历树Postorder(BinTree &T):后序遍历树(递归)PostTreeDepth(BinTree &T) ：树的高度 leaf(BinTree &T): 树的叶子节点InorderN(BinTree

3、 &T) ：中序(非递归)遍历树3) 数据结构二叉链表存储数据类型定义typedef struct nodeTElemType data;struct node *lchild,*rchild;BinTNode;元素类型：int CreateBinTree(BinTree &T);void Preorder(BinTree &T);void Inorder(BinTree &T);void Postorder(BinTree &T);void InorderN(BinTree &T);int PostTreeDepth(BinTree &

4、T);int leaf(BinTree &T);2、编写算法实现二叉树的非递归中序遍历和求二叉树高度。1) 问题描述：实现二叉树的非递归中序遍历和求二叉树高度2) 实验要求：以二叉链表作为存储结构3) 实现过程：1、实现非递归中序遍历代码：void CBiTree:InorderN(BinTree &T)BinTree stackMAX,p;int top=0;p=T;do while(p!=NULL) stacktop=p; top=top+1; p=p->lchild;if(top>0)top=top-1; p=stacktop;printf("%3c

5、",p->data ); p=p->rchild;while(p!=NULL|top!=0);2、求二叉树高度：int CBiTree:PostTreeDepth(BinTree &T)int l,r,max;if(T!=NULL)l=PostTreeDepth(T->lchild ); r=PostTreeDepth(T->rchild ); max=l>r?l:r;return(max+1);else return(O);实验步骤：1) 新建一个基于 Con sole Applicatio n的工程，工程名称 BiTreeTest ;2) 新

6、建一个类CBiTree二叉树类。3) 在类CBiTree的头文件上方定义二叉链表存储数据类型结构体BiTNode。4) 在类 CBiTree 中定义函数 CreateBinTree ()； Preorder() ； Inorder()； Postorder();PostTreeDepth();l norderN()；5) 实 现函数 CreateB in Tree ( )； Preorder() ； In order()；Postorder();PostTreeDepth();I norderN()；6) 在主函数中定义对象，通过对象调用函数，实现各个函数的操作。运行结果：二叉树建立ii归先序

7、嘱厅递归巾序遍厅非递归中序遍历I-逵归后序遍历求二叉树的直度?求二叉树的子叶个数8退岀i育输入要进行的操作:该二叉树的噁陀先斤遍历序列为: Ahri.cf q递归先序逼历递归中序遍历非递归口序遍历递归后库逼历求二叉树的高度农二对对的子叶个数退出青输入要进行的操作， 核二叉树的递归中序遍历序列为: C:UscrsAd rniri5trotorDc5ktopBiTreeTc5tBiTrceTcstCebugvBiTrcc.exee1二叉树建立2遡先序遍历3噁中序遍历4非递归中痒遍历5递启序遍历6农二义树的昌度7求二叉树的子叶个数8退出请输人雯进行的操作：4该二叉树的非递归中序遍历序列为d b o a f c cf2递归先序遍历3递归中序遍历4非递归中库漏力5噬归后序遍历6求二叉树的髙.变V求二叉树的子】廿遨8退出诗