从键盘读入一串整数构造一棵二叉排序树,并对得到的二叉排序述进行中序遍历,得到有序序列.要求:该二叉排序树以二叉链表存储
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/23 15:10:03
从键盘读入一串整数构造一棵二叉排序树,并对得到的二叉排序述进行中序遍历,得到有序序列.要求:该二叉排序树以二叉链表存储
从键盘读入一串整数构造一棵二叉排序树,并对得到的二叉排序述进行中序遍历,得到有序序列.
要求:该二叉排序树以二叉链表存储
从键盘读入一串整数构造一棵二叉排序树,并对得到的二叉排序述进行中序遍历,得到有序序列.要求:该二叉排序树以二叉链表存储
利用c语言,代码如下仅供参考:
说明:为了保证输入的数据按要求构造出想要的、唯一确定的二叉树的形状,这里输入要求利用广义表的形式,虽然会显得繁琐一点,但足以保证严谨性.否则只是单纯一串数字,树形就能千变万化,不一定的.
#include
#include
#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