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

一、实验目的： 1.学会实现二叉树结点结构和对二叉树的基本操作。 2.掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 3．掌握树的创建即对它的遍历，输出树，以及叶子结点，根结点。 4．哈夫曼树的建立与编码的输出。 二、实验环境： 装有Visual C++6.0的windons.7系统的计算机一台 实验内容与步骤： 1..二叉树的创建及输出。 m.h文件： #includestdafx.h #include stdio.h #include malloc.h #define MaxSize 100 typedef char 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(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 #include m.h BTNode *CreateBT1(char *pre,char *in,int n) /*pre存放先序序列,in存放中序序列,n为二叉树结点个数, 本算法执行后返回构造的二叉链的根结点指针*/ { BTNode *s; char *p; int k; if (n=0) return NULL; s=(BTNode *)malloc(sizeof(BTNode)); /*创建二叉树结点*s*/ s-data=*pre; for (p=in;pin+n;p++) /*在中序序列中找等于*ppos的位置k*/ if (*p==*pre) /*pre指向根结点*/ break; /*在in中找到后退出循环*/ k=p-in; /*确定根结点在in中的位置*/ s-lchild=CreateBT1(pre+1,in,k); /*递归构造左子树*/ s-rchild=CreateBT1(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;pin+n;p++) /*在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 *St[MaxSize],*p=NULL; int top=-1,k,j=0; char ch; b=NULL; /*建立的二叉树初始时为空*/ ch=str[j]; while (ch!=\0) /*str未扫描完时循环*/ { switch(ch) { case (:top++;St[top]=p;k=1; break; /*为左孩子结点*/ case ):top