bst 二叉搜索树简单实现

//数组实现二叉树：
//    1.下标为零的元素为根节点，没有父节点
//    2.节点i的左儿子是2*i+1；右儿子2*i+2；父节点（i-1）/2；
//    3.下标i为奇数则该节点有有兄弟，否则又左兄弟
//    4.对bst树的操作主要有插入，删除，后继前驱的查找，树最大最小节点查看

#include <iostream>

using namespace std;

struct node{
    node *p,*left,*right;
    int key;
};

node * root = NULL;

//中序输出BST中的全部关键字
void inorder_tree_walk(node * t)
{
    if(t != NULL){
        inorder_tree_walk(t->left);
        cout<<t->key<<" ";
        inorder_tree_walk(t->right);
    }
    return;
}

//查找关键字k，若存在，则返回指向包含k的节点指针；否则，返回NULL
node * tree_search(node * t,int k)
{
    while(t != NULL && t->key != k){
        if(k < t->key) t = t->left;
        else t = t->right;
    }
    return t;
}

//查找最小关键字的节点
node * tree_minimum(node *t)
{
    while(t->left != NULL)
        t = t->left;
    return t;
}

//查找最大关键字的节点
node * tree_maximum(node *t)
{
    while(t->right != NULL)
        t = t->right;
    return t;
}

//查找节点z的后继
//    1.若该节点有有子树则其后继就是该节点有子树中最小节点
//    2.否则其后继就是其最低祖先节点
node * tree_successor(node * z)
{
    if(z->right != NULL)                    //节点存在右子树
        return tree_minimum(z->right);
    node * y = z->p;                        //节点不存在右子树寻找最近祖先节点
    while(y != NULL && z == y->right){
        z = y;
        y = y->p;
    }
    return y;
}

//查找z的前驱节点
node * tree_precursor(node * z)
{
    if(z->left != NULL)
        return tree_maximum(z->left);
    node * y = z->p;
    while(y != NULL && z == y->left){
        z = y;
        y = y->p;
    }
    return y;
}

//在BST中插入关键字的值为k的节点
//    1.插入节点时要寻找该节点的正确位置
//    2.然后插入该节点
void tree_insert(node * t,int k){
    node * z = new node;
    z->key = k;
    z->left = NULL;
    z->right = NULL;
    z->p = NULL;

    node * y = NULL;
    while(t != NULL){                       //寻找该节点的正确位置
        y = t;
        if(z->key < t->key) t = t->left;
        else t = t->right;
    }
    z->p = y;                               //插入该节点
    if(y == NULL) root = z;
    else if(z->key < y->key) y->left = z;
    else y->right = z;
    return;
}

//用以v为根的子树替换以u为根的子树
void transplant(node * u, node *v)
{
    if(u->p == NULL) root = v;
    else if(u == u->p->left) u->p->left = v;
    else u->p->right = v;
    if(v != NULL) v->p = u->p;
    return;
}

//从BST中删除节点z
//    1.被删除的节点没有左儿子就用其有儿子来填补
//    2.被删除的节点仅有左儿子就用其左儿子来填补
//    3.有两个儿子的情况：
//            a.先找出该节点的一个后继结点 y
//            b.y是该节点的右儿子直接用y填补
//            c.否则先用y的右孩子替换y，再用y替换被删节点
void tree_delete(node * z)
{
    if(z->left == NULL)
        transplant(z,z->right);
    else if(z->right == NULL)
        transplant(z,z->left);
    else{
        node * y = tree_minimum(z->right);
        if(y->p != z){
            transplant(y,y->right);
            y->right = z->right;
            y->right->p = y;
        }
        transplant(z,y);
        y->left = z->left;
        y->left->p = y;
    }
    return;
}

int main(){

    int a[]={12,5,18,2,9,15,19,17};
    for(int i=0;i<=7;++i)
    {
        tree_insert(root,a[i]);
    }
    inorder_tree_walk(root);
    cout<<endl;
    cout<<"insert key = 13:"<<endl;
    tree_insert(root,13);
    inorder_tree_walk(root);
    cout<<endl;
    cout<<"the min key is :"<<tree_minimum(root)->key<<endl;
    cout<<"the max key is :"<<tree_maximum(root)->key<<endl;
    cout<<"the 9's successor is :"<<tree_successor(tree_search(root,9))->key<<endl;
    cout<<"delete key =18 :"<<endl;
    tree_delete(tree_search(root,18));
    inorder_tree_walk(root);
    cout<<endl;
    return 0;
}

二叉搜索树：

　　1.二叉搜索树是以一颗二叉树来组织的，可以用链表数据结构来实现表示，每个节点表示一个对象，每个节点包含的信息由其key值及其各方向的指向。

　　2.对其遍历可用前中后序遍历，这里用的是中序遍历方法

　　3.二叉搜索树的搜索方法：待查找的元素的键值比当前结点先就到当前结点的左树种去寻找，比当前节点大就到当前节点的右树中去寻找，否则就找到或者到叶子结点也没找到就返回null

　　4.查找一棵树的最小元素和最大元素：最小元素救是以该节点为根节点的树的最左边的叶子节点，而最大元素就是以该节点为根节点的最右边的叶子结点

　　5.查找按照中序遍历方法中一个节点的前驱和后继节点：

　　　　a.前驱节点：情况一，该节点的左子树非空，则该节点的前驱节点就是该右子树中最大元素；情况二，该节点的左子树为空，那么该节点的后继结点就是沿这这个节点的父节点往上找，并且同时父节点和该节点都上移，直到当前结点是其父节点的右儿子为止，该父节点就是要找的前驱节点

　　　　b.后继节点：情况一，该节点的右子树非空，则该节点的后继节点就是该右子树中最小元素；情况二，该节点的右子树为空，那么该节点的后继结点就是沿这这个节点的父节点往上找，并且同时父节点和该节点都上移，直到当前结点是其父节点的左儿子为止，该父节点就是要找的后继节点

　　　　实际上前驱节点和后继结点的求法刚好相反

　　6.插入节点：先找到给节点的正确位置，然后插入进搜索树中

　　7.删除节点：比较麻烦，情况也比较复杂，因为在删除的过程中还要维护搜索树的性质

　　　　　　a.被删除的节点只有右儿子，用右儿子来填补该节点

　　　　　　b.被删除的节点只有左儿子，用左儿子来填补该节点

　　　　　　c.被删除的节点没有儿子，则直接删除

　　　　　　d.被删除的节点有两个儿子节点，先找到该节点的后继节点。情况一，如果该后继结点就是被删节点的右儿子，直接用该后继节点替换该节点；情况二，如果该后继节点位于被删节点的右子树中但不是被删节点的右儿子，先用该后继节点的右儿子替换该后继节点，再用该后继节点替换被删除的几点。