Binary search tree

//二叉查找树的实现
#include <cstdio>
#include <cstdlib>
//#define _OJ_

typedef struct tree1
{
    int data;
    struct tree1 *lchild;
    struct tree1 *rchild;
} tree1, *tree;

tree
find(int x, tree T)
{
    if(T == NULL)
        return NULL;
    if(x < T->data)
        find(x, T->lchild);
    else
    if(x > T->data)
        find(x, T->rchild);
    else
        return T;
}

tree
find_min(tree T)
{

    // printf("fsaf
");
    if(T == NULL)
        return NULL;
    else
        if(T->lchild == NULL)
            return T;
    else
        find_min(T->lchild);
}

tree
find_max(tree T)
{
    if(T != NULL)
        while(T->rchild != NULL)
            find_max(T->rchild);
     return T;
}

tree
insert(int x, tree T)
{
    // printf("dfsad
");
    if(T == NULL)
    {
     T = (tree) malloc (sizeof(tree1));
     T->data = x;
     T->lchild = T->rchild = NULL;
    }
    else
    if(x < T->data)
        T->lchild = insert(x,T->lchild);
    else
    if(x > T->data)
        T->rchild = insert(x,T->rchild);
    return T;
}


tree
del_tree(int x, tree T)
{//找出右子树最小的代替要删除的节点,再删除最小的那个节点!!!
    tree tmp;
    if(T == NULL)
        return NULL;
    else
        if(x < T->data)
            T->lchild = del_tree(x,T->lchild);
    else
        if(x > T->data)
            T->rchild = del_tree(x,T->lchild);
    else                                     //find element to del_tree
        if(T->lchild && T->rchild)//two children
        {
        tmp = find_min(T);
        T->data = tmp->data;
        T->rchild = del_tree(T->data, T->rchild);
        }
        else    //one or zero child
        {
        tmp = T;
        if(T->lchild == NULL)
            T = T->rchild;
        else if(T->rchild == NULL)
            T = T->lchild;printf("%p
", T);
            // free(tmp);
        }
        return T;
}

int main(int argc, char const *argv[]) {
#ifndef _OJ_  //ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int i,n;
    int a[10];
    tree T = NULL;
    tree T1 = NULL;
    tree T2 = NULL;
    scanf("%d", &n);
    for(i = 0;i < n; i++)
    {
    scanf("%d", &a[i]);
    printf("%d
", a[i]);
    }
    T = insert(a[0], T);
    printf("T == %p
", T);
    insert(a[1],T);

    T1 = find_min(T);
    printf("T! == %p
", T1);
    printf("%d
", T1->data);
    del_tree(0,T);
    printf("%p
", T->lchild);
    T2 = find_min(T);
    printf("%d
", T2->data);
    return 0;
}

 

原文地址:https://www.cnblogs.com/airfand/p/4987545.html