/*課程設計題十五：.二叉樹用二叉鏈表表示 

一、 設計目的 
1．掌握二叉樹的概念和性質 
2. 掌握任意二叉樹存儲結構。 
3．掌握任意二叉樹的基本操作。 
二、設計內容和要求  
1． 實現二叉樹的建立、前序（非遞歸）、中序和層次遍歷； 
2． 求二叉樹高度、結點數、度為1的結點數和葉子結點數； 
3． 插入結點到指定位置、刪除指定結點； 
4． 將二叉樹所有結點的左右子樹交換。 



源代碼 */


  
#include<iostream.h>  
#include<stdio.h>  
#include<malloc.h> 
#define MAXNODE 100  
//樹的建立  
typedef struct bitnode  
{ char data;  
 struct bitnode *lchild,*rchild;  
}bitnode,*bintree;  
//二叉樹的二叉鏈表的存儲算法  
void createbintree(bintree *t)  
{ char ch;  
 cin>>ch;  
 if(ch=='0')  
 (*t)=NULL;  
 else  
 { (*t)=new bitnode;  
 (*t)->data=ch;  
 createbintree(&(*t)->lchild);  
 createbintree(&(*t)->rchild);  
 }  
} 

//9.中序遍歷  
void inorderout(bintree bt)  
{  
 if(bt!= NULL){  
 inorderout(bt->lchild);  
 printf("%c ", bt->data);  
 inorderout(bt->rchild);  
}  
 return;  
}  
/* 11.按層遍歷 */  
void translevel(bintree b) 
{ struct node 
{ 
bitnode *vec[MAXNODE]; 
int f,r; 
} q; 
q.f=0; 
q.r=0; 
if(b!=NULL)printf("%c ",b->data); 
q.vec[q.r]=b; 
q.r=q.r+1; 
while(q.f<q.r) 
{ 
b=q.vec[q.f]; 
q.f=q.f+1; 
if(b->lchild!=NULL) 
{ 
printf("%c ",b->lchild->data); 
q.vec[q.r]=b->lchild; 
q.r=q.r+1; 
} 
if(b->rchild!=NULL) 
{ 
printf("%c ",b->rchild->data); 
q.vec[q.r]=b->rchild; 
q.r=q.r+1;} 
} 
} 
 /* 6.輸出二叉樹(前序遍歷) */  
void preorder(bitnode *b) 
{ 
bitnode *stack[MAXNODE],*p; 
int top; 
if(b!=NULL) 
{ 
top=1; 
stack[top]=b; 
while(top>0) 
{ 
p=stack[top]; 
top--; 
printf("%c ",p->data); 
if(p->rchild!=NULL) 
{ 
top++; 
stack[top]=p->rchild; 
} 
if(p->lchild!=NULL) 
{ 
top++; 
stack[top]=p->lchild; 
} 
} 
} 

} 

/*求樹的高度 */  
int depth(bitnode *b)  
{  
 int dep1,dep2;  
 if(b==NULL) return(0);  
 else  
 {  
 dep1=depth(b->lchild);  
 dep2=depth(b->rchild);  
 if(dep1>dep2)return(dep1+1);  
 else return(dep2+1);  
 }  
}  
/*所有葉子結點數 */  
int countleaf(bintree bt)  
{ if(bt==NULL)  
 return 0;  
 if(bt->lchild==NULL&&bt->rchild==NULL)  
 return 1;  
 return (countleaf(bt->lchild)+countleaf(bt->rchild));  
  
}  
/*所有結點數 */  
int btreecount(bintree bt)  
{ if(bt==NULL)  
 return 0;  
 else return btreecount(bt->lchild)+btreecount(bt->rchild)+1;  
}  
/*求度為“1”的結點總數*/ 
int onechild(bitnode * b)/*求度為“1”的結點總數*/ 
{ 
int num1,num2; 
if(b==NULL)return(0); 
else if(b->lchild==NULL&&b->rchild!=NULL) 
return(1+onechild(b->rchild)); 
if(b->lchild!=NULL&&b->rchild==NULL) 
return(1+onechild(b->lchild)); 
else 
{ 
num1=onechild(b->lchild); 
num2=onechild(b->rchild); 
return(num1+num2); 
} 
} 
/*將結點的左右子樹交換*/ 
bitnode *swap(bitnode *b)  
{  
 bitnode *t,*t1,*t2;  
 if(b==NULL) t=NULL;  
 else  
 {  
 t=(bitnode *)malloc(sizeof(bitnode));  
 t->data=b->data;  
 t1=swap(b->lchild);  
 t2=swap(b->rchild);  
 t->lchild=t2;  
 t->rchild=t1;  
}  
 return(t);  
  
}  
/*插入左子樹*/ 
 
 
 
