#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<stdbool.h>
#define MaxSize 40
typedef struct node{
char data;
struct node *lchild;
struct node *rchild;
}BTNode;
BTNode *CreateBTree(BTNode *b, char str[]){
BTNode *St[MaxSize], *p=NULL;
int top=-1,k,j=0;
char ch;
ch = str[j];
while(ch != '\0'){
switch(ch){
case '(':
top++;
St[top]=p;
k=1;
break;
case ')':
top--;
break;
case ',':
k=2;
break;
default:
p=(BTNode *)malloc(sizeof(BTNode));
p ->data=ch;
p ->lchild = p ->rchild = NULL;
if(b == NULL)
b=p;
else{
switch(k){
case 1:
St[top] ->lchild = p;
break;
case 2:
St[top] ->rchild =p;
break;
}
}
}
j++;
ch = str[j];
}
return b;
}
void PreOrder(BTNode *b){
if(b != NULL){
printf("%c ",b -> data);
PreOrder(b -> lchild);
PreOrder(b -> rchild);
}
}
void InOrder(BTNode *b){
if(b != NULL){
InOrder(b -> lchild);
printf("%c ",b -> data);
InOrder(b -> rchild);
}
}
void PostOrder(BTNode *b){
if(b != NULL){
PostOrder(b -> lchild);
PostOrder(b -> rchild);
printf("%c ",b -> data);
}
}
int main(void){
BTNode * b=NULL;
char str[66],c;
int i=0,chose;
printf("输入'*'号结束输入二叉树式子\n");
printf("请输入一个二叉树式子\n");
while(true){
if((c=getchar())!= '*'){
str[i]=c;
i++;
}
else{
printf("输入终止");
break;
}
}
b = CreateBTree(b,str);
printf("对应的二叉树已经建立完毕");
while(true){
printf("\n\n请选择下列功能选项\n\n");
printf("1.先序遍历输出二叉树\n2.中序遍历输出二叉树\n3.后序遍历输出二叉树\n");
printf("\n请输入您的选择：");
scanf("%d",&chose);
if(chose>0 && chose<4){
switch(chose){
case 1:
printf("以先序方式遍历二叉树\n");
PreOrder(b);
break;
case 2:
printf("以中序方式遍历二叉树\n");
InOrder(b);
break;
case 3:
printf("以后序方式遍历二叉树\n");
PostOrder(b);
break;
}
}
else
printf("请输入1-3中的其中一个数");
}
return 0;
}
网友评论