数据结构实验2——二叉树的基本操作及哈夫曼编码译码系统的实现

二叉树的遍历及计算

#include <stdio.h>
#include <stdlib.h>
typedef int T;

typedef struct BTNode{
	T Data;
	struct BTNode *LChild,*RChild;
}BTNode;

typedef struct BTTree
{
	BTNode *root;
}BTTree;

/*先序建树*/
BTNode* PreCreateBt(BTNode *t){
	char ch;
	ch = getchar();
	if( ch == '#' ) t = NULL; 
	else{
		t = (BTNode *)malloc(sizeof(BTNode));
		t->Data = ch;
		t->LChild = PreCreateBt(t->LChild);
		t->RChild = PreCreateBt(t->RChild);
	}
	return t;
}

void PrebuildTree(BTTree *tree){
	tree->root = PreCreateBt(tree->root);
}
/*先序遍历*/
void PreOrderTransverse(BTNode *t){
	if(t == NULL) return ;
	printf("%c", t->Data);
	PreOrderTransverse(t->LChild);
	PreOrderTransverse(t->RChild);
}
void TreePreOrder(BTTree *tree){
	if(tree) PreOrderTransverse(tree->root);
}

/*中序遍历*/
void InOrderTransverse(BTNode *t){
	if(t == NULL) return ;
	
	InOrderTransverse(t->LChild);
	printf("%c", t->Data);
	InOrderTransverse(t->RChild);
}
void TreeInOrder(BTTree *tree){
	if(tree) InOrderTransverse(tree->root);
}

/*后序遍历*/
void AfterOrderTransverse(BTNode *t){
	if(t == NULL) return ;
	
	AfterOrderTransverse(t->LChild);
	AfterOrderTransverse(t->RChild);
	printf("%c", t->Data);
}
void TreeAfterOrder(BTTree *tree){
	if(tree) AfterOrderTransverse(tree->root);
}

/*结点数目*/
int countNode(BTNode *t){
	if( t != NULL) return countNode(t->LChild)+countNode(t->RChild)+1;
	else return 0; //如果t为空,则该t的父亲结点是子结点,该t结点不需要计数
}
int Nodenum(BTTree *tree){
	if(tree) return countNode(tree->root);
	else return -1;
}

/*叶子结点数目*/
int countLeafNode(BTNode *t){
	if( t != NULL){
		if( t->LChild == NULL && t->RChild == NULL) return 1;
		else return countLeafNode(t->LChild)+countLeafNode(t->RChild);
	}
	else return 0; //如果t为空,则该t的父亲结点是子结点,该t结点不需要计数
}
int leafNodenum(BTTree *tree){
	if(tree) return countLeafNode(tree->root);
	else return -1;
}

/*计算树的高度*/
int coutTreeHeight(BTNode *t){
	if(t == NULL) return 0;
	else {
		int l = coutTreeHeight(t->LChild);
		int r = coutTreeHeight(t->RChild);
		if ( l > r) return l+1;
		else return r+1;
		// return max(r,l)+1;
	}
}
int TreeHeight(BTTree *tree){
	if(tree) return coutTreeHeight(tree->root);
		else return -1;
}

/*翻转整个二叉树(左右子树交换)*/
BTNode* ReverseLeftRightChild(BTNode *t){	//先序遍历
 if(t!=NULL){
	if( t->LChild!=NULL || t->RChild!=NULL){
		   BTNode *p,*q;
		p = ReverseLeftRightChild(t->LChild);
		q = ReverseLeftRightChild(t->RChild);
		t->LChild = q;
		t->RChild = p;
		}
}
return t;
}

void ReverseBtree(BTTree *tree){
	if(tree) ReverseLeftRightChild(tree->root);
}

int main(int argc, char const *argv[]){
	BTTree tree;
	printf("先序建树:");
	PrebuildTree(&tree);

	printf("\n先序遍历:");
	TreePreOrder(&tree);

	printf("\n中序遍历:");
	TreeInOrder(&tree);

	printf("\n后序遍历:");
	TreeAfterOrder(&tree);

	printf("\n结点数目:%d\n",Nodenum(&tree));
	printf("\n叶子结点数目:%d\n",leafNodenum(&tree));

	printf("\n树的高度:%d\n",TreeHeight(&tree));

	printf("翻转二叉树:\n");
	ReverseBtree(&tree);
	printf("\n后序遍历:");
	TreeAfterOrder(&tree);	

	printf("\n");
	return 0;
}

哈夫曼树

