#include <stdio.h>
#include <malloc.h>
#define TRUE 1
#define FALSE 0
int data[10] = {62,88,58,47,35,73,51,99,37,93};
typedef int Status;
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild;
}BiTNode;
BiTNode *Father, *temp;
/*递归查找二叉排序树是否存在key*/
/*指针f指向T的双亲，其初始调用值为NULL*/
BiTNode* SearchBST(BiTNode *T, int key, BiTNode *f, BiTNode *p)
{
if(T == NULL)
{
p = f;
return p;
}
if(key == T->data)
{
p = T;
Father = f;
temp = p;
return NULL;
}
else if(key < T->data)
{
SearchBST(T->lchild, key, T, p);
}
else
{
SearchBST(T->rchild, key, T, p);
}
}
/*插入节点*/
Status InsrBiTNode(BiTNode *T, int key)
{
BiTNode *p = NULL, *temp = T;
p = SearchBST(temp, key, NULL, p);
if(!p)
return FALSE;
else
{
temp = (BiTNode *)malloc(sizeof(BiTNode));
temp->data = key;
temp->lchild = NULL;
temp->rchild = NULL;
if(p->data > key)
{
p->lchild = temp;
}
else
{
p->rchild = temp;
}
return TRUE;
}
}
Status createBiTree(BiTNode *T)
{
int i;
BiTNode *temp = T;
for(i = 1; i < 10; i++)
{
InsrBiTNode(temp, data[i]);
}
}
/*中序遍历*/
Status MidTrav(BiTNode *T)
{
if(!T)
return FALSE;
MidTrav(T->lchild);
printf("%d ", T->data);
MidTrav(T->rchild);
}
/*删除结点*/
Status delBiTNode(BiTNode *T, int key)
{
BiTNode *p = NULL, *temp2;
int val = 0;
p = SearchBST(T, key, NULL, p);
if(p)
{
printf("删除错误：树种不存在%dn",key);
return FALSE;
}
/*判断p是不是只有独子*/
if((temp->lchild != NULL && temp->rchild == NULL) ||
(temp->rchild != NULL && temp->lchild == NULL))
{
/*只有左孩子*/
if(temp->lchild && !temp->rchild)
{
Father->lchild = temp->lchild;
}
/*只有右孩子*/
else
{
Father->lchild = temp->rchild;
}
free(temp);
}
//删除二叉排序树叶子结点
else if(!temp->lchild && !temp->rchild)
{
if(Father->lchild == temp)
{
Father->lchild = NULL;
free(temp);
}
else
{
Father->rchild = NULL;
free(temp);
}
}
/*删除的结点左右孩子都存在*/
else
{
temp2 = temp;
/*先左后右找直接前驱*/
temp = temp->lchild;
while(temp != NULL)
{
val = temp->data;
temp = temp->rchild;
}
delBiTNode(T, val);
temp2->data = val;
}
}
int main(void)
{
BiTNode *T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = data[0];
T->lchild = NULL;
T->rchild = NULL;
createBiTree(T);
printf("二叉排序树中序遍历结果：n");
MidTrav(T);
printf("n");
printf("删除只存在左孩子58结果：n");
delBiTNode(T, 58);
MidTrav(T);
printf("n");
printf("删除只存在右孩子35结果：n");
delBiTNode(T, 35);
MidTrav(T);
printf("n");
printf("删除存在左右孩子62结果：n");
delBiTNode(T, 62);
MidTrav(T);
return 0;
}