shixian.cpp

严版数据结构。二叉树。功能齐全。经过调试。没有b+b_ 树。（c语言）。

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#include "btree.h"

void InitBiTree(BiTree &T)//初始化二叉树，即把树根指针置空
{T=NULL;
}

void CreateBiTree(BiTree &T,char *a)
//根据a所指向的二叉树广义表字符串建立对应的存储结构
{ BiTree p;
  BiTree s[MAXSIZE1];//定义s数组作为存储根结点指针的栈使用
  int top=-1;//top作为s栈的栈顶指针，初值为-1，表示空栈
  int k;//用k作为处理结点的左子树和右子树的标记，k=1处理左子树，k=2处理右子树
  int i=0;
  T=NULL;
  while(a[i])
  {switch(a[i]){
     case ' ':break;//对空格不做任何处理
	 case '(':if(top==MAXSIZE1-1) 
			  {printf("栈空间太小!\n");
		       exit(1);
			  }
		      top++;
			  s[top]=p;k=1;
			  break;
	  case ')':if(top==-1)
			   {printf("二叉树广义表字符串错!|n");
		        exit(1);
			   }
		       top--;
			   break;
	  case ',':k=2;break;
	  default:p=(BitNode *)malloc(sizeof(BitNode));
		      p->data=a[i];
			  p->lchild=p->rchild=NULL;
			  if(T==NULL) T=p;
			  else
			  {if(k==1) s[top]->lchild=p;
			   else s[top]->rchild=p;
			  }
  }
  i++;
  }
}

int BiTreeEmpty(BiTree &T)//检查二叉树是否为空
{ if(!T) return OK;
  else return ERROR;
}

int PreOrder(BiTree T)//先序输出二叉树
{ if(T!=NULL)
  {
   printf("%c",T->data);
   PreOrder(T->lchild);
   PreOrder(T->rchild);
  }
  return OK;
}

int InOrder(BiTree T)//中序输出二叉树
{ if(T!=NULL)
  {
   InOrder(T->lchild);
   printf("%c",T->data);
   InOrder(T->rchild);
  }
  return OK;
}

int PostOrder(BiTree T)//后序输出二叉树
{ if(T!=NULL)
  {  PostOrder(T->lchild);
   PostOrder(T->rchild);
   printf("%c",T->data);
  }
  return OK;
}

void TrarverseBiTree(BiTree T)//选择一种遍历次序输出二叉树中的所有结点
{ int done,i;
if(!T) printf("二叉树为空!!\n");
else{
  printf("    ***********************\n");
  printf("     1.按先序\n");
  printf("     2.按中序\n");
  printf("     3.按后序\n");
  printf("     0.退出\n");
  printf("     **********************\n");
  while(done)
  {printf("      请输入序号(0-3):");
   scanf("%d",&i);
   switch(i)
   { case 1:printf("      先序为:");PreOrder(T);break;
     case 2:printf("      中序为:");InOrder(T);break;
     case 3:printf("      后序为:");PostOrder(T);break;
     case 0:done=0;break;
    default: printf("     ERROR\n");
   }
   printf("\n");
  }
}
}
    
int BiTreeDepth(BiTree T)//求二叉树的深度
{int depth;
int depthleft,depthright;
 if(!T) depth=0;
 else
 { depthleft=BiTreeDepth(T->lchild);
   depthright=BiTreeDepth(T->rchild);
   depth=1+(depthleft>depthright?depthleft:depthright);
 }
 return depth;
}

int BiTreeCount(BiTree T)//求二叉树中所有结点数
{ int total=0;
  if(!T) total=0;
  else
  { total++;
    BiTreeCount(T->lchild);
    BiTreeCount(T->rchild);
  }
  return total;
}

void PrintBiTree(BiTree T)//输出二叉树的广义表表示
{if(T!=NULL)
{printf("%c",T->data);//输出根结点的值
 if(T->lchild!=NULL||T->rchild!=NULL)
 {printf("(");
  PrintBiTree(T->lchild);
  if(T->rchild!=NULL) printf(",");//若右子树不为空则输出逗号分隔符
  PrintBiTree(T->rchild);
  printf(")");
 }
}
}



