search_tree.c

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

struct node {
    node *left;
    node *right;
    node *parent;
    int value;
};

node *init(const int value){
    node *n = (node*)malloc(sizeof(node));
    n->left = NULL;
    n->right = NULL;
    n->parent = NULL;
    n->value = value;
    return n;
}

int put(node *root, const int value){
    node *p = root;
    node *c = (node*)malloc(sizeof(node));
    c->left = NULL;
    c->right = NULL;
    c->parent = NULL;
    c->value = value;

    while(p){
        if(value==p->value) break;
        if(value<p->value){
            if(!p->left){
                p->left = c;
                c->parent = p;
                break;
            }
            p = p->left;
        } else if(value>p->value){
            if(!p->right){
                p->right = c;
                c->parent = p;
                break;
            }
            p = p->right;
        }
    }

    return 1;
}

node *find_trans(node *root){
    /*
    如果要删除一个结点，则查找
    右子树中的最小值
    或者
    左子树中的最大值
    与要删除的结点交换
     */
    node *p = root;
    if(p->left){
        p = p->left;
        while(p->right){
            p = p->right;
        }
    } else {
        p = p->right;
        while(p->left){
            p = p->left;
        }
    }
    return p;
}

int del(node *root, const int value){
    node *p = root;
    while(p){
        if(value==p->value){
            printf("hit and removed %d\n", p->value);
            /* remove */
            if(!p->left&&!p->right){
                /* nil child */
                if(p->value>p->parent->value){
                    /*at right*/
                    p->parent->right = NULL;
                } else {
                    p->parent->left = NULL;
                }
            } else {
                node *tmp = find_trans(p);
                if(p->value>p->parent->value){
                    /*at right*/
                    p->parent->right = tmp;
                } else {
                    p->parent->left = tmp;
                }
                tmp->parent = p->parent;
            }
            p->value = NULL;
            p->left=NULL;
            p->right=NULL;
            p->parent=NULL;
            free(p);
            return 1;
        }
        if(value<p->value){
            p = p->left;
        } else if(value>p->value){
            p = p->right;
        }
    }
    return 0;
}

void print_tree(node *root){
    if(!root) return;
    print_tree(root->left);
    printf("%d\n", root->value);
    print_tree(root->right);
}

int main(){
    const int root_value = 10;
    node *n = init(root_value);
    put(n, 7);
    put(n, 11);
    put(n, 14);
    put(n, 18);
    del(n, 11);
    del(n, 30);
    put(n, 1);
    put(n, 9);
    del(n, 1);
    print_tree(n);
    return 0;
}