[工学]数据结构实验四.doc

贵州大学实验报告学院：计信学院 专业：通信工程 班级：通信091姓名何川学号0908060235实验组实验时间2011.12、指导教师陈静成绩实验项目名称二叉树操作实验目的1、熟悉二叉树结点的结构和对二叉树的基本操作及具体实现。2、利用递归方法编写对二叉树的各种遍历算法。3、掌握递归方法在二叉树中的使用。实验要求1、认真阅读和掌握本实验内容所给的全部程序。2、在Visual C+6.0集成开发环境下编写和调试所有程序。3、编写的所有算法须给出测试函数，并自行设计测试数据，对算法进行测试。4、保存和打印出程序运行结果，并结合程序进行分析。5、按照你对二叉树操作的需要，重新改写主文件并运行，打印出主文件清单 和运行结果。实验原理Visual C+的编译环境下，独立完成实验要求的内容，独立完成编写、编以运行。实验仪器 安装了VC+6.0的PC机实验步骤1、 实现二叉树结点的定义和操作。该程序包括一个头文件，用来存储定义二叉树结构类型以及对二叉树进行各种操作的函数声明；第二个为操作的实现文件，用来存储每一种操作的具体函数定义以及主函数。二叉树的操作包括二叉树初始化、创建二叉树，判断二叉树是否为空，求二叉树的深度和结点数，遍历二叉树等。2、 已知二叉树的前序遍历序列和中序遍历序列，编写可唯一确定该二叉树的算法。3、根据所给的n个带权叶子结点，编写算法构造哈夫曼树和哈夫曼编码。实验内容（）typedef char ElemType;struct BTreeNodeElemType data;BTreeNode *left;BTreeNode *right;void InitBTree(BTreeNode *&BT);void CreatBTree(BTreeNode *&BT,char *a);bool EmptyBTree(BTreeNode *BT);void TraverseBTree(BTreeNode *BT);int BTreeDepth(BTreeNode *BT);int BTreeCount(BTreeNode &BT);void PrintBTree(BTreeNode *BT);#include <iostream>#include <stdlib.h>using namespace std; void InitBTree(BTreeNode *&BT)BT=NULL;void CreatBTree(BTreeNode *&BT,char *a)const int MaxSize=100;BTreeNode *sMaxSize;int top=-1;BT=NULL;BTreeNode *p;int k;int i=0;while(ai)switch(ai)case ' ':break;case '(':if(top=MaxSize-1)cout<<"栈空间不够，请重新分配栈空间!"<<endl;exit(1);top+;stop=p;k=1;break;case ')':if(top=-1)cout<<"二叉树广义表字符串错!"<<endl;exit(1);top-;break;case ',':k=2;break;default:p=new BTreeNode;p->data=ai;p->left=p->right=NULL;if(BT=NULL)BT=p;elseif(k=1)stop->left=p;elsestop->right=p;i+;bool EmptyBTree(BTreeNode *BT)return BT=NULL;void TraverseBTree(BTreeNode *BT)if(BT!=NULL)cout<<BT->data<<' 'TraverseBTree(BT->left);TraverseBTree(BT->right);int BTreeDepth(BTreeNode *BT)if(BT=NULL)return 0;else int i=BTreeDepth(BT->left);int j=BTreeDepth(BT->right); if(i>j) return i+1; else return j+1;int BTreeCount(BTreeNode *BT)if(BT=NULL)return 0;elseint i= BTreeCount(BT->left);int j= BTreeCount(BT->right); return i+j+1;void PrintBTree(BTreeNode *BT)if(BT!=NULL)cout<<BT->data;if(BT->left!=NULL|BT->right!=NULL)cout<<'('PrintBTree(BT->left);if(BT->right!=NULL)cout<<','PrintBTree(BT->right);cout<<')'void main()BTreeNode *bt;InitBTree(bt);char b50="A(B(C),D(E(F,G),H(,I)"CreatBTree(bt,b);PrintBTree(bt);cout<<endl;cout<<"前序:"TraverseBTree(bt);cout<<endl;cout<<"二叉树的深度为:"cout<<BTreeDepth(bt)<<endl;cout<<"二叉树的结点总数为:"cout<<BTreeCount(bt)<<endl;BTreeNode *PreMinCreateTree(char pre,char min,BTreeNode *&p,int i,int j,int len)BTreeNode *p,*q;for(i=0;i<len;i+) p->data=prei; for(j=0;j<len;j+) prei=minj; p->left=prei+1;(2) typedef char ElemType;struct BTreeNodeElemType data;BTreeNode *left;BTreeNode *right;BTreeNode *PreMinCreateTree(char pre,char min,BTreeNode *&p,int i,int j,int len);int Position(ElemType x, char a);void PrintBTree(BTreeNode *BT);#include "PreMinCreateTree.h"#include <iostream>#include <stdlib.h>using namespace std;int Position(ElemType x, char a)int i;for(i=0;i<8;i+)if(x=ai)return i;BTreeNode *PreMinCreateTree(char pre,char min,BTreeNode *&p,int i,int j,int len)int m,leftlen,rightlen;if(len<=0)p=NULL;elsep=new BTreeNode;p->data=prei;m=Position(prei,min);leftlen=m-j;rightlen=len-(leftlen+1);PreMinCreateTree(pre,min,p->left,i+1,j,leftlen);PreMinCreateTree(pre,min,p->right,i+leftlen+1,m+1,rightlen);return p;void PrintBTree(BTreeNode *BT)if(BT!=NULL)cout<<BT->data;if(BT->left!=NULL|BT->right!=NULL)cout<<'('PrintBTree(BT->left);if(BT->right!=NULL)cout<<','PrintBTree(BT->right);cout<<')'void main()char pre='a','b','c','d','e','f','g','h'char in='c','b','d','a','f','e','h','g'BTreeNode *p;int prestart=0;int preend=7;int instart=0;int inend=7;BTreeNode *bt;bt=PreMinCreateTree(pre,in,p,0,0,8);PrintBTree(bt);cout<<endl;(3) ) typedef int ElemType;struct BTreeNodeElemType data;BTreeNode *left;BTreeNode *right;BTreeNode *CreateHuffman(ElemType a,int n);void HuffManCoding(BTreeNode *FBT,int len);ElemType WeightPathLength(BTreeNode *FBT,int len);void PrintBTree(BTreeNode *BT);#include "huffman.h"#include <iostream>#include <stdlib.h>using namespace std;typedef int ElemType;struct BTreeNodeElemType data;BTreeNode *left;BTreeNode *right;BTreeNode *CreateHuffman(ElemType a,int n)BTreeNode*b,*q;b=new BTreeNode*n;int i,j;for(i=0;i<n;i+) bi=new BTreeNode; bi->data=ai; bi->left=bi->right=NULL; for(i=1;i<n;i+)int k1=-1,k2;for(j=0;j<n;j+)if(bj!=NULL&&k1=-1)k1=j;continue;if(bj!=NULL)k2=j;break;for(j=k2;j<n;j+)if(bj!=NULL)if(bj->data<bk1->data)k2=k1;k1=j;else if(bj->data<bk2->data) k2=j; q=new BTreeNode; q->data=bk1->data+bk2->data; q->left=bk1; q->right=bk2; bk1=q; bk2=NULL; delete b; return q;ElemType WeightPathLength(BTreeNode *FBT,int len)if(FBT=NULL) return 0;elseif(FBT->left=NULL&&FBT->right=NULL)return FBT->data*len;elsereturn WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);void HuffManCoding(BTreeNode *FBT,int len)static int a10;if(FBT!=NULL)if(FBT->left=NULL&&FBT->right=NULL)cout<<"节点权值为"<<FBT->data<<"的编码："for(int i=0;i<len;i+)cout<<ai<<' 'cout<<endl;elsealen=0;HuffManCoding(FBT->left,len+1);alen=1;HuffManCoding(FBT->right,len+1);void PrintBTree(BTreeNode *BT)if(BT!=NULL)cout<<BT->data;if(BT->left!=NULL |BT->right!=NULL)cout<<'('PrintBTree(BT->left);if(BT->right!=NULL)cout<<','PrintBTree(BT->right);cout<<')'void main()int i,n;BTreeNode *fbt=NULL;n=6;ElemType a6=3,9,5,12,6,15;fbt=CreateHuffman(a,n);cout<<"以广义表的形式输出哈夫曼树:"PrintBTree(fbt);cout<<endl;cout<<"哈夫曼树的权:"cout<<WeightPathLength(fbt,0)<<endl;cout<<"树中每个叶子结点的哈夫曼编码:"<<endl;HuffManCoding(fbt,0);实验数据(1) A(B(C),D(E(F,G),H(,I)前序:A B C D E F G H I二叉树的深度为:4二叉树的结点总数为:9请按任意键继续. . .(2) a(b(c,d),e(f,g(h)请按任意键继续. . .(3) 以广义表的形式输出哈夫曼树:50(21(9,12),29(14(6,8(3,5),15)哈夫曼树的权:122树中每个叶子结点的哈夫曼编码:节点权值为9的编码：0 0节点权值为12的编码：0 1节点权值为6的编码：1 0 0节点权值为3的编码：1 0 1 0节点权值为5的编码：1 0 1 1节点权值为15的编码：1 1请按任意键继续. . .实验总结 通过本次试验，是我熟悉和基本掌握了二叉树结点的结构和对二叉树的基本操作及具体实现。为以后更进一步的学习打下了基础。指导教师意见签名： 年 月 日