void MenuSelect(BiTree T)//二叉树菜单选择
{   int done1,m;
    char a[50];
	printf("**********二叉树***********\n");
    printf(" 1.按先序次序建立二叉树\n");
    printf(" 2.检查二叉树是否为空\n");
    printf(" 3.遍历输出二叉树\n");
	printf(" 4.输出二叉树的广义表表示\n");
    printf(" 5.求二叉树的深度\n");
    printf(" 6.求二叉树中所有结点数\n");
	printf(" 0.退出\n");
	printf("****************************\n");
    while (done1)
	{printf("请输入要进行的操作:");
     scanf("%d",&m);
     switch(m)
	 {
	  case 1:printf("输入二叉树广义表字符串:\n");
		     scanf("%s",a);
		     CreateBiTree(T,a);
			 break;
	  case 2:if(BiTreeEmpty(T)) printf("二叉树为空!\n");
		     else printf("二叉树不为空!\n");
			 break;
	  case 3:TrarverseBiTree(T);
		     break;
	  case 4:PrintBiTree(T);break;
	  case 5:printf("深度为:%d\n",BiTreeDepth(T));
		     break;
	  case 6:printf("所有结点数:%d\n",BiTreeCount(T));
		     break;
      case 0:done1=0;break;
      default: printf("ERROR\n");
   }
   printf("\n");
  }
}

int Search(char ino[],char c)//在中序序列中查询
{int i=0,j=0;
 while(ino[i]!='\0')
	{ i++;}
 while(ino[j]!='\0')
 {if(c==ino[j]) break;
	 else j++;
 }
 if(i==j) return -1;
 else return j;
}

BiTree CrtBt(char pre[],char ino[],int ps,int is,int n)
//由两个序列构造二叉链表
{int k;BiTree T,lroot,rroot;
 if(n==0) T=NULL;
 else
 {k=Search(ino,pre[ps]);
  if(k==-1) T=NULL;
  else
  {T=(BitNode *)malloc(sizeof(BitNode));
   T->data=pre[ps];
  }
  if(k==is) T->lchild=NULL;
  else
  {lroot=CrtBt(pre,ino,ps+1,is,k-is);
         T->lchild =lroot;
  }
  if(k==is+n-1) T->rchild=NULL;
  else 
  {rroot=CrtBt(pre,ino,ps+1+(k-is),k+1,n-(k-is)-1);
    T->rchild=rroot;
  }
 }
  return T;
}

void menuCrtBt()
{BiTree T;
 char pre[20],ino[20];
 int ps=0,is=0;int n;
 printf("请输入先序序列:");
 scanf("%s",pre);
 printf("请输入中序序列:");
 scanf("%s",ino);
 printf("字符串长度为:");
 n=strlen(pre);
 printf("%d\n",n);
T=CrtBt(pre,ino,ps,is,n);
	 
 printf("建树成功!!!\n");
 printf("   其后序序列为:");
 PostOrder(T);
 printf("\n");
 printf("   二叉树的广义表表示:");
 PrintBiTree(T);
}

BiTree Createhuffman(int a[],int n)//建立哈夫曼树
{int i,j,t;
 BiTree q,*b;
 b=(BiTree *)malloc(n*sizeof(BiTree));//动态分配由b指向的指针数组
 for(i=0;i<n;i++)
 {b[i]=(BitNode *)malloc(sizeof(BitNode));
  b[i]->data=a[i];
  b[i]->lchild=b[i]->rchild=NULL;
 }
 for(i=1;i<n;i++)//进行n-1次循环建立哈夫曼树
 {int k1=-1,k2;//k1初始指向森林中第一棵树，k2指向森林中第二棵树
  for(j=0;j<n;j++)
  {if(b[j]!=NULL&&k1==-1) {k1=j;continue;}
   if(b[j]!=NULL) {k2=j;break;}
  }
   for(j=k2;j<n;j++)
   { if(b[j]!=NULL)
	 {if(b[j]->data<b[k1]->data) {k2=k1;k1=j;}
	  else if(b[j]->data<b[k2]->data) k2=j;
	 }
   } 
   if(k1>k2&&b[k1]->lchild==NULL&&b[k2]->lchild==NULL){t=k1;k1=k2;k2=t;}
   if(k1<k2&&b[k1]->lchild!=NULL&&b[k2]->lchild==NULL){t=k1;k1=k2;k2=t;}
   q=(BitNode *)malloc(sizeof(BitNode));//建立一棵新树,q指向树根结点
   q->data=b[k1]->data+b[k2]->data;
   q->lchild=b[k1];
   q->rchild=b[k2];
   b[k2]=q;b[k1]=NULL;
  }
  free(b);
  return q;
}