bitnode *insertl(bitnode *b,char x,char e)  
{  
 bitnode *stack[MAXNODE],*p,*s,*t;  
 s=(bitnode*)malloc(sizeof(bitnode));  
 s->data=e;  
 s->lchild=NULL;  
 s->rchild=NULL;  
 int top;  
 if(b!=NULL)  
 {  
 top=1;  
 stack[top]=b;  
 while(top>0)  
 {  
 p=stack[top];  
 top--;  
 printf("%c ",p->data);  
 if(p->data==x)t=p;  
 if(p->rchild!=NULL)  
 {  
 top++;  
 stack[top]=p->rchild;  
 }  
 if(p->lchild!=NULL)  
 {  
 top++;  
 stack[top]=p->lchild;  
 }  
 }  

 }  
 s->lchild=t->lchild;  
 s->rchild=t->rchild;  
 t->lchild=s;  
 printf("\n");  
 return(b);  
}  
void print(bitnode *b)  
{  
 if(b!=NULL)  
 {  
 printf("%c",b->data);  
 if(b->lchild!=NULL||b->rchild!=NULL)  
 {  
 printf("(");  
 print(b->lchild);  
 if(b->rchild!=NULL)printf(", ");  
 print(b->rchild);  
 printf(")");  
 }  
 }  
}  
/*插入右子樹*/ 

