数据结构——二叉排序树

给定关键字序列:63, 90, 70, 55, 67, 42, 98, 83, 10, 45, 58 要求:
l.构建二叉排序树
2.对该树中序遍历,显示其序列
3.依次删除10,42,63
4.再次对该树中序遍历,显示其序列
(运用C语言)

1个回答

#include
#include
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int TElemType;
typedef struct BTNode
{
TElemType data;
struct BTNode *lchild,*rchild;
}BTNode,*BTree;
Status SearchBT(BTree T,TElemType key,BTree f,BTree *p);//查找算法
Status InsertBT(BTree *T,TElemType key);//插入算法
Status Delete(BTree *p);//删除数据算法
Status DeleteBT(BTree *T,TElemType key);//删除算法
void InOrderTraverse(BTree T);//中序遍历二叉树
int main(){
int i,x,n;
BTree p;
BTree T = NULL;
int a[11] = {63,90,70,55,67,42,98,83,10,45,58};
for(i=0;i InsertBT(&T,a[i]);
}
while(1)
{
printf("1.中序遍历 2.删除算法 3.添加算法 \n");
scanf("%d",&n);
switch(n) { case 1: printf("中序遍历二叉树\n"); InOrderTraverse(T); printf("\n"); break; case 2: printf("输入要删除的数\n"); scanf("%d",&x); DeleteBT(&T,x); break; case 3: printf("输入要添加的数\n"); scanf("%d",&x); InsertBT(&T,x); } }}Status SearchBT(BTree T,TElemType key,BTree f,BTree *p){ if(!T)//查找不成功 { *p = f; return FALSE; } else if(key == T->data)//查找成功 { *p = T; return TRUE; } else if(key < T->data) { return SearchBT(T->lchild,key,T,p); } else return SearchBT(T->rchild,key,T,p);}Status InsertBT(BTree *T,TElemType key){ BTree p,s; if(!SearchBT(*T,key,NULL,&p)) { s = (BTree)malloc(sizeof(BTNode)); s->data = key; s->lchild = s->rchild = NULL; if(!p) *T = s; else if(key < p->data) p->lchild = s; else p->rchild = s; return TRUE; } else return FALSE;}Status Delete(BTree *p){ BTree q,s; if((*p)->rchild == NULL)//右子树空只需连接它的左子树 { q = *p; *p = (*p)->lchild; free(q); } else if((*p)->lchild == NULL)//左子树空只需连接它的右子树 { q = *p; *p = (*p)->rchild; free(q); } else//左右子树均不空 { q = *p; s = (*p)->lchild; while(s->rchild)//转左,然后向右到尽头 { q = s;s = s->rchild; } (*p)->data = s->data; if(q != *p) q->rchild = s->lchild; else q->lchild = s->lchild; free(s); } return TRUE;}Status DeleteBT(BTree *T,TElemType key){ if(!*T)//要删除的数不存在 return FALSE; else { if(key == (*T)->data) return Delete(T); else if(key < (*T)->data) return DeleteBT(&(*T)->lchild,key); else return DeleteBT(&(*T)->rchild,key); }}void InOrderTraverse(BTree T){ if(T == NULL) return; InOrderTraverse(T->lchild); printf("%d ",T->data); InOrderTraverse(T->rchild);}

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问