二叉树遍历 实验报告

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

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

3、edef struct node TElemType 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 &T);int leaf(BinTree &T);2、编写算法实现二叉树的非递归中序遍历和求二叉树高度。1）问题描述：实现二叉树的

4、非递归中序遍历和求二叉树高度2）实验要求：以二叉链表作为存储结构3) 实现过程：1、实现非递归中序遍历代码： void CBiTree:InorderN(BinTree &T)BinTree stackMAX,p;int top=0;p=T;dowhile(p!=NULL)stacktop=p;top=top+1;p=p-lchild;if(top0)top=top-1;p=stacktop; printf(%3c,p-data );p=p-rchild;while(p!=NULL|top!=0);2、求二叉树高度：int CBiTree:PostTreeDepth(BinTree &T)in

5、t l,r,max;if(T!=NULL)l=PostTreeDepth(T-lchild );r=PostTreeDepth(T-rchild );max=lr?l:r;return(max+1); else return(0);实验步骤：1） 新建一个基于Console Application的工程，工程名称BiTreeTest；2） 新建一个类CBiTree二叉树类。3） 在类CBiTree的头文件上方定义二叉链表存储数据类型结构体BiTNode。4） 在类CBiTree中定义函数CreateBinTree（）；Preorder()；Inorder()；Postorder();PostTreeDepth();InorderN()；5） 实现函数CreateBinTree（）；Preorder()；Inor