数据结构实验——二叉树

《数据结构实验——二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验名称二叉树应用指导教师周立章实验类型验证实验学时2+8实验时间2011/11/25一、实验目的和要求1．掌握二叉树的基本概念和性质2．掌握创建和构造二叉链表的算法3．掌握二叉树链表存储基础的的三种递归遍历算法和非递归算法。4．掌握计算二叉树的结点、二叉树的深度和二叉树的叶子结点数等算法。5．掌握huffman树的构造和编码。实验要求：（1）理解二叉链表的初始化、二叉树空的判断；（2）理解二叉树的遍历算法，掌握其应用。二、实验环境(实验设备)硬件:微型计算机P5软件:WindowsXP+MicrosoftVisualC

2、++6.0三、实验原理及内容实验题目:1．创建二叉树的链表存储结构；2．实现二叉链表的初始化算法、二叉树空的判断算法；3．实现二叉树的先序遍历算法、中序遍历算法和后序遍历算法；4．利用某遍历算法实现计算二叉树中叶子结点、度为2的结点和度为1的结点的个数。5．求二叉树中结点个数。6．求二叉树的深度。7．设计一个算法，求二叉树中指定结点x的层数。8．设计一算法，求先序遍历序列中第k个结点的左右孩子。9．求结点x的所有祖先。实验前完成：1-5小题。实验中完成：7-9小题。实验后完成：（1）输出所有叶子结点到根结点的路径。（2）

3、如果将二叉树中左分支标为0，右分支标为1，从叶子结点到根结点的路径由所经过的左、右分支组成。取左右分支的上0和1就构成了叶子结点的二进制编码。请输出二叉树中所有叶子结点的编码。[基本要求]：A：从终端读入字符集大小为n，及n个字符和n个权值，建立哈夫曼树，进行编码并且输出。并将它存于文件hfmtree中。8B：利用已建好的哈夫曼编码文件hfmtree，对键盘输入的正文进行译码。输出字符正文，再输出该文的二进制码。[测试数据]用下表中给出的字符集和频度的实际统计数据建立哈夫曼树：字符ABCDEFGHIJKLMN频度6413

4、22321032115475715322057字符OPQRSTUVWXYZ空格频度63151485180238181161168并实现以下报文的译码和输出：“THISPROGRAMISMYFAVORITE”。8实验解答：1.二叉树的二叉链式存储结构的结点结构体定义structTree{ElemTypedata;charch;inti;Tree*lChild,*rChild;};2.二叉链表的初始化（1）带头结点的二叉链表的初始化算法BinaryTree(){head=newTree;root=NULL;head->nex

5、t=root;}（2）无头结点的二叉链表的初始化算法BinaryTree(){root=NULL;}(3)画出用来测试的二叉树的直观图（至少应有二棵不同的二叉树）83.二叉树t是空树的判断条件是什么？root=NULL;4．如果p是指向二叉链表中某一结点，则：（1）p是叶子结点的条件是：p->lChild==NULL&&p->rChild==NULL（2）p是度为1的结点的条件是：(p->lChild!=NULL&&p->rChild==NULL)

6、

7、(p->lChild==NULL&&p->rChild!=NULL)（

8、3）p的左子树的根结点是：p（4）p的右子树的根结点是：p5.写二叉树的先序、中序、后序遍历算法if(p!=NULL)//先序{cout<data<<"";ProOrder(p->lChild);ProOrder(p->rChild);}if(p!=NULL)//中序{InOrder(p->lChild);cout<data<<"";InOrder(p->rChild);}if(p!=NULL)//后序{PostOrder(p->lChild);PostOrder(p->rChild);cout<

9、data<<"";}6.写出求二叉树叶子结点个数的算法。if(p!=NULL){a++;CalculateNode(p->lChild,a);CalculateNode(p->rChild,a);}87．写出求二叉树的深度的算法if(p!=NULL){return1+CalculateDepth(p->lChild)>=CalculateDepth(p->rChild)?CalculateDepth(p->lChild):CalculateDepth(p->rChild);}8．写出求二叉树中结点x所在层数的设计思路和技

10、术路线if(p!=NULL){if(p->i=q->i)return1+CalculateDepth(p->lChild)>=CalculateDepth(p->rChild)?CalculateDepth(p->lChild):CalculateDepth(p->rChild);;}设计思路和技术路线:当结点的编号