《实验三二叉树的基本运算.docx》由会员分享，可在线阅读，更多相关《实验三二叉树的基本运算.docx（17页珍藏版）》请在三一办公上搜索。
1、数据结构实验报告（实验三&实验四）班级：软件121 学号：201200834122姓名：实验三二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容问题描述建立一棵二叉树，试编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表小的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分 别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；（选做）4. 将二叉树每个结点的左右子树交换位置。（选做）基本要求从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），测试数据如输
2、入：ABCSDEGSFSS （其中S表示空格字符）则输出结果为先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA层序：ABCDEFG选作内容采用非递归算法实现二叉树遍历。三、实验前的准备工作1、掌握树的逻辑结构。2、掌握二叉树的逻辑结构和存储结构。3、掌握二叉树的各种遍历算法的实现。四、源代码#include#include#include#include定义二叉树结点类型templateclass BinaryTree;template struct BTreeNode (private:BTreeNode *left;/左子树指针BTreeNode *right;/佑子树指针pu
3、blic:T data;/数 据域构造函数BTreeNode():left(NULL),right(NULL) BTreeNode(T item,BTreeNode *left1=NULL,BTreeNode *right1=NULL):data(item), left(left1),right(right1) BTreeNode *&Left()return left;BTreeNode *&Right()return right; friend class BinaryTree;/二叉树类定义templateclass BinaryTree private:BTreeNode *root;
4、public:构造函数，初始化二叉树为空BinaryTree() root=NULL;/根据字符数组a的二叉树广义表建立对应的二叉树存储结构void CreateBTree(char* a);/判断二叉树是否为空bool BTreeEmpty() return root=NULL;按任一种遍历次序输出二叉树中的所有结点 void TraverseBTree(int mark);/用于遍历的递归函数void Traverse(BTreeNode *&BT,int mark);/求二叉树的深度int BTreeDepth();/用于求二叉树深度的递归函数int Depth(BTreeNode *&
5、BT);/求二叉树中所有结点数int BTreeCount();/用于求二叉树中所有结点数的递归函数int Count(BTreeNode *&BT);/求二叉树中所有叶子结点数int BTreeLeafCount();/用于求二叉树中所有叶子结点数的递归函数int LeafCount(BTreeNode *&BT);按照二叉树的一种表示方法输出整个二叉树void PrintBTree();/用于输出整个二叉树的递归函数void Print(BTreeNode *&BT);/用于清除二叉树的递归函数void Clear(BTreeNode *&BT);/析构函数，清除二叉树BinaryTree
6、();/根据字符数组a的二叉树广义表建立对应的二叉树存储结构templatevoid BinaryTree:CreateBTree(char *a)BTreeNode *s80;/s数组作为存储二叉树中根结点指针的栈int top=-1;/top作为s栈的栈顶指针root=NULL;给树根指针置空BTreeNode *p=NULL;/定义p为指向二叉树结点的指针/用k作为处理结点的左子树和右子树的标记,k=1处理左子树,k=2处理右 子树int k;istrstream ins(a);/把字符串a定义为输入字符串流对象ins char ch;insch;/从 ins流对象顺序读入一个字符，wh
7、ile (ch!=)每循环一次处理一个读入的字符，直到扫描到字符为止switch(ch)case (:top+;stop=p;k=1;break;case ):top-;break;case ,:top+;k=2;break;default:p=new BTreeNode;p-data=ch;p-left=p-right=NULL;coutsetw(2)data;if(root=NULL) root=p;else if(k=1) stop-left=p;else stop-right=p;insch;按任一种遍历次序输出二叉树中的所有结点templatevoid BinaryTree:Trav
8、erseBTree(int mark)Traverse(root,mark);/用于遍历的递归函数templatevoid BinaryTree:Traverse(BTreeNode *&BT,int mark)if(mark=1) /先序遍历if(BT!=NULL)coutdataleft,mark);Traverse(BT-right,mark);elseif(mark=2)/ 中序遍历if(BT!=NULL)Traverse(BT-left,mark);coutdataright,mark);elseif(mark=3) /后序遍历if(BT!=NULL) Traverse(BT-lef
9、t,mark);Traverse(BT-right,mark);coutdata;elseif(mark=4) /按层遍历const MaxLength=80;BTreeNode *QMaxLength;定义存储二叉树结点指针的数组空间作为队列使用 int front=0, rear=0;定义队首指针和队尾指针，初始均置0表示空队BTreeNode *p;if(BT!=NULL) rear=(rear+1)%MaxLength; /后移队尾指针Qrear=BT;将树根结点指针进队while(front!=rear)当队列非空时执行循环front=(front+1)%MaxLength;/后移队
10、首指针p=Qfront;删除队首结点coutdataleft!=NULL)/若结点存在左孩子，则左孩子结点指针进队rear=(rear+1)%MaxLength;Qrear=p-left;if(p-right!=NULL)/若结点存在右孩子，则右孩子结点指针进队rear=(rear+1)%MaxLength;Qrear=p-right;else(cerrmark 的值无效!遍历失败!”endl;exit(1);/求二叉树的深度templateint BinaryTree:BTreeDepth()(return Depth(root);/用于求二叉树深度的递归函数templateint Bina
11、ryTree:Depth(BTreeNode *&BT)(if(BT=NULL) return 0;/对于空树，返回0并结束递归 else(计算左子树的深度int dep1=Depth(BT-left);计算右子树的深度int dep2=Depth(BT-right);/返回树的深度if(dep1dep2) return dep1+1;else return dep2+1;/求二叉树中所有结点数templateint BinaryTree:BTreeCount()(return Count(root);/用于求二叉树中所有结点数的递归函数templateint BinaryTree:Count
12、(BTreeNode *&BT) (if(BT=NULL) return 0;elsereturn Count(BT-left)+Count(BT-right)+1;/求二叉树中所有叶子结点数templateint BinaryTree:BTreeLeafCount()(return LeafCount(root);/用于求二叉树中所有叶子结点数的递归函数templateint BinaryTree:LeafCount(BTreeNode *&BT) (if(BT=NULL) return 0;else if(BT-left=NULL & BT-right=NULL) return 1;els
13、e return LeafCount(BT-left)+LeafCount(BT-right);/按照二叉树的广义表表示输出整个二叉树templatevoid BinaryTree:PrintBTree()(Print(root);/用于输出整个二叉树的递归函数templatevoid BinaryTree:Print(BTreeNode *&BT)(if(BT=NULL) return;/树为空时返回else (/否则执行如下操作coutdata;/输出根结点的值if(BT-left!=NULL II BT-right!=NULL)(coutleft);/输出左子树if(BT-right!=
14、NULL)coutright);/输出右子树coutvv); /输出右括号/析构函数，清除二叉树templateBinaryTree:BinaryTree()(Clear(root);/用于清除二叉树的递归函数 template void BinaryTree:Clear(BTreeNode *&BT) if(BT!=NULL) 当二叉树非空时进行如下操作Clear(BT-left); /删除左子树 Clear(BT-right);/删 除右子树 delete BT;删除根结点BT=NULL;置根指针为空 void main() int n; char b80=(A)(B),C(D),E(F)
15、,G(H),I(J),K(L),M(N),O; BinaryTree B;cout创建的二叉树为:n”; B.CreateBTree(b);coutendl; if(!B.BTreeEmpty() cout”二叉树非空!n; elsecout”二叉树为空!n; cout先序遍历二叉树:n; B.TraverseBTree(1);coutendl; cout中序遍历二叉树:n; B.TraverseBTree(2);coutendl; cout后序遍历二叉树:n; B.TraverseBTree(3);coutendl; cout按层遍历二叉树:n; B.TraverseBTree(4);cou
16、tendl; n=B.BTreeDepth(); cout二叉树的深度=nendl; n=B.BTreeCount(); cout”二叉树的所有结点数=nendl; n=B.BTreeLeafCount(); cout”二叉树的所有叶子结点数=nendl; cout按二叉树的广义表输出:n;B.PrintBTree();coutendl; 五、实验过程实验四哈夫曼树与哈夫曼编码一、实验目的1、熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。二、实验内容问题描述已知n个字符在原文中出现的频率，求它们的哈夫曼编码。基本要求1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffma
17、n树。（具体算法可参见教材P147的算法6.12）2. 编码：根据建立的Huffman树，求每个字符的Huffman 编码。对给定的待编码字符序列进行编码。选作内容3. 译码：利用已经建立好的Huffman树，对上面的编码结果 译码。译码的过程是分解电文中的字符串，从根结点出发，按字符0 和1确定找左孩子或右孩子，直至叶结点，便求得该子串相应的 字符。4. 打印 Huffman 树。测试数据利用教材P.148例6-2中的数据调试程序。可设8种符号 分别为A,B,C,D,E,F,G,H。编/译码序列为“CFBABBFHGH”（也可 自己设定数据进行测试）。三、实验前的准备工作1、掌握树的逻辑结构
18、。2、掌握哈夫曼树的定义及生成算法。3、掌握哈夫曼编码的方法。四、源代码/赫夫曼树与赫夫曼编码#include#include#include const int MaxV=1000;/初始设定的最大权值const int MaxBit=10;/初始设定的最大编码位数const int MaxN=10;/初始设定的最大结点数/赫夫曼树的结点结构typedef structint weight;/权值int flag; 标十己int parent;/双亲结点下标int left;/左孩子下标int right;/右 孩子下标HuffNode;typedef structint bitMaxN;/
19、存 放编码数组int start;/编码的起始下标int weight;/字 符的权值Code;类定义class HuffmanTpublic:构造函数HuffmanT(HuffNode *&,Code *&,int);创建叶结点个数为n,权值数组为weight的赫夫曼树HuffTree void MakeHufm(int weight,int n);由n个结点的赫夫曼树HuffTree构造赫夫曼编码huffCodevoid HuffCode(int n);private:HuffNode *HuffTree;Code *huffCode;HuffmanT:HuffmanT(HuffNode
20、*&huffnode,Code *&huCode,int n) huffnode=new HuffNode2*n+1;huCode=new Coden;HuffTree=huffnode;huffCode=huCode;void HuffmanT:MakeHufm(int weight,int n)int j,m1,m2,x1,x2,i;/赫夫曼树HuffTree的初始化for(i=0;i2*n-1;i+)if(in) HuffTreei.weight=weighti;else HuffTreei.weight=0;HuffTreei.parent=0;HuffTreei.flag=0;Huf
21、fTreei.left=-1;HuffTreei.right=-1;构造赫夫曼树HuffTree的n-1个非叶结点for(i=0;in-1;i+)m1=m2=MaxV;x1=x2=0;for(j=0;jn+i;j+)if(HuffTreej.weightm1&HuffTreej.flag=0)m2=m1;x2=x1;m1=HuffTreej.weight;x1=j;else if(HuffTreej.weightm2&HuffTreej.flag=0)m2=HuffTreej.weight;x2=j;/将找出的两棵权值最小的子树合并为一棵子树HuffTreex1.parent=n+i;Huff
22、Treex2.parent=n+i;HuffTreex1.flag=1;HuffTreex2.flag=1;HuffTreen+i.weight=HuffTreex1.weight+HuffTreex2.weight;HuffTreen+i.left=x1;HuffTreen+i.right=x2;void HuffmanT:HuffCode(int n)Code *cd=new Code;int child,parent;/求n个叶结点的赫夫曼编码for(int i=0;istart=n-1;/不等长编码的最后一位为n-1cd-weight=HuffTreei.weight;/取 得编码对应
23、权值的字符 child=i;parent=HuffTreechild.parent;由叶结点向上直到根结点while(parent!=0)if(HuffTreeparent.left=child)cd-bitcd-start=0;/左孩子结点编码 0elsecd-bitcd-start=1;/右 孩子结点编码 1 cd-start-;child=parent;parent=HuffTreechild.parent;/保存每个叶结点的编码和不等长编码的起始位for(int j=cd-start+1;jbitj;huffCodei.start=cd-start;huffCodei.weight=c
24、d-weight;/i己住编码对应权值的字符 /赫夫曼编码问题的测试void main()int i,j,n;coutn;int weight10;cout其权值依次为：”；for(i=0;iweighti;HuffNode *myHuffTree;Code *myHuffCode;HuffmanT t(myHuffTree,myHuffCode,n);if(nMaxN)coutn 越界，修改 MaxN!n;exit(1);t.MakeHufm(weight,n);t.HuffCode(n);输出每个叶结点的赫夫曼编码coutHuffman编码问题的运行结果:n;for(i=0;in;i+)(
25、cout权值 weight=setw(2)myHuffCodei.weightsetw(2)” 其对应的赫夫曼码Huffman Code=;for(j=myHuffCodei.start+1;jn;j+)coutmyHuffCodei.bitj;coutendl;cin.get();五、实验过程1.第一组rE:ll llllgg g gg gDe bugiiiiiii.exe6 回请输入要测试节点个数（。-项）：4.| 4 &_卜r E:IIHIIIgg g gggDe bugiiiiiii.exe2.第二组3.第三组I E:lll lllgqqagqDebLiqiiiiiii.exe口回00
26、0 001 110 111 0110CodeCodeCodeCodeCodeCodeaaaaaa m m m m m m f f f f f f f f f f f f u u u u u u H H H H H H 马马马马马马 G I-巾G ? G用 曼曼曼曼曼曼 h-_匕- am.Hm.-7 -H8 - T 1果的的的的的的lie C012蔑应应应应应in 一 丁一：T. 一、. 一： 一、.T. t IrTx. 9 Erv.-乂7.-X7.-1 X n 8圭比堂食登食堂国 5 的 O 养题 589271 t FT.旬 1 1 2 y 讯为驴t=t=t=t=t=t=ke h h h h
27、h h M.1.!:.扁 g g ggg g y 隼甫eieieieieieian A值二： 朝机Ff值值值值值值Bs BFHufppe4.第四组E:llllllggggggDebijgiiiiiii.exe):814 15 1701100 01101 Bill 010 110 111 00 10CodeCodeCodeCodeCodeCodeCodeCodennnnnnnn aaaaaaaa ffffffff uuuuuuuu HHHHHHHH 马马马马马马马.马. T巾I-巾I-巾I-巾I-巾I-巾I-巾I-巾 曼曼曼曼* 4.,4.,4.,4.,4.,4.孑0 诱 1 1 ITTe 1 Er- r*TT l-r- l_r-1rT.llrT.I1rT.IlrT.Ilr一a 7S应应应应应应应in 一 丁一.：一.：一.：一.：一.：一.：一.：一、. t 攵 5 E-r7.-7.-7.-7.-乂?.-1 乂?.-1 n 后宜纹纹纹纹纹纹套m13571457i i i i试为奇t=t=t=t=t=t=t=t= 测欲制ssss eieieieieieieiei 入值 wwwwwwww 曹HUFEEEEEEEErrr
