#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");
}