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

struct node{
int data;
struct node *lchild;
struct node *rchild;
};
typedef struct node NODE;
typedef struct node *PNODE;

PNODE create(PNODE tree,PNODE p,int key)//建树
{
if(!p) //分配空间
{
p=(PNODE)malloc(sizeof(NODE));
if(!p) //如果不成功则退出
{
printf("内存分配失败!");
exit(0);
}
//成功则开始初始化树
p->lchild=NULL;
p->rchild=NULL;
p->data=key;
if(!tree)
return p;
if(key<tree->data)
tree->lchild=p;
else if(key>tree->data)
tree->rchild=p;
return p;
}
if(key<p->data)
create(p,p->lchild,key);
else if(key>p->data)
create(p,p->rchild,key);
return tree;

}
//下面编写功能方法；

void new_node(PNODE *n,int key)//新结点
{
*n=(PNODE)malloc(sizeof(NODE));
if(*n!=NULL)
{
(*n)->data=key;
(*n)->lchild=NULL;
(*n)->rchild=NULL;
}
}

void free_node(PNODE *n)//释放结点
{
if((*n)!=NULL)
{
free(*n);
*n=NULL;
}
}

PNODE find_node(PNODE n,int key)//查找
{
if(n==NULL)
return NULL;
else if (n->data==key)
return n;
else if(key<n->data)
return find_node(n->lchild,key);
else
return find_node(n->rchild,key);
}

void insert_node(PNODE *n,int key)//插入
{
if(*n==NULL)
new_node(n,key);
else if(key==(*n)->data) //数据一样不用插入，返回。
return;
else if(key>(*n)->data)
insert_node(&((*n)->rchild),key);
else if(key<(*n)->data)
insert_node(&((*n)->lchild),key);
}


void deletenode(PNODE &n,int key)//删除
{

if((n)->data==key)
{
PNODE tmp=NULL;
if((n)->rchild==NULL)//右为空
{
tmp=n;
n=(n)->lchild;
free(tmp);
}else if((n)->lchild==NULL)//左为空
{
tmp=n;
n=(n)->rchild;
free(tmp);
}else{
tmp=n;
PNODE s=n->lchild;
while(s->rchild){
tmp=s;
s=s->rchild;
}
n->data=s->data;
if(tmp!=n)
tmp->rchild=s->lchild;
else
tmp->lchild=s->lchild;
delete(s);
}

}else if(key<n->data)
deletenode(n->lchild,key);
else if(key>n->data)
deletenode(n->rchild,key);
}



void traversal(PNODE n)
{
if(n!=NULL)
{
traversal(n->lchild);
printf("%i ",n->data);
traversal(n->rchild);
}
}

int main()
{
int i,n,option,s[80];
PNODE tree=NULL;
PNODE node=NULL;
printf("输入结点数：");
scanf("%d",&n);
printf("输入%d个数据:",n);
for(i=0;i<n;i++)
{
scanf("%d",&s[i]);
tree=create(tree,tree,s[i]);
}
traversal(tree);
printf("\n\n");
while(1)
{
printf("操作菜单:\n\n");
printf("1 插入\n");
printf("2 删除\n");
printf("3 查找\n");
printf("4 退出\n");
printf("选择要操作的功能:");
scanf("%d",&option);
if(option<0||option>5)
{
printf("输入错误，请重新输入:");
continue;
}
switch(option)
{
case 1:
printf("输入要插入的数：");
scanf("%d",&option);
printf("\n\n");
if(!find_node(tree,option))
{
insert_node(&tree,option);
printf("插入%d成功：",option);
traversal(tree);
}
else {printf("插入%d失败:",option);
printf("\n\n");
traversal(tree);}
printf("\n\n");
break;
case 2:
printf("输入要删除的数:");
scanf("%d",&option);
printf("\n\n");
if(find_node(tree,option))
{
deletenode(tree,option);
printf("删除%d成功:",option);
traversal(tree);
}
else
{printf("删除%d失败",option);
printf("\n\n");
traversal(tree);}
printf("\n\n");

break;
case 3:
printf("输入要查找的数：");
scanf("%d",&option);
printf("\n\n");
node=find_node(tree,option);
if(node!=NULL)
printf("查找成功%d\n\n",(node->data));
else
{printf("查找失败\n\n");
printf("\n\n");traversal(tree);
}

break;
case 4:
break;

}
}
}
源 码奉上；主要看的方法函数是deletenode(),答辩的时候，老师提出了4-2-3-6-5这棵树，然后删除6这个结点，我之前用过 findnode()的方法来找到指定的6节点，然后用deletenode()方法来删除，会出现5这个结点没有了根结点，后来改良后用 deletenode()自己来递归查找6这个结点，然后调用
{
tmp=n;
n=n->lichild;
free(tmp);

}
我的理解是用一个tmp来指向6这个结点，然后n指向他的左孩子，然后n的根节点是4,4的右孩子一直是指向n的，故而言之，释放掉tmp就可以了，然后中序遍历出来没有错误。
但是老师用DEBUG来查找的时候，查到6的指针地址跟删除tmp以后的指针地址不同了，问为什么？
大神们，求助攻！~~