?? shixian.cpp
字號:
#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");
}
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -