从键盘读入一串整数构造一棵二叉排序树，并对得到的二叉排序述进行中序遍历，得到有序序列。

Question

要求：该二叉排序树以二叉链表存储

Answer 1

利用c语言，代码如下仅供参考：

说明：为了保证输入的数据按要求构造出想要的、唯一确定的二叉树的形状，这里输入要求利用广义表的形式，虽然会显得繁琐一点，但足以保证严谨性。否则只是单纯一串数字，树形就能千变万化，不一定的。

#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 );
}本回答被提问者采纳