数据结构与算法实验二叉树基本操作

《数据结构与算法实验二叉树基本操作》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、二叉树基本操作实验报告二叉树基本操作实验报告实验名称二义树基本操作实验目的1.熟悉二叉树结点的结构和二叉树的基本操作；2.掌握二义树每种操作的具体实现；3.学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法；4.在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法;5.掌握构造哈夫曼树以及哈夫曼编码的方法。实验内容编制一个演示二叉树创建、遍历、计算等操作的程序。问题描述用数据结构相关知识，实现二叉树的定义和操作。该程序包括二叉树结构类型以及对二叉树操作的具体的函数定义（包括：初始化二叉树、清空二叉树、检查二叉树是否为空、遍历

2、二叉树（先序、后序、屮序、层次）、求二叉树的深度、求二叉树所有节点数）。问题分析该实验是棊于C语言和数据结构知识棊础的对二叉树的棊本操作的检验，无需设计复杂的算法，程序语句也相对简单。因此，我直接按要求定义了对二叉树操作的具体函数，并于主函数中实现对应的功能调用，其中，功能选择靠switch语句实现。实验步骤1.需求分析木演示程序用VC++编写，完成二叉树的生成、遍历、计算等基木操作。①输入的形式和输入值的范围：以字符（其中表示虚节点）的形式输入，以创建二叉树；在输入二叉树节点前，必须先确定该序列能正确创建二叉树。②输出的形式：在所有三种操作中

3、都显示操作是否正确以及操作后二叉树的内容。③程序所能达到的功能：完成二叉树的生成、遍历（包括先序、后序、中序、层次四种方式)、计算等基本操作。④测试数据：创建操作中依次输入a,b,d,#,#生成一个二叉树。2.概要设计1)为了实现上述程序功能，需要定义二叉树的抽象数据类型：ADTBitTree{数据对象：由一个根节点和两个互不和交的左右子树构成数据关系：结点具有相同的数据类型及层次结构基本操作：VoidBinTreelnit(BitTree*T)初始条件：无操作结果：初始化一棵二叉树VoidBinTreeCreat(BitTree*T)初始条件

4、：二叉树T已存在操作结果：按先序次序创建一棵二叉树2)本程序包含7个函数：①主函数main()②初始化二义树函数BinTreelnit()③建立一棵二叉树函数BinTreeCreat()④先序遍历函数PreOrderTraverse()⑤中序遍历函数lnOrderTraverse()⑥后序遍历闲数PostOrderTraverse()⑦层次遍历函数LevelOrderTraverse()⑧求二叉树深度函数Countlcvcl0⑨检验空树函数BinTreeEmpty()⑩求节点数函数Countnode()函数说明#include

5、#includetypedefcharDatatype;typedefstructNodeType{Datatypedata;structNodeType*lchild;structNodeType*rchild;}BiTNode;typedefBiTNode*BinTree;//初始化二叉树。即把树指针置空voidBinTreelnit(BiTNode*T){//BiTNode*T;T=(BiTNode*)malloc(sizeof(BiTNode));T=NULL;}//二叉树的建立BinTreeCreateBiTNod

6、e()BiTNode*T;printfC'Error!");Datatypech;ch=getchar();jf(ch=='#')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))T->data=ch;T->lchild=CreateBiTNode();T->rchild=CreateBiTNode();}returnT;}//先序遍历voidPreOrderTraverse(BiTNode*p){if(p!=NULL){printf("%c",p->data);PreOrderTrav

7、erse(p->lchild);PreOrderTraverse(p->rchild);}}//中序遍历voidInOrderTraversefBiTNode*p){if(p!=NULL){InOrderTraverse(p->lchild);printf("%cnzp->data);InOrderTraverse(p->rchild);}}//后序遍历voidPostOrderTraverse(BiTNode*p){if(p!=NULL){PostOrderTraverse(p->lchild);PostOrderTraverse(p->rc

8、hild);printf("%c",p->data);}}//层序遍历voidLevelOrderTraverse(BiTNode*T){BiTNod