二叉树验证实验和哈夫曼编码的代码

树和二叉树实验六二叉树构造和遍历一.实验目的⑴掌握二叉树的逻辑结构；⑵掌握二叉树的二叉链表存储结构；⑶掌握基于二叉链表存储的二叉树的遍历操作的实现。二.实验环境Windows操作系统，VisualC++6.0编程环境。三.实验内容和步骤1．观察下面图6-1的二叉树，回答问题。图6-1（1）写出前序、中序和后序遍历序列；前序：ABDECFG中序：DBEAFGC后序：DEBGFCA（2）分别写单支结点和叶子结点；单支结点：CF叶子结点：DEG（3）以”#”补充所有结点的空分支；ABD##E##CF#G###（4）写出补充空分支后二叉树的前序遍历序列（扩展的前序遍历序列）；ABD##E##CF#G###2．建立工程Bitree，编写Biree.h，Biree.cpp和测试函数Bireemain.cpp,完成下列功能。⑴建立一棵含有n个结点的二叉树，采用二叉链表存储；⑵前序（或中序、后序）遍历该二叉树。四．编码头文件Bitree.h#includeiostreamusingnamespacestd;树和二叉树templateclassTstructBiNode{Tdata;BiNodeT*lchild,*rchild;};templateclassTclassBiTree{public:BiTree(){root=Creat(root);}//有参构造函数，初始化一棵二叉树，其前序序列由键盘输入~BiTree(){Release(root);}//析构函数，释放二叉链表中各结点的存储空间voidPreOrder(){PreOrder(root);}//前序遍历二叉树voidInOrder(){InOrder(root);}//中序遍历二叉树voidPostOrder(){PostOrder(root);}//后序遍历二叉树private:BiNodeT*root;//指向根结点的头指针BiNodeT*Creat(BiNodeT*bt);//有参构造函数调用voidRelease(BiNodeT*bt);//析构函数调用voidPreOrder(BiNodeT*bt);voidInOrder(BiNodeT*bt);voidPostOrder(BiNodeT*bt);};templateclassTBiNodeT*BiTreeT::Creat(BiNodeT*bt){Tch;cinch;if(ch=='#')bt=NULL;//建立一棵空树else{bt=newBiNodeT;//生成一个结点bt-data=ch;bt-lchild=Creat(bt-lchild);//递归建立左子树bt-rchild=Creat(bt-rchild);//递归建立右子树}returnbt;}树和二叉树templateclassTvoidBiTreeT::Release(BiNodeT*bt){if(bt!=NULL){Release(bt-lchild);Release(bt-rchild);deletebt;}}templateclassTvoidBiTreeT::PreOrder(BiNodeT*bt){if(bt==NULL)return;//递归调用的结束条件else{coutbt-data;//访问根结点的数据域PreOrder(bt-lchild);//前序递归遍历root的左子树PreOrder(bt-rchild);//前序递归遍历root的右子树}}templateclassTvoidBiTreeT::InOrder(BiNodeT*bt){if(bt==NULL)return;//递归调用的结束条件else{InOrder(bt-lchild);coutbt-data;InOrder(bt-rchild);}}templateclassTvoidBiTreeT::PostOrder(BiNodeT*bt){if(bt==NULL)return;//递归调用的结束条件else{PostOrder(bt-lchild);PostOrder(bt-rchild);coutbt-data;}树和二叉树}主函数main#includeBitree.hvoidmain(){intc=1;while(c){cout输入前序序列:;BiTreechartree;cout前序遍历:;tree.PreOrder();coutendl;cout中序遍历:;tree.InOrder();coutendl;cout后序遍历:;tree.PostOrder();coutendl;cout0.结束1.重试endl;cout请选择:;cinc;}}五.调试结果（表5-1）树和二叉树（表5-1）二叉树验证实验调试结果六．实验小结本次实验主要是通过实验过程掌握二叉树的逻辑结构，掌握二叉树的二叉链表存储结构和掌握基于二叉链表存储的二叉树的遍历操作的实现。树和二叉树哈夫曼编码代码#includeiostreamusingnamespacestd;constintSize=10,Size1=50;structelement{intweight;intlchild,rchild,parent;};intgetW(charT[],int*w,char*s){charc;intcount,k=0;for(inti=0;T[i]!='\0';i++){count=0;if(T[i]='a'&&T[1]='z'){c=T[i];s[k]=c;s[k+1]='\0';}if(c!='\0'){for(intj=0;T[j]!='\0';j++){if(T[j]==c){count++;T[j]='$';}}}if(c!='\0')w[k++]=count;c='\0';}returnk;}voidSelect(elementh[],int&i3,int&i4){intc;树和二叉树i3=-1;i4=-1;for(inti=0;i3==-1;i++)if(h[i].parent==-1)i3=i;for(i;i4==-1;i++)if(h[i].parent==-1)i4=i;if(h[i3].weighth[i4].weight){c=i3;i3=i4;i4=c;}for(i;h[i].weight0;i++){if(h[i].parent==-1)if(h[i].weighth[i3].weight)i4=i3,i3=i;elseif(h[i].weighth[i4].weight)i4=i;}}voidHuffmanTree(element*huffTree,intw[],intn){inti1,i2;for(inti=0;i2*n-1;i++){huffTree[i].parent=-1;huffTree[i].lchild=-1;huffTree[i].rchild=-1;}for(i=0;in;i++)huffTree[i].weight=w[i];for(intk=n;k2*n-1;k++){Select(huffTree,i1,i2);huffTree[i1].parent=k;huffTree[i2].parent=k;树和二叉树huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight;huffTree[k].lchild=i1;huffTree[k].rchild=i2;}}voidbm(elementh[],intm){charb[Size];b[0]='\0';ints[Size],cd;inttop=-1,i=0,k;while(m!=-1||top!=-1){while(m!=-1){if(h[m].lchild==-1&&h[m].rchild==-1)//记录路径编码‘0’，‘1’的算法，用到parent回溯。{cd=0;for(intj=h[m].parent;j!=-1;j=h[j].parent)cd++;b[cd]='\0';k=m;for(j=h[k].parent;j!=-1;j=h[j].parent){if(h[j].lchild==k)b[--cd]='0';elseb[--cd]='1';k=j;}couth[m].weight:bendl;}s[++top]=m;m=h[m].lchild;}if(top!=-1){m=s[top--];m=h[m].rchild;}}树和二叉树}voidmain(){charT[Size1],s[Size];intw[Size],n;cout输入字符串：;gets(T);n=getW(T,w,s);for(inti=0;in;i++)couts[i]w[i]endl;elementhuffTree[Size1];HuffmanTree(huffTree,w,n);cout编码：endl;bm(huffTree,2*n-2);}