树,二叉树的创建及输出.哈夫曼编码的输出

1、一、实验目的：1.学会实现二叉树结点结构和对二叉树的基本操作。2.掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。3掌握树的创建即对它的遍历，输出树，以及叶子结点，根结点。4哈夫曼树的建立与编码的输出。二、实验环境：装有Visual C+6.0的windons.7系统的计算机一台3、 实验内容与步骤：1.二叉树的创建及输出。m.h文件：#include"stdafx.h"#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char

2、ElemType;typedef struct node ElemType data;/*数据元素*/struct node *lchild;/*指向左孩子结点*/struct node *rchild;/*指向右孩子结点*/ BTNode;BTNode *CreateBT1(char *pre,char *in,int n);BTNode *CreateBT2(char *post,char *in,int n);void CreateBTNode(BTNode * &b,char *str);void DispBTNode(BTNode *b); BTNode *FindNode(

3、BTNode *b,ElemType x) ;BTNode *LchildNode(BTNode *p);BTNode *RchildNode(BTNode *p);int BTNodeHeight(BTNode *b); pBTNode(BTNode *b);m.cpp #include "stdafx.h"#include<stdio.h>#include "m.h"BTNode *CreateBT1(char *pre,char *in,int n)/*pre存放先序序列,in存放中序序列,n为二叉树结点个数,本算法执行后返回构造的二叉