void Huffmancoding(BiTree T,int len)//对各字符进行哈夫曼编码
{ static int c[10];
  if(T!=NULL){
   if(T->lchild==NULL&&T->rchild==NULL)
   { int i;
     printf("      结点权值为%d的编码:",T->data);
	 for(i=0;i<len;i++)
		 printf(" %d ",c[i]);
	  printf("\n");
   }
   else
   {c[len]=0;Huffmancoding(T->lchild,len+1);
    c[len]=1;Huffmancoding(T->rchild,len+1);
   }
  }
}
  
int PreOrderha(BiTree T)//先序输出哈夫曼树
{ if(T!=NULL)
  {
   printf(" %d",T->data);
   PreOrderha(T->lchild);
   PreOrderha(T->rchild);
  }
  return OK;
}

int InOrderha(BiTree T)//中序输出哈夫曼树
{ if(T!=NULL)
  {
   InOrderha(T->lchild);
   printf(" %d",T->data);
   InOrderha(T->rchild);
  }
  return OK;
}

int PostOrderha(BiTree T)//后序输出哈夫曼树
{ if(T!=NULL)
  {  PostOrderha(T->lchild);
   PostOrderha(T->rchild);
   printf(" %d",T->data);
  }
  return OK;
}

void PrintBiTreeha(BiTree T)//输出哈夫曼树的广义表表示
{if(T!=NULL)
{printf("%d",T->data);//输出根结点的值
 if(T->lchild!=NULL||T->rchild!=NULL)
 {printf("(");
  PrintBiTreeha(T->lchild);
  if(T->rchild!=NULL) printf(",");//若右子树不为空则输出逗号分隔符
  PrintBiTreeha(T->rchild);
  printf(")");
 }
}
}


void huffmenu()
{int done2,h;
 int n,i,s;int *a;
 char c;
 int p[13]={186,64,13,22,32,103,21,15,47,57,1,5,32};
 int q[13]={57,63,15,1,48,51,80,23,8,18,1,16,1};
 BiTree T;
 printf("*****************************\n");
 printf("1.建立哈夫曼树\n");
 printf("2.对各字符进行哈夫曼编码\n");
 printf("3.对给定的字符串译码\n");
 printf("4.对哈夫曼树进行先序遍历\n");
 printf("5.对哈夫曼树进行中序遍历\n");
 printf("6.对哈夫曼树进行后序遍历\n");
 printf("7.打印哈夫曼树\n");
 printf("0.退出\n");
 printf("******************************\n");
 
 while (done2)
 {printf("请输入对哈夫曼树进行的操作序号:");
     scanf("%d",&h);
     switch(h)
	 {case 1:printf("---------------------------------------------\n");
                 printf("字符:");
                 for(c='a';c!='n';c++)
	               printf("%3c ",c);
                 printf("\n频度:");
                 for(s=0;s<13;s++)
	               printf("%4d",p[s]);
                 printf("\n字符:");
                 for(c='n';c!='{';c++)
	               printf("%3c ",c);
                 printf("\n频度:");
                 for(s=0;s<13;s++)
	               printf("%4d",q[s]);
                 printf("\n");
	         printf("  输入带权叶子结点数:");
             while(1)
			 {scanf("%d",&n);
              if(n>1) break;
              else printf("重输n值:");
			 }
             a=(int *)malloc(n*sizeof(int));
             printf("  输入%d个整数作为权值:",n);
             for(i=0;i<n;i++)
	         scanf("%d",&a[i]);
             T=Createhuffman(a,n);
             printf("      哈夫曼树已成功建立!!\n");break;
	  case 2: printf("  树中每个叶子的哈夫曼编码:\n");
		      Huffmancoding(T,0);break;
	  case 4:printf("      先序为:");PreOrderha(T);break;
      case 5:printf("      中序为:");InOrderha(T);break;
      case 6:printf("      后序为:");PostOrderha(T);break;
	  case 7:printf("  广义表形式的哈夫曼树:");
		               PrintBiTreeha(T);break;
      case 0:done2=0;break;
      default: printf("ERROR\n");
	 }
      printf("\n");
 }
}