二叉树验证实验和哈夫曼编码的代码(共9页).doc
精选优质文档-倾情为你奉上实验六 二叉树构造和遍历一. 实验目的 掌握二叉树的逻辑结构； 掌握二叉树的二叉链表存储结构； 掌握基于二叉链表存储的二叉树的遍历操作的实现。二. 实验环境Windows操作系统，Visual C+ 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#include<iostream>using namespace std;template <class T>struct BiNodeT data; BiNode<T> *lchild, *rchild;template <class T>class BiTreepublic:BiTree()root=Creat(root); /有参构造函数，初始化一棵二叉树，其前序序列由键盘输入 BiTree()Release(root); /析构函数，释放二叉链表中各结点的存储空间 void PreOrder()PreOrder(root); /前序遍历二叉树 void InOrder()InOrder(root); /中序遍历二叉树 void PostOrder()PostOrder(root); /后序遍历二叉树private: BiNode<T> *root; /指向根结点的头指针 BiNode<T> *Creat(BiNode<T> *bt); /有参构造函数调用 void Release(BiNode<T> *bt); /析构函数调用 void PreOrder(BiNode<T> *bt); void InOrder(BiNode<T> *bt); void PostOrder(BiNode<T> *bt);template <class T>BiNode<T> *BiTree<T>:Creat(BiNode<T> *bt)T ch; cin>>ch; if(ch='#')bt=NULL; /建立一棵空树 else bt=new BiNode<T> /生成一个结点 bt->data=ch; bt->lchild=Creat(bt->lchild); /递归建立左子树 bt->rchild=Creat(bt->rchild); /递归建立右子树return bt;template <class T>void BiTree<T>:Release(BiNode<T> *bt)if(bt!=NULL)Release(bt->lchild);Release(bt->rchild);delete bt;template <class T>void BiTree<T>:PreOrder(BiNode<T> *bt) if (bt=NULL) return; /递归调用的结束条件 else cout<<bt->data; /访问根结点的数据域 PreOrder(bt->lchild); /前序递归遍历root的左子树 PreOrder(bt->rchild); /前序递归遍历root的右子树 template <class T>void BiTree<T>:InOrder(BiNode<T> *bt) if (bt=NULL) return; /递归调用的结束条件 else InOrder(bt->lchild);cout<<bt->data; InOrder(bt->rchild); template <class T>void BiTree<T>:PostOrder(BiNode<T> *bt) if (bt=NULL) return; /递归调用的结束条件 else PostOrder(bt->lchild); PostOrder(bt->rchild);cout<<bt->data; 主函数main#include"Bitree.h"void main()int c=1;while(c)cout<<"输入前序序列:"BiTree<char> tree;cout<<"前序遍历:"tree.PreOrder();cout<<endl; cout<<"中序遍历:"tree.InOrder();cout<<endl;cout<<"后序遍历:"tree.PostOrder();cout<<endl;cout<<"0.结束 1.重试"<<endl;cout<<"请选择:"cin>>c;五.调试结果（表5-1） （表5-1）二叉树验证实验调试结果六实验小结本次实验主要是通过实验过程掌握二叉树的逻辑结构，掌握二叉树的二叉链表存储结构和掌握基于二叉链表存储的二叉树的遍历操作的实现。哈夫曼编码代码#include<iostream>using namespace std;const int Size=10,Size1=50; struct elementint weight;int lchild,rchild,parent;int getW(char T,int *w,char *s)char c;int count,k=0;for(int i=0;Ti!='0'i+)count=0;if(Ti>='a'&&T1<='z') c=Ti;sk=c;sk+1='0'if(c!='0')for(int j=0;Tj!='0'j+)if(Tj=c)count+; Tj='$'if(c!='0') wk+=count;c='0'return k;void Select(element h,int &i3,int &i4)int c;i3=-1;i4=-1;for(int i=0;i3=-1;i+)if(hi.parent=-1)i3=i;for(i;i4=-1;i+)if(hi.parent=-1)i4=i;if(hi3.weight>hi4.weight) c=i3;i3=i4;i4=c;for(i;hi.weight>0;i+)if(hi.parent=-1)if(hi.weight<hi3.weight)i4=i3,i3=i;else if(hi.weight<hi4.weight)i4=i;void HuffmanTree(element *huffTree,int w,int n)int i1,i2;for(int i=0;i<2*n-1;i+)huffTreei.parent=-1; huffTreei.lchild=-1; huffTreei.rchild=-1;for(i=0;i<n;i+)huffTreei.weight=wi;for(int k=n;k<2*n-1;k+)Select(huffTree,i1,i2);huffTreei1.parent=k;huffTreei2.parent=k; huffTreek.weight=huffTreei1.weight+huffTreei2.weight; huffTreek.lchild=i1; huffTreek.rchild=i2;void bm(element h,int m)char bSize;b0='0' int sSize,cd;int top=-1,i=0,k;while(m!=-1|top!=-1)while(m!=-1)if(hm.lchild=-1 && hm.rchild=-1)/记录路径编码0，1的算法，用到parent回溯。cd=0;for(int j=hm.parent;j!=-1;j=hj.parent)cd+;bcd='0'k=m;for(j=hk.parent;j!=-1;j=hj.parent)if(hj.lchild=k) b-cd='0'else b-cd='1'k=j;cout<<hm.weight<<":"<<b<<endl;s+top=m;m=hm.lchild;if(top!=-1)m=stop-;m=hm.rchild;void main()char TSize1,sSize;int wSize,n;cout<<"输入字符串："gets(T);n=getW(T,w,s); for(int i=0;i<n;i+)cout<<si<<" "<<wi<<endl;element huffTreeSize1; HuffmanTree(huffTree,w,n);cout<<"编码："<<endl;bm(huffTree,2*n-2);专心-专注-专业
