#include <stdio.h>
#include <stdlib.h>
typedef struct _BinaryTree{
int key;
struct _BinaryTree *left;
struct _BinaryTree *right;
}BinaryTree;
int searchBST(BinaryTree *T, int key, BinaryTree *f, BinaryTree **p)
{
if(T == NULL){
*p = f;
return 0;
}
if(T->key == key){
*p = T;
return 1;
}
if(key < T->key){
return searchBST(T->left, key, T, p);
}else{
return searchBST(T->right, key, T, p);
}
}
int insertBST(BinaryTree **T, int key)
{
BinaryTree *p;
BinaryTree *s;
if( 0 == searchBST(*T, key, NULL, &p) ){
s = malloc(sizeof(BinaryTree));
s->key = key;
s->left = s->right = NULL;
if(p == NULL){
*T = s;
}else{
if(s->key < p->key){
p->left = s;
}else{
p->right = s;
}
}
return 1;
}else{
return 0;
}
}
int delete(BinaryTree **p)
{
BinaryTree *q;
BinaryTree *s;
if(NULL == (*p)->right){
q = *p;
*p = (*p)->left;
free(q);
}else if(NULL == (*p)->left){
q = *p;
*p = (*p)->right;
free(q);
}else{
q = *p;
s = (*p)->left;
while(s->right != NULL){
s = s->right;
}
s->right = (*p)->right;
(*p) = (*p)->left;
free(q);
}
}
int deleteBST(BinaryTree **T, int key)
{
if(*T == NULL){
return 0;
}
if((*T)->key == key){
return delete(T);
}else if( key < (*T)->key ){
return deleteBST( &(*T)->left, key);
}else{
return deleteBST( &(*T)->right, key);
}
}
void printTree(BinaryTree *T){
if(T == NULL){
return;
}
printf(" %d", T->key );
printf("(");
if(T->left != NULL){
printTree(T->left);
}
printf(",");
if(T->right != NULL){
printTree(T->right);
}
printf(")");
}
void main()
{
int seq[] = { 0, 45, 24, 53, 45, 12, 24, 90};
int n = sizeof(seq)/sizeof(int);
int i;
BinaryTree *T = NULL;
printf("Original data:\n");
for (i=0; i<n; i++) {
printf("%d\t", seq[i]);
}
printf("\n");
printf("Insert binary search tree:\n");
for(i=1;i<n;i++){
insertBST(&T, seq[i]);
}
printf("\n");
printf("Print the tree:\n");
printTree(T);
printf("\n");
printf("Delete node:\n");
deleteBST(&T, 45);
printf("Print the tree:\n");
printTree(T);
printf("\n");
}