?? bitree.cpp
字號:
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<process.h>
#include<string.h>
#include<math.h>
#include<stdio.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define MAXSIZE 50
char f[80]={'\0'};
typedef struct BiTnode{
char *data;
struct BiTnode *lchild,*rchild;
int layer;//給樹加上layer屬性方便輸出的格式控制
}BiTnode,*BiTree;
typedef struct stack{
BiTree data;
struct stack *next;
} stack,* linkstack;
typedef struct stack1{
float data;
struct stack1 *next;
} stack1,* linkstack1;
typedef struct {
BiTree *elem;
int front;
int rear;
int queuesize;
}Queue;
/**************************************************************/
void push(linkstack &S,BiTnode *e)
{ linkstack p;
p=new stack;
p->data=e;
p->next=S;
S=p;
}
/**************************************************************/
void push1(linkstack1 &S,float e)
{ linkstack1 p;
p=new stack1;
p->data=e;
p->next=S;
S=p;
}
/**************************************************************/
bool pop(linkstack &S,BiTnode* &e)
{
linkstack p;
if(S)
{
p=S;
S=S->next;
e=p->data;
delete p;
return TRUE;
}
else return ERROR;
}
/**************************************************************/
bool pop1(linkstack1 &S,float &e)
{
linkstack1 p;
if(S)
{
p=S;
S=S->next;
e=p->data;
delete p;
return TRUE;
}
else return ERROR;
}
/* ******************************************************************** */
bool ISOP(char c)
{
if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#')
return TRUE;
else return ERROR;
}
/* ******************************************************************** */
bool IsNumber(char c)
{
if(c>='0'&&c<='9')
return TRUE;
else return ERROR;
}
/* ******************************************************************** */
char* GetNum(char* &p)
{
char *floatnum=new char [20];
int i=0;
//floatnum[i]=*p;
//i++;
while(IsNumber(*(p+1))||*(p+1)=='.')
{
floatnum[i]=*p;
p++;
i++;
}
floatnum[i]=*p;
floatnum[i+1]='\0';
return floatnum;
}
/* ******************************************************************** */
void ChartoNum(char *a,float &f1)
{// 將a數組中的字符型數變成浮點數f1
f1=0;
int flag=0,count=0;
while(*a!='\0')
{
if(*a=='.') flag=1;
else
{
f1=f1*10+(*a)-'0';
if(flag==1) count++;//count 統計小數位 出現flag==1表明出現小數位
}
a++;
}
f1=f1/(float)pow(10,count);
}
/* ******************************************************************** */
int checktable(char b,char a)//b 是棧頂元素， a是新遇到的運算符，比較a b的優先級
{
char table1[7]={'+','-','*','/','(',')','#'};
int b1=0,a1=0;
while(table1[b1]!=b)b1++;
while(table1[a1]!=a)a1++;
int table[7][7]={ 0,0,1,1,0,0,0,
0,0,1,1,0,0,0,
0,0,0,0,0,0,0,
0,0,0,0,0,0,0,
1,1,1,1,0,2,0,
1,1,1,1,2,0,0,
1,1,1,1,1,1,3}; //優先級s>=p就返回0，優先級s<p就返回1，左右括號相遇時就返回2,#和#相遇就返回3
return (table[b1][a1]);
}
/* ******************************************************************** */
void InitQueue(Queue &Q,int maxsize=MAXSIZE)
{
Q.elem=new BiTree[maxsize];
Q.queuesize=maxsize;
Q.front=Q.rear=0;
}
/* ******************************************************************** */
bool DeQueue(Queue &Q,BiTree &e)
{
if(Q.front==Q.rear) return FALSE;
e=Q.elem[Q.front];
Q.front=(Q.front+1)%Q.queuesize;
return TRUE;
}
/* ******************************************************************** */
bool EnQueue(Queue &Q,BiTree e)
{
if((Q.rear+1)%Q.queuesize==Q.front) return FALSE;
Q.elem[Q.rear]=e;
Q.rear=(Q.rear+1)%Q.queuesize;
return TRUE;
}
/* ******************************************************************** */
bool QueueEmpty(Queue Q)
{
if(Q.front==Q.rear) return TRUE;
else return FALSE;
}
/* ******************************************************************** */
void printspace(int depth)
{ int i=depth;
for(;i>0;i--)
{
cout<<" ";
}
}
/* ******************************************************************** */
void CreatBiT(BiTree &T)
{
BiTnode *tempt[20]={NULL};//tempt中存放樹的節點
BiTree a,b,c;
int i=0,flag;
char *p=f;//p 是指向計算式的指針 ch 接受字符 a&b是操作數 c是運算符。
linkstack S_number=NULL,S_op=NULL;
/*while((ch=getchar())!='#')
{
f[i]=ch;
i++;
}
f[i]='#';//輸入算式*/
tempt[0]=new BiTnode;
tempt[0]->data=new char;//申請空間 并賦值
tempt[0]->data[0]='#';
push(S_op,tempt[0]);
i=1;
while(1)
{
if(IsNumber(*p))
{
tempt[i]=new BiTnode;
tempt[i]->data=GetNum(p);
tempt[i]->lchild=NULL;
tempt[i]->rchild=NULL;
push(S_number,tempt[i]);//若是 操作數入作操數棧
i++;
}
else if(*p=='(')
{ tempt[i]=new BiTnode;
tempt[i]->data=new char;
tempt[i]->data[0]=*p;
push(S_op,tempt[i]);
i++; //左括號直接入棧
}
else if(ISOP(*p))
{
flag=checktable(S_op->data->data[0],*p);//判斷優先級
while(flag==0)
{
pop(S_number,a);
pop(S_number,b);
pop(S_op,c);
T=c;
c->rchild=a;
c->lchild=b;//棧頂優先級高于未入棧的 則建立樹
push(S_number,c);
flag=checktable(S_op->data->data[0],*p);
}
if(flag==1)
{
tempt[i]=new BiTnode;
tempt[i]->data=new char;
tempt[i]->data[0]=*p;
push(S_op,tempt[i]);//棧頂優先級低于未入棧的 則入op棧
i++;
}
if(flag==2)
pop(S_op,a);//括號相遇就消除之
if(flag==3)
return;
}//else if
p++;
}//while
for(i=0;tempt[i]!=NULL;i++)
{
free (tempt[i]);//釋放臨時的輔助節點
}
}
/* ******************************************************************** */
void Operate(BiTree T,linkstack1 &Snum,float &result)
{//實現對二叉樹表達式的求值
float f1,f2,f;
if(T)
{
Operate(T->lchild,Snum,result);
Operate(T->rchild,Snum,result);
if(ISOP(T->data[0]))
{
pop1(Snum,f1);
pop1(Snum,f2);
switch(T->data[0])
{
case '+':
{
result=f1+f2;break;
}
case'-':
{
result=f2-f1;break;
}
case '*':
{
result=f1*f2;break;
}
case '/':
{
result=f2/f1;break;
}
default:
{
cout<<"算式不合法!\n";
return;
}
}
push1(Snum,result);
}//if
else
{
ChartoNum(T->data,f);
push1(Snum,f);
}
}//if
}//operate
/* ******************************************************************** */
float Operate1(BiTree T)
{//實現對二叉樹表達式的求值
float f1,f2,f;
if(!T->lchild&&!T->rchild)
{
ChartoNum(T->data,f);
return f;
}
else{
f1=Operate1(T->lchild);
f2=Operate1(T->rchild);
if(ISOP(T->data[0]))
{
switch(T->data[0])
{
case '+':
{
return f1+f2;
}
case'-':
{
return f1-f2;
}
case '*':
{
return f1*f2;
}
case '/':
{
return f1/f2;
}
default:
{
cout<<"算式不合法!\n";
return FALSE;
}
}
}//if
}//else
}//operate
/* ******************************************************************** */
void Operate2(BiTree T,float &result)
{//實現對二叉樹表達式的求值
float f1,f2;
if(T)
{
Operate2(T->lchild,f2);
Operate2(T->rchild,f1);
if(ISOP(T->data[0]))
{
switch(T->data[0])
{
case '+':
{
result=f1+f2;break;
}
case'-':
{
result=f2-f1;break;
}
case '*':
{
result=f1*f2;break;
}
case '/':
{
result=f2/f1;break;
}
default:
{
cout<<"算式不合法!\n";
return;
}
}
}//if
else
{
ChartoNum(T->data,result);
}
}//if
}//operate2
/* ******************************************************************** */
void CreatBiT2(BiTree &T)
{
char ch;
cin>>ch; //if here is getchar() cannot opetate well why??
if(ch=='#'){T=NULL;return;}
else
{
T=new BiTnode;
T->data=new char;
T->data[0]=ch;
cout<<"輸入"<<T->data[0]<<"左孩子\n";
CreatBiT2(T->lchild);
cout<<"輸入"<<T->data[0]<<"右孩子\n";
CreatBiT2(T->rchild);
}
}
/* ******************************************************************** */
void BiTDepth(BiTree T,int &depth,int h)
{
if(T==NULL) return;
if(h>depth) depth=h;
BiTDepth(T->lchild,depth,h+1);// must be ++h not h++!!
BiTDepth(T->rchild,depth,h+1);
}
/* ******************************************************************** */
void Show(BiTree T)
{
Queue Q;
BiTree e;
int i=0;
int depth=0,h=1,count=0,n=0;
int prelayer=0;
if(T==NULL) return;
InitQueue(Q);
EnQueue(Q,T);
Q.elem[Q.front]->layer=1;//this is the first layer
BiTDepth(T,depth,h);
while(!QueueEmpty(Q))
{
DeQueue(Q,e);
if(e->layer!=prelayer) // if layer changed output space and return
{
cout<<"\n";
printspace(depth--);
}//print return
prelayer=e->layer;
if(e->lchild!=NULL)
{
EnQueue(Q,e->lchild);
e->lchild->layer=e->layer+1;
}
if(e->rchild!=NULL)
{
EnQueue(Q,e->rchild);
e->rchild->layer=e->layer+1;
}
i=0;
while(e->data[i])
{
cout<<e->data[i];
i++;
}
cout<<" ";
}
}
/* ******************************************************************** */
void CopyTree(BiTree T,BiTree &T1)
{
if(T==NULL) {T1=NULL;return;}
T1=new BiTnode;
T1->data=T->data;
CopyTree(T->lchild,T1->lchild);
CopyTree(T->rchild,T1->rchild);
}
/* ******************************************************************** */
void DestoryTree(BiTree T)
{
if(T){
DestoryTree(T->lchild);
DestoryTree(T->rchild);
free(T);
}
}//
/* ******************************************************************** */
void Calcute(BiTree T,float &result)
{
float f1,f2;
if(T)
{
Calcute(T->lchild,f1);
// if(T->lchild!=NULL)ChartoNum(T->lchild->data,f1);
Calcute(T->rchild,f2);
// if(T->lchild!=NULL)ChartoNum(T->rchild->data,f2);
if(T->lchild==NULL)
{
ChartoNum(T->data,result);
ChartoNum(T->data,result);
}
else{
switch(T->data[0])
{
case '+':{ result=f1+f2;break;}
case '-':{result=f1-f2;break;}
case '*':{result=f1*f2;break;}
case '/':{result=f1/f2;break;}
}
}
}
}
/* ******************************************************************** */
void main()
{ int depth=0;
int h=1,k;
BiTree T=NULL,T1=NULL,TNUM=NULL;//T is tree T1 is its copy TNUM is tree for computing machine;
float result;
linkstack1 Snum=NULL;
while(1)
{
cout<<"-------------二叉樹計算器-------------\n"
<<"1 創建二叉樹\n"
<<"2 復制二叉樹\n"
<<"3 銷毀二叉樹\n"
<<"4 求樹的深度\n"
<<"5 樹形顯示二叉樹\n"
<<"6 二叉樹實現的數值計算器，支持浮點數\n"
<<"0 退出\n";
cin>>k;
switch(k)
{
case 1:
{
cout<<"創建二叉樹請輸入根節點：\n";
CreatBiT2(T);
cout<<"創建二叉樹成功\n";
break;
}
case 2:
{
CopyTree(T,T1);
cout<<"復制二叉樹成功\n";
Show(T);Show(T1);
break;
}
case 3:
{
DestoryTree(T);
DestoryTree(T1);
DestoryTree(TNUM);
cout<<"銷毀二叉樹成功\n";
break;
}
case 4:
{
BiTDepth(T,depth,h);
cout<<"樹的深度是"<<depth<<"\n";
break;
}
case 5:
{
cout<<"樹形顯示二叉樹如下:\n";
Show(T);
cout<<"\n";
break;
}
case 6:
{
int i=0;
cout<<"請輸入算式，以'#'字符結束輸入：\n";
cin>>f[i];
while(f[i]!='#')
{
i++;
cin>>f[i];
}
//輸入算式
CreatBiT(TNUM);
Operate2(TNUM,result);
//result=Operate1(TNUM);
cout<<result;
//Calcute(TNUM,result);
//Operate(TNUM,Snum,result);
cout<<"\n";
cout<<"運算結果:"<<result<<"\n";
cout<<"樹形顯示如下:\n";
Show(TNUM);
cout<<"\n";
break;
}
case 0:
{
return;
}
}//switch
}//while
}//main
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -