二叉查找树示例

In computer science, a binary search tree (BST) is a binary tree where every node has a value, every node's left subtree contains only values less than or equal to the node's value, and every node's right subtree contains only values that are greater than or equal. (Depending on the application of the binary search tree, equal values may not be allowed in either the left or right subtree).

二叉查找树又叫二叉排序树，属于二叉树的一种特例。它的左子树上所有节点的值均小于根节点的值，它的右子树上的所有节点的值均大于根节点的值，并且其左右子树也都是二叉查找树。搜索,插入,删除的复杂度等于树高，O(log(n)).

#include "stdio.h"
#include "stdlib.h"

struct Node 
...{
    int key;//结点值
    struct Node *parent;//父结点
    struct Node *left;//左结点
    struct Node *right;//右结点
};

//打印二叉树
void PrintTree(struct Node *Root)
...{
    struct Node *pointer=(struct Node*)malloc(sizeof(struct Node));
    pointer=Root;
    if(pointer!=NULL)
    ...{
        PrintTree(pointer->left);
        printf("%d ",pointer->key);
        PrintTree(pointer->right);
    }
}

//删除树，递归释放树的结点
void DeleteTree(struct Node *Root)
...{
    struct Node *pointer=(struct Node*)malloc(sizeof(struct Node));
    pointer=Root;

    if(pointer!=NULL)
    ...{
        DeleteTree(pointer->left);
        free(pointer);
        DeleteTree(pointer->right);
    }
}

//最小值
struct Node *Minimum(struct Node *Root)
...{
    struct Node *pointer=(struct Node*)malloc(sizeof(struct Node));
    pointer=Root;

    while(pointer->left!=NULL)
        pointer=pointer->left;

    return pointer;
}

//最大值
struct Node *Maximum(struct Node *Root)
...{
    struct Node *pointer=(struct Node*)malloc(sizeof(struct Node));
    pointer=Root;

    while(pointer->right!=NULL)
        pointer=pointer->right;

    return pointer;
}

//查找
struct Node *Search(struct Node *Root,int value)
...{
    struct Node *pointer=(struct Node*)malloc(sizeof(struct Node));
    pointer=Root;

    while(pointer!=NULL&&pointer->key!=value)
    ...{
        //如果查找值比结点值小，查找它的左子树
        if(value<pointer->key)
            pointer=pointer->left;
        else
            pointer=pointer->right;//如果查找值比结点值大，查找它的右子树
    }

    return pointer;
}

//后继
struct Node *Successor(struct Node *pointer)
...{
    if(pointer->right!=NULL)
        return Minimum(pointer->right);

    struct Node *y=(struct Node*)malloc(sizeof(struct Node));
    y=pointer->parent;
    while(y!=NULL&&y->right==pointer)
    ...{
        pointer=y;
        y=pointer->parent;    
    }

    return y;
}

//前驱
struct Node *Predecessor(struct Node *pointer)
...{
    if(pointer->left!=NULL)
        return Maximum(pointer->left);

    struct Node *y=(struct Node*)malloc(sizeof(struct Node));
    y=pointer->parent;
    while(y!=NULL&&y->left==pointer)
    ...{
        pointer=y;
        y=pointer->parent;    
    }

    return y;
}

//插入新结点
struct Node *Insert(struct Node *Root,struct Node *newNode)
...{
    struct Node *back=(struct Node*)malloc(sizeof(struct Node));
    struct Node *pointer=(struct Node*)malloc(sizeof(struct Node));
    back=NULL;
    pointer=Root;

    //找到要插入的位置
    while(pointer!=NULL)
    ...{
        back=pointer;
        if(newNode->key<pointer->key)
            pointer=pointer->left;
        else
            pointer=pointer->right;
    }

    //新结点的Parent指针先指向父结点
    newNode->parent=back;
    
    if(back==NULL)
        Root=newNode;//树为空，新结点成为树根
    else 
    ...{
        if(newNode->key<back->key)
            back->left=newNode;
        else 
            back->right=newNode;
    }

    return Root;
}

