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

实验6：二叉树的基本操作一、实验目的.掌握二叉树的非线性和递归性特点.理解二叉树的存储结构.掌握二叉树遍历操作二、实验内容1.使用二叉链表，创建一个如图(a)的二叉树。可以用先序、中序和后序方式遍历二叉树并将结点输出，.统计出一个二叉树叶子节点及树的深度。#include<iostream>#include<cstdio>usingnamespacestd;typedefcharDatatype;intent;structTNode(Datatypedata;TNode*rchild;TNode*Ichild;};voidCreatTree(TNode*&root)(charndata;cin»ndata;if(ndata=='#')root二NULL;else(root=newTNode;root->data=ndata;CreatTree(root->lchild);CreatTree(root->rchild);))voidpreOrderTraver(TNode*&root)〃先|if(root!=NULL)cout«root->data«nH;preOrderTraver(root->lchild);preOrderTraver(root->rchild);))voidInOrderTraver(TNode*&root)〃中(if(root!=NULL)(InOrderTraver(root->lchild);cout«root->data«nn;InOrderTraver(root->rchild);})voidposOrderTraver(TNode*&root)//后(if(root!=NULL)(posOrderTraver(root->lchild);posOrderTraver(root->rchild);cout«root->data«nn;))intBTHeight(TNode*t)/〃二叉树的深度{intans=0;if(t==NULL)return0;elseif(t!=NULL)ans+=max(ans,max(BTHeight(t->lchild),BTHeight(t->rchild))+1);returnans;)intBTLeaff4ode(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);returnent;)intmain()(TNode*root=NULL;cout<〈”请输入该二叉树的先序遍历结果:\n"；CreatTree(root);coutvv”先序遍历结果"vvendl;preOrderTraver(root);cout«endl;cout«"中序遍历结果:"<<endl;InOrderTraver(root);cout«endl;coutvv”后序遍历结果:“vvendl;posOrderTraver(root);cout«endl;printf("\n输出二叉树的深度：”)；intsum二BTHeight(root);cout«sum«endl;printf("输出二叉树的叶子结点：”)；intans二BTLeafNode(root);printf(n\n输出二叉树的叶子结点的个数：)cout«ans«endl;return0;)运行结果：存在问题：无2.对于给定的w二｛2,3,4,7,8,9｝权值，试构造一棵哈夫曼树，并给出各个节点的huffman编码及huffman数组的值。#defineN50〃叶子结点数#defineM2*N-1//树中结点总数typedefstruct(chardata[5];//结点值intweight;〃权重intparent;〃双亲结点intIchild;〃左孩子结点intrchild;〃右孩子结点｝HTNode;typedefstructcharcd[N];〃存放哈夫曼码intstart;}HCode;voidCreateHT(HTNodeht[],intn){inti,k,Inode,mode;doubleminl,min2;for(i=0;i<2*n-l;i++)〃所有结点的相关域置初值-1ht[i].parent=ht[i].lchild=ht[i].rchild-1;for(i=n;i<2*n-l;i++)〃构造哈夫曼树(min1=min2=32767;//Inode和mode为最小权重的两个结点位置lnode=rnode=-1;for(k=0;k<=i-l;k++)if(ht[k].parent--1)〃只在尚未构造二叉树的结点中查找(if(ht[k].weight<minl)(min2=min1;mode=lnode;min1=ht[k].weight;lnode=k;)else(if(ht[k].weight<min2)(min2=ht[k].weight;rnode=k;)))ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i].lchild=lnode;ht[i].rchild=rnode;ht[lnode].parent=i;ht[rnode].parent=i;voidCreateHCode(HTNodeht[],HCodehcd[],intn){inti,f,c;HCodehe;for(i=0;i<n;i++)//根据哈夫曼树求哈夫曼编码(f=ht[i].parent;while(f!=l)〃循序直到树根结点(if(ht[f].lchild==c)〃处理左孩子结点else〃处理右孩子结点c=f;f=ht[f].parent;}指向哈夫曼编码最开始字符hcd[i]=hc;}}voidDispHCode(HTNodeht[],HCodehcd[],intn){inti,k;intsum=0,m=0;intj;printf("输出哈夫曼数组的值及编码:\n");〃输出哈夫曼编码for(i=0;i<n;i++)(j=0；printf(n%s:\tH,ht[i].data);for(k=hcd[i].start;k<=n;k++)printf(n%cn,hcd[i].cd[k]);j++;)m+=ht[i].weight;sum+=ht[i].weighty;printf(H\nn);}printf(n\n带权路径长度WPL=%d\n”,sum);)intmain()(intn=6,i;//n表示初始字符串的个数char*str[]={"2T3'J417'J8：9'};intfnum[]={2,3,4,7,8,9};HTNodeht[M];HCodehcd[N];for(i=0;i<n;i++)(strcpy(ht[i].data,str[i]);ht[i].weight=fnum[i|;}printf(n\n!!);CreateHT(ht,n);CreateHCode(ht,hcd,n);DispHCode(ht,hcd,n);printf(n\nn);)测试数据：运行结果：存在问题：二、本次实验问题分析及学习建议备注：.每次实验完毕，各位学生可提交实验报告纸质（A4打印