bitnode *insertr(bitnode *b,char x,char e)  
{  
 bitnode *stack[MAXNODE],*p,*s,*t;  
 s=(bitnode*)malloc(sizeof(bitnode));  
 s->data=e;  
 s->lchild=NULL;  
 s->rchild=NULL;  
 int top;  
 if(b!=NULL)  
 {  
 top=1;  
 stack[top]=b;  
 while(top>0)  
{  
 p=stack[top];  
 top--;  
 printf("%c ",p->data);  
 if(p->data==x)t=p;  
 if(p->rchild!=NULL)  
 {  
 top++;  
 stack[top]=p->rchild;  
 }  
 if(p->lchild!=NULL)  
 {  
 top++;  
 stack[top]=p->lchild;  
 }  
}  

}  
 s->lchild=t->lchild;  
 s->rchild=t->rchild;  
 t->rchild=s;  
 printf("\n");  
 return(b);  
}  
/*刪除左子樹*/ 
bitnode *deletl(bitnode *b,char x)  
{  
 bitnode *stack[MAXNODE],*p,*t;  
 int top;  
 if(b!=NULL)  
 {  
 top=1;  
 stack[top]=b;  
 while(top>0)  
 {  
 p=stack[top];  
 top--;  
 printf("%c ",p->data);  
 if(p->data==x)t=p;  
 if(p->rchild!=NULL)  
 {  
 top++;  
 stack[top]=p->rchild;  
 }  
 if(p->lchild!=NULL)  
 {  
 top++;  
 stack[top]=p->lchild;  
 }  
 }  

 }  
 t->lchild=NULL;  
 printf("\n");  
 return(b);  
}  
/*刪除右子樹*/ 
bitnode *deletr(bitnode *b,char x)  
{  
 bitnode *stack[MAXNODE],*p,*t;  
 int top;  
 if(b!=NULL)  
 {  
 top=1;  
 stack[top]=b;  
 while(top>0)  
 {  
 p=stack[top];  
 top--;  
 printf("%c ",p->data);  
 if(p->data==x)t=p;  
 if(p->rchild!=NULL)  
 {  
 top++;  
 stack[top]=p->rchild;  
 }  
 if(p->lchild!=NULL)  
 {  
 top++;  
 stack[top]=p->lchild;  
 }  
 }  

 }  
 t->rchild=NULL;  
 printf("\n");  
 return(b);  
}  
void main()  
{  
 int a; 
 bintree bt;  
 printf("\n\n\n***************二叉樹的二叉鏈表表示***************"); 
 cout<<endl<<endl<<endl; 
 printf("\n請按先序輸入二叉樹：\n"); 
 createbintree(&bt); 
 printf("請選擇你要進行的操作：\n"); 
 printf("1.輸出樹的高度、葉子結點數、所有結點數、度為1的結點數；\n"); 
 printf("2.非遞歸前序遍歷、中序遍歷和層次遍歷；\n"); 
 printf("3.交換左右子樹；\n"); 
 printf("4.插入結點的左孩子；\n"); 
 printf("5.插入結點的右孩子；\n"); 
 printf("6.刪除結點的左孩子；\n"); 
 printf("7.刪除結點的右孩子；\n"); 
 printf("0.退出程序；\n"); 
 cin>>a; 
 for(;a!=0;) 
 { 
 if(a==1) 
 { 
 printf("樹的高度為：%d",depth(bt));  
 printf("\n");  
 printf("葉子結點數為：%d",countleaf(bt));  
 printf("\n");  
 printf("所有結點數為：%d",btreecount(bt));  
 printf("\n"); 
printf("度為1的結點數為：%d",onechild(bt)); 
 printf("\n"); 
 cout<<endl<<endl<<endl<<endl; 
 } 
 if(a==2) 
 { 
 printf("前序遍歷為：");  
 preorder(bt);  
 printf("\n");  
 printf("中序遍歷為：");  
 inorderout(bt);  
 printf("\n");  
 printf("層次遍歷為：");  
 translevel(bt); 
printf("\n"); 
cout<<endl<<endl<<endl<<endl; 
 } 
 if(a==3) 
 { 
 printf("交換后的樹中序輸出為："); 
 inorderout(swap(bt));  
 cout<<endl<<endl<<endl<<endl; 
  
 } 
 if(a==4) 
 { 
 printf("請輸入要插入結點的雙親及要插入的元素(如bc)-----"); 
 char x,e;  
 cin>>x>>e;  
 print(insertl(bt, x, e));  
 cout<<endl<<endl<<endl<<endl; 
  
 } 
 if(a==5) 
 { 
 printf("請輸入要插入結點的雙親及要插入的元素(如bc)-----"); 
 char x,e;  
 cin>>x>>e;  
 print(insertr(bt, x, e)); 
 cout<<endl<<endl<<endl<<endl; 
  
 } 
 if(a==6) 
 { 
 printf("請輸入要刪除的雙親結點-----");  
 char y;  
 cin>>y;  
 print(deletl(bt, y));  
 cout<<endl<<endl<<endl<<endl; 
  
 } 
 if(a==7) 
 { 
 printf("請輸入要刪除的雙親結點-----");  
 char y;  
 cin>>y;  
 print(deletr(bt, y));  
 cout<<endl<<endl<<endl<<endl; 
  
 } 

 printf("請選擇你要進行的操作：\n"); 
 printf("1.輸出樹的高度、葉子結點數、所有結點數、度為1的結點數；\n"); 
 printf("2.非遞歸前序遍歷、中序遍歷和層次遍歷；\n"); 
 printf("3.交換左右子樹；\n"); 
 printf("4.插入結點的左孩子；\n"); 
 printf("5.插入結點的右孩子；\n"); 
 printf("6.刪除結點的左孩子；\n"); 
 printf("7.刪除結點的右孩子；\n"); 
 printf("0.退出程序；\n\n\n"); 


 cin>>a; 
 }  
}