平衡二叉搜索树的简单实现

本文涉及：

• BST

BST的实现

#ifndef BST_H
#define BST_H
#include <queue>

template<typename Key,typename Value>
class BST{
public:
    BST(){
        root = NULL;
        count = 0;
    }
    ~BST(){
        destroy(root);
    }
    int size() const{
        return count;
    }
    bool empty(){
        return count == 0;
    }
    //插入节点
    void insert(Key key,Value value){
        root = insert(root,key,value);
        ++count;
    }
    //返回BST中是否包含键为key的节点
    bool contain(Key key){
        return contain(root,key);
    }
    //返回BST中键为key的节点值的指针
    Value* seach(Key key){
        return seach(root,key);
    }
    //前序遍历
    void preOrder(){
        preOrder(root);
    }
    //中序遍历
    void inOrder(){
        inOrder(root);
    }    
    //后序遍历
    void postOrder(){
        postOrder(root);
    }
    //层次遍历
    void levelOrder(){
        std::queue<Node*> q;
        q.push(root);
        while(!q.empty()){
            Node* node = q.front();
            q.pop();//出队
            order(node);
            if(node->left)
                q.push(node->left);
            if(node->right)
                q.push(node->right);
        }
    }
    //返回最小key
    Key minimum(){
        assert(count != 0);
        Node* node = minimum(root);
        return node->key;
    }
    //返回最大key
    Key maximum(){
        assert(count != 0);
        Node* node = maximum(root);
        return node->key;
    }
    //删除key最小节点
    void removeMin(){
        if(root)
            root = removeMin(root);
    }
    //删除key最大的节点
    void removeMax(){
        if(root)
            root = removeMax(root);
    }
    //删除键值为给定key得节点
    void remove(const Key& key){
        if(root)
            root = remove(root,key);
    }

private:
    //私有的Node节点
    struct Node{
        Key key;//键
        Value value;//值
        Node* left;//左孩子
        Node* right;//右孩子
        Node(Key key,Value value){//构造函数
            this->key = key;
            this->value = value;
            this->left = this->right = NULL;
        }
        Node(Node* node){
            key = node->key;
            value = node->value;
            left = node->left;
            right = node->right;
        }
    };
    Node* root;//根节点
    int count;//计数

    //在根为node的树中插入节点
    Node* insert(Node* node,Key key,Value value){//返回插入节点子树根
        if(node == NULL)//递归基
            return new Node(key,value);
        if(key == node->key)//命中,更新
            node->value = value;
        else if(key < node->key)//转入左子树
            node->left = insert(node->left,key,value);
        else//转入右子树
            node->right = insert(node->right,key,value);

        return node;
    }
    //在根为node的BST中查找是否包含键为key的节点
    bool contain(Node* node,Key key){
        if(node == NULL)//递归基
            return false;
        if(node->key == key)//命中
            return true;
        else return (key < node->key) ? contain(node->left,key) : contain(node->right,key);
    }
    //返回根为node的BST中键为key的节点值的指针
    Value* seach(Node* node,Key key){
        if(node == NULL)//递归基
            return NULL;
        if(key == node->key)//命中
            return &(node->value);
        else return (key < node->key) ? seach(node->left,key) : seach(node->right,key);
    }
    //回收内存，
    void destroy(Node* node){
        //后序遍历模式
        if(node){
            destroy(node->left);
            destroy(node->right);
            delete node;
            count--;
        }
    }
    //模拟遍历节点
    void order(Node* node){
        std::cout << "[" << node->key << " " << node->value << "]" << std::endl;
    }
    //前序遍历
    void preOrder(Node* node){
        if(node){//根左右
            order(node);
            preOrder(node->left);
            preOrder(node->right);
        }
    }
    //中序遍历
    void inOrder(Node* node){
        if(node){//左根右
            inOrder(node->left);
            order(node);
            inOrder(node->right);
        }
    }    
    //后序遍历
    void postOrder(Node* node){
        if(node){//左右根
            postOrder(node->left);
            postOrder(node->right);
            order(node);
        }
    }
    // 返回以node为根的二分搜索树的最小键值所在的节点
    Node* minimum(Node* node){
        if(!node->left)//没有左孩子，命中，返回
            return node;
        //否则转向左孩子
        return minimum(node->left);
    }
    // 返回以node为根的二分搜索树的最大键值所在的节点
    Node* maximum(Node* node){
        if(!node->right)//没有右孩子，命中，返回
            return node;
        //否则转向右孩子
        return maximum(node->right);
    }
    //删除以node为根的二分搜索树key最小的节点
    Node* removeMin(Node* node){
        if(!node->left){
            Node* rchild = node->right;
            delete node;
            count--;
            return rchild;
        }else{
            node->left = removeMin(node->left);
            return node;
        }

    }
    //删除以node为根的二分搜索树key最大的节点
    Node* removeMax(Node* node){
        if(!node->right){
            Node* lchild = node->left;
            delete node;
            count--;
            return lchild;
        }else{
            node->right = removeMax(node->right);
            return node;
        }
    }
    //删除以node为根的二分搜索树键值为给定key的节点
    Node* remove(Node* node,const Key& key){
        if(!node)
            return nullptr;
        if(key < node->key){
            node->left = remove(node->left,key);
            return node;
        }
        else if(key > node->key){
            node->right = remove(node->right,key);
            return node;
        }
        else{
            if(!node->left){
                Node* rchild = node->right;
                delete node;
                --count;
                return rchild;
            }
            if(!node->right){
                Node* lchild = node->left;
                delete node;
                --count;
                return lchild;
            }
            //左右孩子都存在的情况
            
            Node* seccessor = new Node(minimum(node->right)); //当前节点直接后继
            count++;//保证计数正确

            seccessor->right = removeMin(node->right);
            seccessor->left = node->left;

            delete node;
            count--;
            return seccessor;
        }
    }

};

#endif

第一次自己比较完整的实现了BST，记录下来，方便自己复习。