Question

编程：二叉排序树，必须实现构建，查找，插入，删除四个基本操作

简单的问题，可是我不会，还要请高手帮帮忙，马上就要答辩了啊~~
辛苦了啊！

Answer 1

#include <stdio.h>
#include <malloc.h>

typedef struct BiTnode
{
int data;
struct BiTnode *lchild,*rchild;
}BiTnode,*BiTree;

BiTree search_tree(BiTree T,int keyword,BiTree *father)
{
BiTree p;
*father = NULL;
p = T;
while (p && p->data!=keyword)
{
*father = p;
if (keyword < p->data)
p = p->lchild;
else
p = p->rchild;
}
return p;
}

BiTree creat_tree(int count)
{
BiTree T,p;
int i = 1;
while (i <= count)
{
if (i == 1)
{
p = (BiTnode *)malloc(sizeof(BiTree));
if (!p)
return NULL;
T = p;
scanf("%d",&p->data);
p->lchild = p->rchild = NULL;
i++;
}
else
{
int temp;
scanf("%d",&temp);
search_tree(T,temp,&p);
if (temp < p->data)
{
p->lchild = (BiTnode *)malloc(sizeof(BiTnode));
if (!p->lchild)
return NULL;
p = p->lchild;
}
else
{
p->rchild = (BiTnode *)malloc(sizeof(BiTnode));
if (!p->rchild)
return NULL;
p = p->rchild;
}
p -> data = temp;
p -> lchild = p->rchild = NULL;
i++;
}
}
return T;
}

int insert_tree(BiTree *T,int elem)
{
BiTree s,p,father;
s = (BiTnode *)malloc(sizeof(BiTnode));
if (!s)
return -1;
s->data = elem;
s->lchild = s->rchild = NULL;
p = search_tree(*T,elem,&father);
if (!p)
return -1;
if (father == NULL)
*T = s;
else if (elem < father->data)
father->lchild = s;
else
father->rchild = s;
return 0;
}

int delete_tree(BiTree *T,int elem)
{
BiTree s,p,q,father;
p = search_tree(*T,elem,&father);
if(!p)
return -1;
if(!p->lchild)
{
if (father == NULL)
{
*T = p->rchild;
free(p);
return 0;
}
if (p == father->lchild)
father->lchild = p->rchild;
else
father->rchild = p->rchild;
free(p);
return 0;
}
else
if(!p->rchild)
{
if (father == NULL)
{
*T = p->lchild;
free(p);
return 0;
}
if (p == father->lchild)
father->lchild = p->lchild;
else
father->rchild = p->lchild;
free(p);
return 0;
}
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 0;
}
}

main()
{
}