(完整word版)二叉树遍历实验报告

数据结构实验报告

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

一．实验目的

1、 基本要求：深刻理解二叉树性质和各种存储结构的特点及适用范围;掌握用指针类型描述、访问和处理二叉树的运算;熟练掌握二叉树的遍历算法；。

2、 较高要求： 在遍历算法的基础上设计二叉树更复杂操作算法；认识哈夫曼树、哈夫曼编码的作用和意义；掌握树与森林的存储与便利.

(完整word版)二叉树遍历实验报告

二。 实验学时: 课内实验学时:3学时 课外实验学时：6学时 三．实验题目

1． 以二叉链表为存储结构，实现二叉树的创建、遍历(实验类型：验证型） 1）问题描述：在主程序中设计一个简单的菜单,分别调用相应的函数功能： 1…建立树 2…前序遍历树 3…中序遍历树 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)数据结构

(完整word版)二叉树遍历实验报告

二叉链表存储数据类型定义

typedef 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）问题描述：实现二叉树的非递归中序遍历和求二叉树高度 2）实验要求：以二叉链表作为存储结构

3) 实现过程：

1、实现非递归中序遍历代码:

void CBiTree：：InorderN（BinTree &T） {

BinTree stack［MAX],p； int top=0;p=T； do

(完整word版)二叉树遍历实验报告

{

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 )； }

while（p！=NULL｜|top!=0);

｝

p=p—>rchild;

｝

2、求二叉树高度：

int CBiTree：：PostTreeDepth（BinTree &T） {

int l，r，max; if（T！=NULL) {

l=PostTreeDepth(T—〉lchild )；

(完整word版)二叉树遍历实验报告

｝

r=PostTreeDepth（T->rchild ); max=l〉r?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()；Inorder（)；Postorder（)；PostTreeDepth(）;InorderN（）；

6） 在主函数中定义对象,通过对象调用函数，实现各个函数的操作. 运行结果:

(完整word版)二叉树遍历实验报告

(完整word版)二叉树遍历实验报告

(完整word版)二叉树遍历实验报告