#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*结构体节点*/
typedef struct _node{
int key;
struct _node *left;
struct _node *right;
struct _node *parent;
}node;
/*插入节点*/
void insert(node *root,node *toInsert)
{
node *p,*q;
p=root;
q=NULL;
if(toInsert==NULL || root==NULL)
{
return;
}
while(p!=NULL)
{
q=p;/*记录父节点*/
if(toInsert->key<p->key)
{
p=p->left;
}else{
p=p->right;
}
}
if(toInsert->key<q->key)
{
q->left=toInsert;
}else{
q->right=toInsert;
}
toInsert->parent=q;
toInsert->left=NULL;
toInsert->right=NULL;
}
/*递归中序遍历根节点*/
void middleSearch(node *root)
{
if(root!=NULL)
{
middleSearch(root->left);
printf("%d\t",root->key);
middleSearch(root->right);
}
}
/*先序遍历*/
void preSearch(node *root)
{
if(root!=NULL)
{
printf("%d\t",root->key);
preSearch(root->left);
preSearch(root->right);
}
}
/*查找返回节点关键字为key的节点*/
node* search(node *root,int key)
{
node *p=root;
while(p!=NULL)
{
if(key<p->key)
{
p=p->left;
}else if(key>p->key)
{
p=p->right;
}else
break;
}
return p;
}
/*查找二叉树最小值*/
node *minimun(node *root)
{
node *p=root;
if(p==NULL)
return p;
while(p->left!=NULL)
p=p->left;
printf("min %d\n",p->key);
return p;
}
/*查找二叉树最大值*/
node *maximun(node *root)
{
node *p=root;
if(p==NULL)
return;
while(p->right!=NULL)
p=p->right;
printf("max %d\n",p->key);
return p;
}
/*找节点后续*/
node* successor(node *x)
{
node *p;
if(NULL==x)
return x;
if(x->right!=NULL)
return minimun(x->right);
p=x->parent;
while(p!=NULL && p->right==x)
{
x=p;
p=p->parent;
}
return p;
}
/*删除节点*/
void delete(node *root,node *toDelete)
{
node *p,*q;
int key;
if(root==NULL || toDelete==NULL)
return ;
p=toDelete->parent;
/*第一种情况，要删除的节点的左右子树都为空*/
if(toDelete->left ==NULL && toDelete->right ==NULL)
{
if(p==NULL)/*要删除的是根节点*/
{
free(toDelete);
return;
}
if(p->left==toDelete)
{
p->left=NULL;
}else
p->right=NULL;
free(toDelete);
}
/*第二种情况，要删除的左子树为空，右子树不为空*/
else if(toDelete->left==NULL)
{
if(p==NULL)
{
q=root->right;
root->key=q->key;
root->left=q->left;
root->right=q->right;
free(q);
return;
}
else if(p->left==toDelete)
{
p->left=toDelete->right;
}else
p->right=toDelete->right;
toDelete->right->parent=p;
free(toDelete);
}
/* 第三种情况，要删除的右子树为空，左子树不为空*/
else if(toDelete->right==NULL)
{
if(p==NULL)
{
q=root->left;
root->key=q->key;
root->left=q->left;
root->right=q->right;
root->parent=NULL;
free(q);
return;
}
else if(p->left==toDelete)
{
p->left=toDelete->left;
}else
p->right=toDelete->right;
toDelete->parent=p;
free(toDelete);
}
/* 第四种情况，要删除的左右子树都不为空*/
else{
q=successor(toDelete);
key=q->key;
delete(root,q);
toDelete->key=key;
}
}
int main()
{
node *root;
int a[12]={15,5,3,12,10,13,6,7,16,20,18,23};
node *toInsert;
node *x,*y;
int i;
/*创建头节点*/
if((root=(node*)malloc(sizeof(node)))==NULL)
{
perror("malloc error");
exit(1);
}
root->key=a[0];
/*插入节点*/
for(i=1;i<12;i++)
{
if((toInsert=(node*)malloc(sizeof(node)))==NULL)
{
perror("malloc error");
exit(1);
}
toInsert->key=a[i];
insert(root,toInsert);
}
/*中序遍历*/
middleSearch(root);
printf("\n");
/*先序遍历*/
preSearch(root);
printf("\n");
/*最大值*/
maximun(root);
/*最小值*/
minimun(root);
/*查找关键字节点及其前驱*/
x=search(root,6);
y=successor(x);
if(y!=NULL)
printf("节点 6 后驱 %d\n",y->key);
x=search(root,3);
y=successor(x);
if(y!=NULL)
printf("节点 3 后驱 %d\n",y->key);
x=search(root,13);
y=successor(x);
if(y!=NULL)
printf("节点 13 后驱 %d\n",y->key);
x=search(root,23);
y=successor(x);
if(y!=NULL)
printf("节点 23 后驱 %d\n",y->key);
/*删除节点*/
printf("before delete the node\n");
x=search(root,13);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
if((toInsert=(node*)malloc(sizeof(node)))==NULL)
{
perror("malloc error");
exit(1);
}
toInsert->key=13;
insert(root,toInsert);
printf("\n中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\nbefore delete the node\n");
x=search(root,16);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
if((toInsert=(node*)malloc(sizeof(node)))==NULL)
{
perror("malloc error");
exit(1);
}
toInsert->key=16;
insert(root,toInsert);
printf("\n中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\nbefore delete the node\n");
x=search(root,5);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
if((toInsert=(node*)malloc(sizeof(node)))==NULL)
{
perror("malloc error");
exit(1);
}
toInsert->key=5;
insert(root,toInsert);
printf("\n中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\nbefore delete the node\n");
x=search(root,15);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\n");
printf("before delete the node\n");
x=search(root,16);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\n");
printf("before delete the node\n");
x=search(root,18);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\n");
printf("before delete the node\n");
x=search(root,20);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\n");
printf("before delete the node\n");
x=search(root,23);
delete(root,x);
printf("\nafter delete the node\n");
printf("中序遍历\n");
middleSearch(root);
printf("\n先序遍历\n");
preSearch(root);
printf("\n");
}