說明：為了保證輸入的數據按要求構造出想要的、唯壹確定的二叉樹的形狀，這裏輸入要求利用廣義表的形式，雖然會顯得繁瑣壹點，但足以保證嚴謹性。否則只是單純壹串數字，樹形就能千變萬化，不壹定的。
#include <stdio.h>
#include <malloc.h>
#define MaxSize 10
#define Number 30
struct BiTNode{//定義數據結構
char data;
BiTNode *lchild,*rchild;
};
void InitBtree(BiTNode * &BT){//初始化二叉樹
BT=NULL;
}
void CreateBiTree(BiTNode *&BT,char *str){//建立二叉樹
BiTNode *s[MaxSize];
int top=-1;
BT=NULL;
BiTNode *p=NULL;
int k, j=0;
char ch;
ch=str[j];
while(ch!='\0'){
switch(ch){
case '(':
top++;
s[top]=p;
k=1;
break;
case ')':
top--;
break;
case ',':
k=2;
break;
default:
p=(struct BiTNode *) malloc(sizeof(struct BiTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(BT==NULL)
BT=p;
else{
if(k==1)
s[top]->lchild=p;
else
s[top]->rchild=p;
}
}
j++;
ch=str[j];
}
}
void PrintBtree(BiTNode *BT){//輸出二叉樹
if(BT!=NULL){
putchar(BT->data);
if(BT->lchild!=NULL||BT->rchild!=NULL){
putchar('(');
PrintBtree(BT->lchild);
if(BT->rchild!=NULL)
putchar(',');
PrintBtree(BT->rchild);
putchar(')');
}
}
}
void inorder(BiTNode *BT){//中序遍歷二叉樹
if(BT!=NULL){
inorder(BT->lchild );
printf("%c ",BT->data);
inorder(BT->rchild );
}
}
void DeleteBtree(BiTNode *BT){//刪除二叉樹的所有的節點
if(BT!=NULL){
DeleteBtree(BT->lchild );
DeleteBtree(BT->rchild );
free(BT);
}
}
void ClearBtree(BiTNode *&BT){//清除二叉樹
DeleteBtree(BT);
BT=NULL;
}
void main(){
BiTNode *BT,*BT1;
char c;
printf("請以廣義表形式輸入壹個二叉數 （如A(B(C,D),E(,F))的形式）\n\n");
char string[Number]="A(B(,C),D(E(F),G(,H)))";
/*char string[Number],ch;
int i=0;
ch=getchar();
while(ch!='\n' && i<Number){
string[i]=ch;
i++;
ch=getchar();
}
string[i]='\0';
*///想要按要求自己輸入只需去掉此部分的註釋即可
printf("這裏為了減少重復輸入，測試采用默認的輸入：\n");
InitBtree(BT);
CreateBiTree(BT,string);
PrintBtree(BT);
printf("\n\n\n中序遍歷二叉樹順序為： ");
inorder(BT);
printf("\n\n");
ClearBtree(BT);
scanf("%c",&c );
}