#include<stdio.h>
#define n 5           //叶子数目
#define m (2*n-1)     //结点总数
#define maxval 10000.0
#define maxsize 100   //哈夫曼编码的最大位数

typedef struct{
 char ch;
 float weight;
 int lchild,rchild,parent;
}hufmtree;

typedef struct{
 char bits[n];   //位串
 int start;      //编码在位串中的起始位置
 char ch;        //字符
}codetype;


//建立哈夫曼树
void huffman(hufmtree tree[]){
   int i,j,p1,p2;//p1,p2分别记住每次合并时 权值最小 和 次小 的两个根结点的下标
   float small1,small2,f;
   char c;
   for(i=0;i<m;i++){    //初始化
    tree[i].parent=0;
    tree[i].lchild=-1;
    tree[i].rchild=-1;
    tree[i].weight=0.0;
    }
   for(i=0;i<n;i++){        //读入前n个叶子结点的字符及权值
      printf("输入第%d个字符为和权值:",i+1);
      scanf("%c %f",&c,&f);
      getchar();
      tree[i].ch=c;
      tree[i].weight=f;
    }
   for(i=n;i<m;i++){               //进行n-1次合并，产生n-1个新结点
    p1=0;p2=0;
    small1=maxval;small2=maxval;   //maxval是float类型的最大值
    for(j=0;j<i;j++)               //选出两个权值最小的根结点
     if(tree[j].parent==0)
      if(tree[j].weight<small1){
       small2=small1;               //改变最小权、次小权及对应的位置
       small1=tree[j].weight;
       p2=p1;
       p1=j;
      }else
        if(tree[j].weight<small2){
          small2=tree[j].weight;  //改变次小权及位置
          p2=j;
        }
    tree[p1].parent=i;
    tree[p2].parent=i;
    tree[i].lchild=p1;  //最小权根结点是新结点的左孩子
    tree[i].rchild=p2;  //次小权根结点是新结点的右孩子
    tree[i].weight=tree[p1].weight+tree[p2].weight;
   }
}//huffman


//根据哈夫曼树求出哈夫曼编码
//codetype code[]为求出的哈夫曼编码
//hufmtree tree[]为已知的哈夫曼树
void huffmancode(codetype code[],hufmtree tree[]){
   int i,c,p;               
   codetype cd;               //缓冲变量
   for(i=0;i<n;i++){
      cd.start=n;
      cd.ch=tree[i].ch;
      c=i;                      //从叶结点出发向上回溯
      p=tree[i].parent;         //tree[p]是tree[i]的双亲
      while(p!=0){
         cd.start--;
         if(tree[p].lchild==c) cd.bits[cd.start]='0';   
         //tree[i]是左子树，生成代码'0'
         else cd.bits[cd.start]='1';   
         //tree[i]是右子树，生成代码'1'
         c=p;
         p=tree[p].parent;
      }
      code[i]=cd;    //第i+1个字符的编码存入code[i]
   }
}//huffmancode

//哈夫曼树译码
void decode(hufmtree tree[]){
   int i,j;
   char b[maxsize];
   i=m-1;             //从根结点开始往下搜索
   printf("输入发送的编码(以'#'为结束标志)：");
   gets(b);
   printf("译码后的字符为");
   for(j=0;b[j]!='#';j++){
      if(b[j]=='0') i=tree[i].lchild;         //走向左孩子
      else i=tree[i].rchild;                  //走向右孩子
      if(tree[i].lchild==-1) {                //tree[i]是叶结点
       printf("%c",tree[i].ch);
       i=m-1;                                 //回到根结点
      }
   }
   if(tree[i].lchild!=-1 && b[j]!= '#')   //电文读完，但尚未到叶子结点
     printf("\nERROR\n");               //输入电文有错
}

void input(hufmtree tree[],codetype code[]){
  int i,j;//循环变量
  printf("【哈夫曼编码】\n");
  printf("总共有%d个字符\n",n);
  huffman(tree);//建立哈夫曼树
  huffmancode(code,tree);//根据哈夫曼树求出哈夫曼编码
  printf("【输出每个字符的哈夫曼编码】\n");
  for(i=0;i<n;i++){
  printf("%c: ",code[i].ch);
  for(j=code[i].start;j<n;j++)
  printf("%c",code[i].bits[j]);
  printf("\n");
 }
}

int main(){
 hufmtree tree[m];
 codetype code[n];
 input(tree,code);

 printf("【哈夫曼译码】\n");
 decode(tree);//依次读入电文，根据哈夫曼树译码
 return 0;
}