值得一说的是删除操作，删除操作我们分为三种情况：
1.要删的节点有两个孩子：
找到左子树中的最大值或者右子树中的最小值所对应的节点，记为node，并把node的值赋给要删除的节点del,然后删除node
实际上真正删除的是node，del只是发生了一次值的替换。
为了方便理解和操作，我们把两个孩子的情况放在最前面，这样经过以上处理后，该节点就会变成情况2或者情况3 ，接下爱这行这两种情况的代码。
2.要删的节点有一个孩子
r判断要删除的节点del是其父亲father的左孩子还是右孩子，以是father的左孩子为例，del是father的左孩子，接下来判断del是否有左孩子，
如果有，则father的左孩子变成del的左孩子，如果没有，则father的左孩子变成del的右孩子。
3.要删的节点没有孩子
即为当情况2 del的左孩子右孩子为空的时候
#include<stdio.h>
#include<stdlib.h>
typedef struct Tree
{
int data;
Tree*right;
Tree*left;
}BinaryTree;
void insert(BinaryTree **p,int e)
{
BinaryTree *temp=(BinaryTree*)malloc(sizeof(BinaryTree));
temp->data=e;
temp->left=NULL;
temp->right=NULL; if(*p==NULL)
{
*p=temp;
return ;
}
BinaryTree*root=*p;
while(1)
{
if(e<root->data)
{
if(root->left)
{
root=root->left;
}
else
{
root->left=temp;
break;//完成插入操作了
} }
else if(e>root->data)
{
if(root->right)
{
root=root->right; }
else
{
root->right=temp;
break;
}
}
}
}
void FindNode(BinaryTree* p,BinaryTree **del,BinaryTree**father, int e)//我们在删除操作中不仅需要知道要删除哪个节点，还要知道要删除节点的父亲
{ //return无法返回两个值，要实现返回两个值，我们在这里采用二级指针
while(1) //实际上也可以通过结构体封装来完成同时返回两个值
{
if(e<p->data)
{
*father=p;//每次都记录一下父亲
p=p->left;
}
else if(e>p->data)
{
*father=p;
p=p->right;
}
else if(e==p->data)
{
*del=p;return ;
}
}
}
void deleteNode(BinaryTree **p,int e)//
{
if(*p==NULL) return ;
BinaryTree *root=*p;
BinaryTree *del=NULL;
BinaryTree *father=NULL;
BinaryTree *pmark=NULL;
FindNode(root,&del,&father,e);
if(del->left&&del->right)
{
pmark=del;//标记要删除的点
father=del;
del=del->left;
while(del->right)
{
father=del;
del=del->right;
}
pmark->data=del->data;
}
//接下来分析有一个或者没有孩子的情况
//被删节点 是根
if(father==NULL)//??
{
*p=del->left?del->left:del->right;
free(del);
return ;
}
else
{//不用在写判断条件了，走到这说明就是一个或者没有孩子，只需要判断是哪边的孩子就可
if(del==father->left)
father->left=del->left?del->left:del->right;
else if(del==father->right)
father->right=del->left?del->left:del->right;
free(del); }
}
void inorder(BinaryTree *p)
{
if(p==NULL) return ;
//递归要有结束条件
inorder(p->left);
printf(" %d ",p->data);
inorder(p->right);
}
void preorder(BinaryTree *p)
{
if(p==NULL) return ;
//递归要有结束条件 printf(" %d ",p->data);
preorder(p->left);
preorder(p->right);
}
int main()
{
int m;
BinaryTree *p=NULL;
int a[10];
int i;
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<m;i++)
{
insert(&p,a[i]);
}
preorder(p);
printf("\n");
inorder(p);
deleteNode(&p,9);
preorder(p);
printf("\n");
inorder(p);
return 0;
}