/* 新建结点赋值，特别是左右子结点指针要赋值为NULL */
pNewNode->key = key;
pNewNode->lchild = NULL;
pNewNode->rchild = NULL;
/* 二叉排序树是空树 */
if （*tree==NULL）
{
*tree = pNewNode;
return 0;
}
else
{
p = *tree;
/* 寻找插入位置 */
while （NULL != p）
{
/* key值已在二叉排序树中 */
if （p->key == key）
{
return 0;
}
else
{
parent = p;
p = （p->key < key） p->rchild : p->lchild;
}
}
if （parent->key < key）
{
parent->rchild = pNewNode;
}
else
{
parent->lchild = pNewNode;
}
return 0;
}
}
//删除节点
/* 通过值查找并删除一个结点 */
int delNode（BSTree **tree, KeyType key）
{
BSTNode *p = NULL, *q = NULL, *parent = NULL, *child = NULL;
p = *tree;
/* parent为NULL表示根结点的父亲为NULL */
while （NULL != p）
{
if （p->key == key）
{
break;
}
else
{ parent = p;
p = （p->key < key） p->rchild : p->lchild;
}
}
/* p为NULL时， 表示没有找到结点值为key的结点 */
if （NULL == p）
{
return 0;
}
/* p, q现在都是保存了待删结点指针 */
q = p;
/* 待删结点有两个儿子结点，进行一下转化 */
if （NULL != p->lchild && NULL != p->rchild）
{
//找中序后继，先右拐，然后左走到底
parent = p;
p = p->rchild;
while （NULL != p->lchild）
{
parent = p;
p = p->lchild;
}
/* p中保存了待删结点右子树中最左下的结点指针， parent中就保存了该结点父亲指针 */
child = p->rchild;
}
/* parent保存待删结点的父亲结点指针， child保存了待删结点的儿子结点
//实际删除的是待删节点的直接后继，下面是删除直接后继的过程，（待删结点至多只有一个儿子， 有两个会转化为0个或1个右结点）
待删结点是根结点 */
if （NULL == parent）
{
*tree = child;
}
else
{
/*待删结点是父亲结点的左儿子*/
if （parent->lchild == p）
{
parent->lchild = child;
}
else
{
parent->rchild = child;
}
//将实际删除的节点的key值赋给原先要删除的节点
if （p != q）
{
q->key = p->key;
}
}
free（p）；
return 0;
}
//二叉排序树查找
BSTNode* SearchBST（BSTree *T,KeyType key）
{ //在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返回NUll
if（T==NULL） //递归的终结条件
return NULL; //T为空，查找失败；
if（key==T->key）
//成功，返回找到的结点位置
{
printf（"Got it!"）；
return T;
}
if（key<T->key）
return SearchBST（T->lchild,key）；
else
return SearchBST（T->rchild,key）；//继续在右子树中查找
} //SearchBST
int main（）
{
int n;
BSTree *B=NULL;
printf（"Input number to initialize a BSTree:"）；
while（1）
{
scanf（"%d",&n）；
if（n==0） break;
InsertNode（&B, n）；
}
dispTree（B）；
printf（"PreOrder:"）；
preOrder（B）；
printf（"\n"）；
printf（"Search a node:"）；
scanf（"%d",&n）；
SearchBST（B,n）；
printf（"\n"）；
printf（"Delete a node:"）；
scanf（"%d",&n）；
delNode（&B,n）；
dispTree（B）；
printf（"PreOrder:"）；
preOrder（B）；
printf（"\n"）；
return 1;
}
#include<stdio.h>
#include<stdlib.h>
#define maxSize 20
#define maxWidth 20
typedef int KeyType; //假定关键字类型为整数
typedef struct node { //结点类型
KeyType key; //关键字项
struct node *lchild,*rchild;//左右孩子指针
} BSTNode,BSTree;
//typedef BSTNode *BSTree; //BSTree是二叉排序树的类型
//先序遍历
void preOrder（BSTree *BT）
{
if（BT!= NULL）
{
printf（"%d",BT->key）；
preOrder（BT->lchild）；
preOrder（BT->rchild）；
}
}
//中序遍历
void inOrder（BSTree *BT）
{
if（BT!= NULL）
{
inOrder（BT->lchild）；
printf（"%d",BT->key）；
inOrder（BT->rchild）；
}
}