4、链的根结点指针*/BTNode *s;char *p;int k;if (n<=0) return NULL;s=(BTNode *)malloc(sizeof(BTNode);/*创建二叉树结点*s*/s->data=*pre;for (p=in;p<in+n;p+)/*在中序序列中找等于*ppos的位置k*/if (*p=*pre)/*pre指向根结点*/break;/*在in中找到后退出循环*/k=p-in;/*确定根结点在in中的位置*/s->lchild=CreateBT1(pre+1,in,k);/*递归构造左子树*/s->rchild=CreateB

5、T1(pre+k+1,p+1,n-k-1); /*递归构造右子树*/return s;BTNode *CreateBT2(char *post,char *in,int n)/*post存放后序序列,in存放中序序列,n为二叉树结点个数,本算法执行后返回构造的二叉链的根结点指针*/BTNode *s;char r,*p;int k;if (n<=0) return NULL;r=*(post+n-1);/*根结点值*/s=(BTNode *)malloc(sizeof(BTNode);/*创建二叉树结点*s*/s->data=r;for (p=in;p<in+n;p+)/*在

6、in中查找根结点*/if (*p=r)break;k=p-in;/*k为根结点在in中的下标*/s->lchild=CreateBT2(post,in,k);/*递归构造左子树*/s->rchild=CreateBT2(post+k,p+1,n-k-1);/*递归构造右子树*/return s;void CreateBTNode(BTNode * &b,char *str)BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/*建立的二叉树初始时为空*/ch=strj;while (ch!='0

7、9;) /*str未扫描完时循环*/ switch(ch) case '(':top+;Sttop=p;k=1; break;/*为左孩子结点*/case ')':top-;break;case ',':k=2; break; /*为孩子结点右结点*/default:p=(BTNode *)malloc(sizeof(BTNode);p->data=ch;p->lchild=p->rchild=NULL;if (b=NULL) /*p为二叉树的根结点*/ b=p;else /*已建立二叉树根结点*/switch(k) case

8、1:Sttop->lchild=p;break;case 2:Sttop->rchild=p;break;j+;ch=strj;void DispBTNode(BTNode *b) if (b!=NULL)printf("%c",b->data);if (b->lchild!=NULL | b->rchild!=NULL)printf("(");/*有孩子结点时才输出(*/DispBTNode(b->lchild);/*递归处理左子树*/if (b->rchild!=NULL) printf(",&qu

9、ot;);/*有右孩子结点时才输出,*/DispBTNode(b->rchild);/*递归处理右子树*/printf(")");/*有孩子结点时才输出)*/BTNode *FindNode(BTNode *b,ElemType x) BTNode *p;if (b=NULL)return NULL;else if (b->data=x)return b;else p=FindNode(b->lchild,x);if (p!=NULL) return p;else return FindNode(b->rchild,x);BTNode *Lchild

10、Node(BTNode *p) return p->lchild;BTNode *RchildNode(BTNode *p) return p->rchild;int BTNodeHeight(BTNode *b) int lchildh,rchildh; if (b=NULL) return(0); /*空树的高度为0*/ else lchildh=BTNodeHeight(b->lchild);/*求左子树的高度为lchildh*/rchildh=BTNodeHeight(b->rchild);/*求右子树的高度为rchildh*/return (lchildh&g

11、t;rchildh)? (lchildh+1):(rchildh+1); 工程文件xtt.cpp/ xxt.cpp : Defines the entry point for the console application./#include "stdafx.h"#include<stdio.h>#include"m.h"int main(int argc, char* argv)ElemType pre="ABDGCEF",in="DGBAECF",post="GDBEFCA"BT

12、Node *b1,*b2;b1=CreateBT1(pre,in,7);printf("b1:");DispBTNode(b1);printf("n");b2=CreateBT2(post,in,7);printf("b2:");DispBTNode(b2);printf("n");BTNode *b;CreateBTNode(b,"A(B(D,E),C(,F)");DispBTNode(b);printf("n");return 0;运行结果如下2树的子叶xhX.cpp代码

13、为：#include <malloc.h>#include "stdafx.h"#include<stdio.h>#include"x.h"void CreateBTNode(BTNode * &b,char *str)BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/*建立的二叉树初始时为空*/ch=strj;while (ch!='0') /*str未扫描完时循环*/ switch(ch) case '(':top+;

14、Sttop=p;k=1; break;/*为左孩子结点*/case ')':top-;break;case ',':k=2; break; /*为孩子结点右结点*/default:p=(BTNode *)malloc(sizeof(BTNode);p->data=ch;p->lchild=p->rchild=NULL;if (b=NULL) /*p为二叉树的根结点*/b=p;else /*已建立二叉树根结点*/switch(k) case 1:Sttop->lchild=p;break;case 2:Sttop->rchild=p;

15、break;j+;ch=strj;BTNode *FindNode(BTNode *b,ElemType x) BTNode *p;if (b=NULL)return NULL;else if (b->data=x)return b;else p=FindNode(b->lchild,x);if (p!=NULL) return p;else return FindNode(b->rchild,x);BTNode *LchildNode(BTNode *p) return p->lchild;BTNode *RchildNode(BTNode *p) return p-

16、>rchild;int BTNodeHeight(BTNode *b) int lchildh,rchildh; if (b=NULL) return(0); /*空树的高度为0*/ else lchildh=BTNodeHeight(b->lchild);/*求左子树的高度为lchildh*/rchildh=BTNodeHeight(b->rchild);/*求右子树的高度为rchildh*/return (lchildh>rchildh)? (lchildh+1):(rchildh+1); void DispBTNode(BTNode *b) if (b!=NULL

17、)printf("%c",b->data);if (b->lchild!=NULL | b->rchild!=NULL)printf("(");/*有孩子结点时才输出(*/DispBTNode(b->lchild);/*递归处理左子树*/if (b->rchild!=NULL) printf(",");/*有右孩子结点时才输出,*/DispBTNode(b->rchild);/*递归处理右子树*/printf(")");/*有孩子结点时才输出)*/void DispLeaf(BT

18、Node *b)if (b!=NULL) if (b->lchild=NULL && b->rchild=NULL) printf("%c ",b->data);/*访问叶子结点*/DispLeaf(b->lchild);/*输出左子树中的叶子结点*/DispLeaf(b->rchild);/*输出右子树中的叶子结点*/void DispLeaf1(BTNode *b)if (b!=NULL) if (b->lchild=NULL && b->rchild=NULL) printf("%c

19、",b->data);/*访问叶子结点*/DispLeaf1(b->rchild);/*输出右子树中的叶子结点*/DispLeaf1(b->lchild);/*输出左子树中的叶子结点*/jjj.cpp结果是：3.根据哈夫曼树哈夫输出曼编码：j.cpp文件工程文件.cppa.h文件。运行结果如下：4.线段树的输出。z.cpp文件。工程文件.cppS.h文件。运行结果如下：5.二叉树的先序和中序及高度。W.h文件：运行结果如下：四、实验过程分析：1树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。先根遍历，即先访问根结点，然后按照从左到右的次序先根遍历根结点的每一棵子树。后根遍历 ，即先按照从左到右的次序后根遍历根结点的每一棵子树然后访问根结点。一个结点所在的层次为其双亲结点所在的层次加1。树中结点的最大层次称为树的高度(或树的深度)。2. 用先序建树的时候虽然只要输入一个字符串，但是要判断空树的情况。比较麻烦，我个人觉得用先序与中序联合建树比较简单。因为这样只要输入先序与中序就可以建树了。3. 对于二叉树的三种遍历的过程，要是用递归写的就根据书上所给出的遍历步骤做稍微的调整就好了。至于非递归的三种遍历，中序最为简单，用一个栈就可以完成了，思路是边进栈边收索左孩子，直到左孩子为