算法导论笔记（5）二叉搜索树

二叉查找树简介

二叉查找树(Binary Search Tree)，又被称为二叉搜索树。
它是特殊的二叉树：对于二叉树，假设x为二叉树中的任意一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。那么，这棵树就是二叉查找树。

集合操作

search搜索

有迭代版和递归版。
思想都是向下查找合适的值，有值会返回节点，无合适值会一直向下走直到返回null

/*
 * (递归实现)查找"二叉树x"中键值为key的节点
 */
BNode* search(BSTree x, Type key)
{
    if (x==NULL || x->key==key)
        return x;
    if (key < x->key)
        return bstree_search(x->left, key);
    else
        return bstree_search(x->right, key);
}

/*
 * (非递归实现)查找"二叉树x"中键值为key的节点
 */
    BNode* search(DataType key) const{
        BNode *p=root;
        while(p!=NULL&&p->key!=key){
            if (key<p->key)
            {
                p=p->left;
            }else{
                p=p->right;
            }
        }
        if(p!=NULL)
            printf("search %d\n",p->key);
        return p;
    }

mininum寻找子树的最小key节点

最小节点是最左子节点

maxnum子树最大key节点

最大节点是最右子节点

predecessor前序寻找比此节点小的最大节点

两种情况，
正常来说是找次节点的左子树最大节点，如果没有左子树，向上寻找根

    BNode* Predecessor(BNode *T){
        BNode *x=T;
        if (x->left!=NULL)
        {
            return maxmun(x->left);
        }
        BNode *y=x->p;
        while(y!=NULL&&x==y->left){
            x=y;
            y=y->p;
        }
        return y;
    };

succesor后序

同样两种情况，右子树的最小值，或者没有右子树的情况下，向上找根

    BNode* Successor(BNode *T){
        BNode *x=T;
        if(x->right!=NULL){
            return minmun(x->right);
        }
        BNode *y=T->p;
        while(y!=NULL&&y->right==x){
            x=y;
            y=y->p;
        }
        return y;
    }

insert插入

向下插入，
两种情况，有根和无根。注意对root的操作

delete删除

删除节点x
1。无左子树，右子树接上。
2。无右子树，左子树接上。
3。左右都有，寻找右子树最小值y
3.1如果最小值为直接右子树，直接替换接上
3.2不是直接右子树，把y右子树替换y，y再替换x

c++实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef int DataType;
struct BNode
{
    DataType key;
    BNode *p,*left,*right;
};
class Btree
{
private:
    BNode *root;
public:
    Btree(){
        root=NULL;
    };
    ~Btree(){
        destoryNode(root);
        root=NULL;
    };
    void Insert(DataType key){
        BNode *z=new BNode;
        BNode *y=NULL;
        BNode *x=root;
        z->key=key;
        z->p=z->right=z->left=NULL;
        //初始化x，y和z
        while(x!=NULL){
            y=x;
            if (x->key>key)
            {
                x=x->left;
            }else{
                x=x->right;
            }
        }//x指向root，向下查找
        z->p=y;
        if (y==NULL)
        {
            root=z;
        }else if(y->key>key){
            y->left=z;
        }else{
            y->right=z;
        }//建立z的双亲节点y与z的联系
        printf("Node %d",z->key);
        if(y!=NULL){
            printf("p %d\n",y->key);
        }else{
            printf("\n");
        }
    };
    BNode* search(DataType key) const{
        BNode *p=root;
        while(p!=NULL&&p->key!=key){
            if (key<p->key)
            {
                p=p->left;
            }else{
                p=p->right;
            }
        }
        if(p!=NULL)
            printf("search %d\n",p->key);
        return p;
    }
    BNode* minmun(BNode *T){
        BNode *p=T;
        while(p->left!=NULL){
            p=p->left;
        }
        printf("%d‘s minmun %d\n",T->key,p->key);
        return p;
    }
    BNode* maxmun(BNode *T){
        BNode *p=T;
        while(p->right!=NULL){
            p=p->right;
        }
        printf("%d‘s maxmun %d\n",T->key,p->key);
        return p;
    }
    BNode* Successor(BNode *T){
        BNode *x=T;
        if(x->right!=NULL){
            return minmun(x->right);
        }
        BNode *y=T->p;
        while(y!=NULL&&y->right==x){
            x=y;
            y=y->p;
        }
        return y;
    }
    BNode* Predecessor(BNode *T){
        BNode *x=T;
        if (x->left!=NULL)
        {
            return maxmun(x->left);
        }
        BNode *y=x->p;
        while(y!=NULL&&x==y->left){
            x=y;
            y=y->p;
        }
        return y;
    };
    void Translate(BNode *u,BNode *v){
        if (u->p==NULL)
        {
            root=v;
        }else if(u->p->left==u){
            u->p->left=v;
        }else{
            u->p->right=v;
        }
        if (v!=NULL)
        {
            v->p=u->p;
        }
    }
    int TreeDelete(BNode *z){
        if (z->left==NULL)
        {
            printf("Translate z z->right\n");
            Translate(z,z->right);
            delete z;
        }else if(z->right==NULL){
            printf("Translate z z->left\n");
            Translate(z,z->left);
            delete z;
        }else{
            BNode *y=minmun(z->right);
            if (y->p!=z)
            {
                Translate(y,y->right);
                y->right=z->right;
                y->right->p=y;
                printf("Translate y y->right\n");
            }
            Translate(z,y);
            y->left=z->left;
            y->left->p=y;
            printf("Translate z y\n");
        }
    }
    void destoryNode(BNode *T){
        if (T->left!=NULL)
        {
            destoryNode(T->left);
        }
        if (T->right!=NULL)
        {
            destoryNode(T->right);
        }
        printf("destory %d\n",T->key);
        BNode *p=T;
        delete p;
    };
};
int main(int argc, char const *argv[])
{
    Btree *T=new Btree();
    T->Insert(3);
    T->Insert(7);
    T->Insert(1);
    T->Insert(12);
    T->Insert(8);
    BNode *t=T->search(12);
    BNode *t1=T->search(3);
    T->maxmun(t);
    T->minmun(t);
    T->TreeDelete(t);
    T->TreeDelete(t1);
    delete T;
    return 0;
}