二叉树遍历--实验报告.doc

《二叉树遍历--实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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&T)：中序(非递归)遍历树3

3、)数据结构²二叉链表存储数据类型定义typedefstructnode{TElemTypedata;structnode*lchild,*rchild;}BinTNode;元素类型：intCreateBinTree(BinTree&T);voidPreorder(BinTree&T);voidInorder(BinTree&T);voidPostorder(BinTree&T);voidInorderN(BinTree&T);intPostTreeDepth(BinTree&T);intleaf(BinTree&T);2、编写算法实现二叉树的非递归中序遍历和求二

4、叉树高度。1）问题描述：实现二叉树的非递归中序遍历和求二叉树高度2）实验要求：以二叉链表作为存储结构3)实现过程：1、实现非递归中序遍历代码：voidCBiTree::InorderN(BinTree&T){BinTreestack[MAX],p;inttop=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

5、

6、top!=0)

7、;}2、求二叉树高度：intCBiTree::PostTreeDepth(BinTree&T){intl,r,max;if(T!=NULL){l=PostTreeDepth(T->lchild);r=PostTreeDepth(T->rchild);max=l>r?l:r;return(max+1);}elsereturn(0);}实验步骤：1）新建一个基于ConsoleApplication的工程，工程名称BiTreeTest；2）新建一个类CBiTree二叉树类。3）在类CBiTree的头文件上方定义二叉链表存储数据类型结构体BiTNode。4）在类CBiT

8、ree中定义函数CreateBinTree（）；Preorder()；Inorder()；Postorder();PostTreeDepth();InorderN()；5）实现函数CreateBinTree（）；Preorder()；Inorder()；Postorder();PostTreeDepth();InorderN()；6）在主函数中定义对象，通过对象调用函数，实现各个函数的操作。运行结果：