二叉树的建立和遍历的实验报告.pdfVIP

竭诚为您提供优质文档/双击可除

二叉树的建立和遍历的实验报告

篇一：二叉树遍历实验报告

数据结构实验报告

报告题目：二叉树的基本操作学生班级：

学生姓名：学号：

一．实验目的

1、基本要求：深刻理解二叉树性质和各种存储结构的

特点及适用范围；掌握用指针类型描述、访问和处理二叉树

的运算；熟练掌握二叉树的遍历算法；。

2、较高要求:在遍历算法的基础上设计二叉树更复杂操

作算法；认识哈夫曼树、哈夫曼编码的作用和意义;掌握树

与森林的存储与便利。二.实验学时：

课内实验学时：3学时课外实验学时：6学时三．实验

题目

1．以二叉链表为存储结构，实现二叉树的创建、遍历

114

（实验类型：验证型）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;};

214

if(top0){

top=top-1;p=stack[top];

while(p!=nuLL||top!=0);}

2、求二叉树高度：

intcbiTree::postTreeDepth(binTreeif(T!=nuLL){

l=postTreeDepth(T-lchild);r=postTreeDepth(T-rchil

d);max=lr?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）在主函数中定义对象，通过对象调用函数，实现各

个函数的操作。运行结果：