《数据结构》实验项目卡-6-二叉树的基本操作.docx

《《数据结构》实验项目卡-6-二叉树的基本操作.docx》由会员分享，可在线阅读，更多相关《《数据结构》实验项目卡-6-二叉树的基本操作.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验6：二叉树的基本操作一、实验目的1 .掌握二叉树的非线性和递归性特点2 .理解二叉树的存储结构3 .掌握二叉树遍历操作二、实验内容1.使用二叉链表，创建一个如图(a)的二叉树。可以用先序、中序和后序方式遍历二叉树并将结点输出，.统计出一个二叉树叶子节点及树的深度。#include #include using namespace std;typedef char Datatype;int ent;struct TNode (Datatype data;TNode* rchild;TNode* Ichild;void CreatTree(TNode* &root) (char ndata;c

2、inndata;if(ndata=#) root二NULL; else (root=new TNode;root-data=ndata;CreatTree(root-lchild);CreatTree(root-rchild);)void preOrderTraver(TNode*& root)先|if(root!=NULL)coutroot-datan H;preOrderTraver(root-lchild); preOrderTraver(root-rchild);)void InOrderTraver(TNode*& root)中(if(root!=NULL) (InOrderTrav

3、er(root-lchild);coutroot-datan n; InOrderTraver(root-rchild);)void posOrderTraver(TNode*& root)/后(if(root!=NULL)(posOrderTraver(root-lchild);posOrderTraver(root-rchild); coutroot-datan n;)int BTHeight(TNode *t)/二叉树的深度int ans = 0;if(t = NULL) return 0;else if(t != NULL)ans += max(ans,max(BTHeight(t-l

4、child),BTHeight(t-rchild)+1); return ans;)int BTLeaff4ode(TNode *t)/二叉树的叶子节点数(if(t != NULL) if(t-lchild 二二 NULL & t-rchild 二二 NULL) (printf(n %cn ,t-data); CT1L+； else(BTLeafNode(t-lchild);BTLeafNode(t-rchild);return ent;)int main()(TNode *root=NULL;cout”请输入该二叉树的先序遍历结果:n；CreatTree(root);coutvv”先序遍历结

5、果 vvendl;preOrderTraver(root);coutendl;cout 中序遍历结果:endl;InOrderTraver(root);coutendl;coutv v”后序遍历结果:“ v vendl;posOrderTraver(root) ;coutendl;printf(n输出二叉树的深度：”)；int sum 二 BTHeight(root);cout sum endl;printf(输出二叉树的叶子结点：”)；int ans 二 BTLeafNode(root);printf(nn输出二叉树的叶子结点的个数：)cout ans endl;return 0;)运行结果

6、：存在问题：无2.对于给定的w二2,3,4,7,8,9权值，试构造一棵哈夫曼树，并给出各个节点的huffman编码及huffman数组的值。#define N 50叶子结点数#define M 2*N-1/树中结点总数typedef struct(char data5; /结点值int weight; 权重int parent;双亲结点int Ichild;左孩子结点int rchild;右孩子结点 HTNode;typedef structchar cdN;存放哈夫曼码int start; HCode;void CreateHT(HTNode ht,int n)int i,k,Inode,m

7、ode;double minl,min2;for (i=0;i2*n-l;i+)所有结点的相关域置初值-1hti.parent=hti .lchild=hti .rchild- 1;for (i=n;i2*n-l ;i+)构造哈夫曼树(min 1 =min2=32767;/Inode和mode为最小权重的两个结点位置lnode=rnode=-1;for (k=0;k=i-l ;k+)if (htk.parent-1) 只在尚未构造二叉树的结点中查找(if (htk.weightminl)(min2=min 1 ;mode=lnode;min 1 =htk. weight;lnode=k;) e

8、lse (if (htk.weightmin2)(min2=htk .weight;rnode=k;)hti.weight=htlnode.weight+htrnode. weight;hti.lchild=lnode;hti.rchild=rnode;htlnode.parent=i;htrnode.parent=i;void CreateHCode(HTNode ht,HCode hcd,int n)int i,f,c;HCode he;for (i=0;in;i+) /根据哈夫曼树求哈夫曼编码(f=hti.parent;while (f!=l)循序直到树根结点(if(htf.lchild

9、=c)处理左孩子结点else处理右孩子结点c=f;f=htf .parent;指向哈夫曼编码最开始字符hcdi=hc;void DispHCode(HTNode ht,HCode hcd,int n)int i,k;int sum=0,m=0;intj;printf(输出哈夫曼数组的值及编码:n);输出哈夫曼编码for (i=0;in;i+)(j=0；printf(n %s:tH,hti .data);for (k=hcdi.start;k=n;k+)printf(n%cn,hcdi.cdk);j+;)m+=hti. weight;sum+=hti. weighty;printf(Hnn);p

10、rintf(nn 带权路径长度 WPL=%dn”,sum);)int main()(int n=6,i;/n表示初始字符串的个数char *str= 2T3J417J8：9;int fnum=2,3,4,7,8,9;HTNode htM;HCode hcdN;for (i=0;in;i+)(s trcpy (ht i. data, str i);hti.weight=fnumi|;printf(nn!);CreateHT(ht,n);CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);printf(nnn);)测试数据：运行结果：存在问题：二、本次实验问题分析及学习建议备注：1 .每次实验完毕，各位学生可提交实验报告纸质（A4打印）及实验源程序代码，命名格式为学号.姓名 _sy序号一题号.cpp”，若多个文件则以文件夹”学号一姓名_sy序号”保存。以实验一为例子：1700000L李 四李四李四可保存为17000001_李四_syl”文件夹。2 .每次实验项目提交，请依据会师提供实验项目卡复制填写实验目的及实验内容，算法设计及测试运 行结果、存在问题分析等以实际填写。