//删除结点
struct Node *Delete(struct Node *Root,struct Node *pointer)
...{
    struct Node *y=(struct Node*)malloc(sizeof(struct Node));
    y->parent=NULL;
    y->left=NULL;
    y->right=NULL;
    //找到实际要删除的结点
    if(pointer->left==NULL||pointer->right==NULL)
        y=pointer;
    else
        y=Successor(pointer);

    struct Node *x=(struct Node*)malloc(sizeof(struct Node));
    x->parent=NULL;
    x->left=NULL;
    x->right=NULL;
    //要删除结点的子结点
    if(y->left!=NULL)
        x=y->left;
    else
        x=y->right;

    if(x!=NULL)
        x->parent=y->parent;
    
    if(y->parent==NULL)
        Root=x;//删除的是根结点
    else
    ...{
        if(y==y->parent->left)
            y->parent->left=x;
        else
            y->parent->right=x;
    }

    if(y!=pointer)
        pointer->key=y->key;

    if(y!=NULL)
    ...{
        free(y);
        printf("Delete success! ");
    }
    else
        printf("Delete failure! ");

    return Root;    
}

int main()
...{
    struct Node *Root=NULL;
    int value;
    
    int flag=1;
    while(flag)
    ...{    
        printf("1:Insert ");
        printf("2:Delete ");
        printf("3:Search ");
        printf("4:Minimum ");
        printf("5:Maximum ");
        printf("6:Successor ");
        printf("7:Predecessor ");
        printf("0:Exit ");
        printf("Please input your choice:");
        scanf("%d",&flag);

        switch(flag)
        ...{
        case 0:
            return 0;
        case 1:
            ...{
                printf("Please input the value you want to input:");
                scanf("%d",&value);
                struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));
                newNode->key=value;
                newNode->parent=NULL;
                newNode->left=NULL;
                newNode->right=NULL;
                Root=Insert(Root,newNode);
                break;
            }
        case 2:
        ...{
            printf("Please input the value you want to delete:");
            scanf("%d",&value);
            struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));
            newNode=Search(Root,value);
            if(newNode!=NULL)
                Root=Delete(Root,newNode);
            else
                printf("%d does'n exist in this tree! ",value);
            break;
        }
        case 3:
        ...{
            printf("Please input the value you want to input:");
            scanf("%d",&value);
            struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));
            newNode=Search(Root,value);
            if(newNode!=NULL)
                printf("%d exist in this tree! ",newNode->key);
            else
                printf("%d does'n exist in this tree! ",value);
            break;
        }
        case 4:
        ...{        
            if(Root!=NULL)
            ...{
                struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));
                newNode=Minimum(Root);
                printf("The minimum value of this tree is %d! ",newNode->key);
            }
            else
                printf("This tree is empty! ");
            break;
        }
        case 5:
        ...{        
            if(Root!=NULL)
            ...{
                struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));
                newNode=Maximum(Root);
                printf("The Maximum value of this tree is %d! ",newNode->key);
            }
            else
                printf("This tree is empty! ");
            break;
        }
        case 6:
        ...{
            printf("Please input the value:");
            scanf("%d",&value);
            struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));
            newNode=Search(Root,value);
            if(newNode!=NULL)
            ...{
                newNode=Successor(newNode);
                if(newNode!=NULL)
                    printf("%d's successor is %d! ",value,newNode->key);
                else
                    printf("%d has't successor int this tree! ",value);
            }
            else
                printf("%d does'n exist in this tree! ",value);
            break;
        }
        case 7:
        ...{
            printf("Please input the value:");
            scanf("%d",&value);
            struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));
            newNode=Search(Root,value);
            if(newNode!=NULL)
            ...{
                newNode=Predecessor(newNode);
                if(newNode!=NULL)
                    printf("%d's Predecessor is %d! ",value,newNode->key);
                else
                    printf(