《树二叉树的创建及输出哈夫曼编码的输出》由会员分享，可在线阅读，更多相关《树二叉树的创建及输出哈夫曼编码的输出（28页珍藏版）》请在金锄头文库上搜索。
1、一、实验目的：1. 学会实现二叉树结点结构和对二叉树的基本操作。2. 掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树 这种递归数据结构进行处理的算法。3. 掌握树的创建即对它的遍历，输出树，以及叶子结点，根结点。4. 哈夫曼树的建立与编码的输出。二、实验环境：装有Visual C+6.0的windons.7系统的计算机一台三、实验内容与步骤:1.二叉树的创建及输出。m.h文件:Q File Edit View Insert Project Build Tools Window Help| node (All class members t|No members - Create
2、C/C+ Memb 殴 TWorkspace xxt： 1 pro -xxt files-_J Source Files 酉 m.cpp 酉 StdAfx.cpp 酉 xxt.cpp-_J Header FilesttincludestdaFx.h include ttinclude ttdefine MaxSize 10S typedef char ElemTijpe; typedef struct node骂m.h骂 StdAfx.h_| Resource Files 骂 ReadMe.txtElemType data;/啖据7L素可struct node *lchild;指向左孩子结点可
3、struct node *rchild;指向右孩子结点可 BTNode;BTNode *CreateBT1(char *pre,char *in,int n); BTNode *CreateBT2(char *post,char *in,int n); uoid CreateBTNode(BTNode * &b,char *str); uoid DispBTNode(BTNode *b);BTNode *FindNode(BTNode *b.ElemType x);BTNode *LchildNode(BTNode *p);BTNode RchildNode(BTNode *p); int B
4、TNodeHeight(BTNode *b); pBTNode(BTNode *b);#includestdafx.h#include stdio.h#include malloc.h#define MaxSize 100typedef char ElemType;typedef struct nodeElemType da ta;/* 数据元素*/st ruct node *lchild; /* 指向左孩子结点*/ st ruct node *rchild; /* 指向右孩子结点*/ BTNode;BTNode *CreateBTl(char *pre,char *in ,int n);BT
5、Node *CreateBT2(char *post,char *in ,int n); void CreateBTNode(BTNode * &b,char *str); void DispBTNode(BTNode *b);BTNode *FindNode(BTNode *b,ElemType x);BTNode *LchildNode(BTNode *p);BTNode *RchildNode(BTNode *p);int BTNodeHeight(BTNode *b); pBTNode(BTNode *b);m.cpp#include stdafx.h #includestdio.h
6、#include m.hBTNode *CreateBTl(char *pre,char *in ,int n) /*pre存放先序序列,in存放中序序列,n为二叉树结点个数, 本算法执行后返回构造的二叉链的根结点指针*/BTNode *s;char *p;int k;if (nlch il d=Crea teBTl(pre+l,in,k);/* 递归构造左子树*/srch il d=Crea teBTl(pre+k+l,p+l,n-kT); /* 递归构造右子树*/return s;BTNode *CreateBT2(char *post,char *in ,int n)/*post存放后序
7、序列，in存放中序序列,n为二叉树结点个数, 本算法执行后返回构造的二叉链的根结点指针*/BTNode *s;char r,*p;int k;if (n=0) return NULL;r=*(post+n1);/*根结点值*/s=(BTNode *)malloc(sizeof(BTNode);/* 创建二叉树结点 *s*/sdata二r;for (p=in;plchild=Crea teBT2(pos t,i n,k);/*递归构造左子树*/srch il d=Crea teBT2(pos t+k,p+l,n-k-l); /* 递归构造右子树*/return s;void CreateBTNo
8、de(BTNode * &b,char *str)BTNode *StMaxSize,*p二NULL;int to p=_1,k,j=0;char ch;b二NULL;/*建立的二叉树初始时为空*/ch=strj;while (ch!=0)/*str 未扫描完时循环*/swit ch(ch)case (:to p+;S tto p=p;k=1; break;/* 为左孩子结点*/case ):top;break;case ,:k=2; break;/* 为孩子结点右结点*/default:p=(BTNode *)malloc(sizeof(BTNode);p-data二ch;p-lchild二
9、p-rchild二NULL;if (b二二NULL)/*p 为二叉树的根结点*/b=p;else/*已建立二叉树根结点*/swit ch(k)case 1:Sttop-lchild二p;break; case 2:Sttop-rchild二p;break;j+；ch=strj;void DispBTNode(BTNode *b)if (b!二NULL) pri ntf (%c,b-da ta);if (b-lchild!二NULLb-rchild!二NULL) prin tf();/*有孩子结点时才输出（*/DispBTNode(b-lchild);/* 递归处理左子树*/if (b-rchi
10、ld!二NULL) prin tf(,);/* 有右孩子结点时才输出，*/DispBTNode(b-rchild);pri ntf();/*递归处理右子树*/*有孩子结点时才输出）*/BTNode *FindNode(BTNode *b,ElemType x)BTNode *p; if (b二二NULL)return NULL;else if (b-data=x)return b;elsep二FindNode(b-lchild,x);if (p!二NULL)return p;elsereturn FindNode(b-rchild,x);BTNode *LchildNode(BTNode *p
11、)return p-lchild;BTNode *RchildNode(BTNode *p)return p-rchild;int BTNodeHeight(BTNode *b)int lchildh,rchildh;if (b二二NULL) return(0);/*空树的高度为 0*/elselchildh二BTNodeHeight(b-lchild); /* 求左 子树的 高度为 lchildh*/rch il dh二BTNodeHeigh t(b-rchild); /* 求右子树的高度为 rchildh*/return (lchildhrchildh)? (lchildh+l):(rch
12、ildh+l);11 Workspace xxt1： 1 pro -Ol xxt files-6 Source Files圈 m.cpp圈 StdAfx.cpp 囲 xxt.cpp工程文件Xtt.cppQ f衲需齬龜S?- Cl - |c嗨Cj|(Globals (All global membersl main辺 XKt - Microsoft Visual C+ - xxt.cpp */ xxt.cpp : Defines the entry point for the console applicati /国 File Edit View Insert Project Build Too
13、ls Window Helpttinclude stdafx.h ttinclude itincludaF.ti int mainfint argc , char* argu)-Header FilesHl m.h宣 StdAfx.hOl Resource FilesP| ReadMe.txtElemType pre=ABDGCEF,in=DGBAECF,post=GDBEFCA; BTNode *b1,*b2;b1=CreateBT1(pre ,in ,7); printF(b1:);DispBTNode(b1);printF(n); b2=CreateBT2(post ,in ,7);printF(b2:):DispBTNode(b2);printf(Xn);BTNode *b;CreateBTNode(b,A(B(D,E),C(,F);DispB
