二叉搜索树(C++) – 左小右大

树的概念应该比较直观，一个根延伸出很多的分支，每个分支又延伸出多个分支，以此类推，直到没有分支的为叶，以此枝繁叶茂；二叉树则是一棵有性格的树，规定了一个节点的分支不能超过2个；二叉搜索树则是在这个基础上再规定了，一个节点的左子节点的值必须小于该节点的值，右子节点的值必须大于该节点的值
这里二叉搜索树是基于递归实现的，递归实现起来要简便一些，思路是从上至下的，只需确定好递归条件和递归结束条件即可；BST类中主要实现了二叉搜索树的增删改查；
需要注意的是，二叉搜索树中的每一个节点都是一个对象(这里是struct Node)，其中存放了键值和值，左节点指针和右节点指针，二叉搜索树中的排序比较是以各节点的键值进行比较的；在public中的方法供外部调用，绝大部分方法功能的实现在private中的同名方法加了__，如插入方法public供外部调用的是insert方法，实际实现在private中的__insert方法~~

二叉搜索树 – 递归玩法

template <typename KeyType, typename ValueType>
// 二叉搜索树
class BST {

private:
    // 二叉树中的节点
    struct Node {
        KeyType key;
        ValueType value;
        Node* left;
        Node* right;

        Node(KeyType key, ValueType value) {
            this->key = key;
            this->value = value;
            this->left = this->right = NULL;
        }
    };

    // 根节点
    Node* root;
    // 节点数
    int count;

    // 内部实现，插入节点，插入完成则返回根节点
    // 插入的bst就是当(子)树的根节点，因为树可以通过根节点到达任意节点，所以用根节点描述为bst
    Node* __insert(Node* bst, KeyType key, ValueType value) {
        // 找到节点需要插入的位置了，插入
        if(bst == NULL) {
            bst = new Node(key, value);
            count++;
            return bst;
        }

        // 键值与当前键值相等，则更新值，也就是说这里没有相同键值的不同元素存在
        if(key == bst->key) {
            bst->value = value;
            // 键值比当前节点键值小，则左遍历
        } else if(key < bst->key) {
            bst->left = __insert(bst->left,key,value);
            // 键值比当前节点键值大，则右遍历
        } else {
            bst->right = __insert(bst->right,key,value);
        }

        // 返回执行完插入操作的搜索二叉树的根节点
        return bst;
    }
    // 内部实现，二叉搜索树是否包含键值为key的节点
    bool __contain(Node* bst, KeyType key) {
        // 递归结束条件，节点为NULL，说明找不到key
        if(bst == NULL) {
            return false;
        }

        // 节点键值与待找键值的关系进行递归查找
        if(key == bst->key) {
            return true;
        } else if(key < bst->key) {
            return __contain(bst->left,key);
        } else {
            return __contain(bst->right,key);
        }
    }

    // 内部实现，二叉搜索树是否包含键值为key的节点，可能为NULl，用指针
    ValueType* __search(Node* bst, KeyType key) {
        // 递归结束条件，节点为NULL，说明找不到key
        if(bst == NULL) {
            return NULL;
        }

        // 节点键值与待找键值的关系进行递归查找
        if(key == bst->key) {
            return &(bst->value);
        } else if(key < bst->key) {
            return __search(bst->left,key);
        } else {
            return __search(bst->right,key);
        }
    }
    // 获取最左节点，也就是最小值所在的节点，给删除节点用
    Node* __getLeftmost(Node* bst) {
        if(bst == NULL)
            return NULL;
        Node* node = bst;
        while(node->left != NULL)
            node = node->left;

        return node;
    }
    // 获取最右节点，也就是最大值所在的节点，给删除节点用
    Node* __getRightmost(Node* bst) {
        if(bst == NULL)
            return NULL;
        Node* node = bst;
        while(node->right != NULL)
            node = node->right;

        return node;
    }
    // 内部实现，删除节点
    // 删除节点有2种情况会出现，找到要删除的节点和没找到要删除的节点
    // 找到要删除的节点，删除后会出现4种情况，被删除的节点左右都有子节点，被删除的节点只有左节点，删除的节点只有右节点，被删除的节点就是叶节点
    // 根节点代表了二叉搜索树BST，所以这里根节点用bst作为参数
    Node* __remove(Node* bst, KeyType key) {
        // 根节点为NULL，说明二叉搜索树已经遍历结束，没有找到key，不需要进行删除，则返回NULL
        if(bst == NULL)
            return NULL;

        // 寻找要删除的节点
        // bst是根节点，当删除的节点是左节点或右节点时根节点不变，所以还是返回bst，但在传递时因为返回的都是根节点，
        // 所以要分别对应bst-left和bst-right
        if(key < bst->key) {
            bst->left = __remove(bst->left, key);
            return bst;
        } else if(key > bst->key) {
            bst->right = __remove(bst->right, key);
            return bst;
            // 找到要删除的节点，进行删除和二叉搜索树维护，维护时要分情况判断
        } else {
            // 待删除节点没有左右子节点时，直接删除节点
            if(bst->left == NULL && bst->right == NULL) {
                // 释放了空间之后，注意还需要将该节点置为NULL，因为delete后虽然空间释放了，但指针还在，防止乱指所以置NULL
                delete bst;
                bst = NULL;
                count--;
            } else {
                Node* temp;
                // 待删除节点有右左右子节点时，根据二叉搜索树的性质可以用左子树的最右节点或右子树的最左节点替换掉被删除的节点，
                // 这样在节点被删除后，二叉搜索树的性质得以维护，因为这两个节点分别作为左子树的最大值和右子树的最小值，
                // 结合左子树节点均小于父节点，右子树节点军大于父节点的特性，就能确定这两个节点都必定大于所有左子树的节点并小于所有右子树的节点；
                // 这里选取右子树的最左节点作为替换节点
                if(bst->left != NULL && bst->right != NULL) {
                    temp = __getLeftmost(bst->right);
                    // 将被删除节点的键值和值替换成右子树的最左节点的键值和值
                    bst->key = temp->key;
                    bst->value = temp->value;
                    // 待删除节点只有左子树时，直接将左子树的第一个节点提上来，删掉待删除的节点
                } else if(bst->left != NULL) {
                    temp = bst;
                    bst = bst->left;
                    // 待删除节点只有右子树时，直接将右子树的第一个节点提上来，删掉待删除的节点
                    //  if(bst->right != NULL)
                } else {
                    temp = bst;
                    bst = bst->right;
                }
                // 减少计数和删除节点都在这进行，节省代码
                count--;
                delete temp;
            }
        }

        return bst;
    }

public:
    // 构造函数
    BST() {
        root = NULL;
        count = 0;
    }

    // 析构函数，用到了后序遍历删除二叉搜索树
    ~BST() {
        __freeUp(root);
    }

    // 二叉搜索树元素个数
    int size() {

        return count;
    }

    // 是否为空树
    bool isEmpty() {

        return count == 0;
    }

    // 外部调用，插入节点
    void insert(KeyType key, ValueType value) {

        // 设置二叉搜索树根节点，主要作用在插入唯一一个节点时获取根节点，因为这个二叉搜索树插入第一个节点后，根节点就不会动了
        root = __insert(root,key,value);
    }
    // 外部调用，二叉搜索树是否包含键值为key的节点
    bool contain(KeyType key) {

        return __contain(root,key);
    }
    // 外部调用，获取二叉搜索树中对应键值节点的值，可能为NULl，用指针
    ValueType* search(KeyType key) {

        return __search(root,key);
    }
    // 获取最大键值，最大键值在二叉搜索树最右边
    KeyType getMaxKey() {
        assert(count > 0);
        Node* node = root;
        while(node->right != NULL)
            node = node->right;

        return node->key;
    }
    // 获取最小键值，最小键值在二叉搜索树最左边
    KeyType getMinKey() {
        assert(count > 0);
        Node* node = root;
        while(node->left != NULL)
            node = node->left;

        return node->key;
    }
    // 外部调用，删除节点，因为delete是内部关键字，所以方法名不能用delete，改用remove
    void remove(KeyType key) {
        // 删除后可能会改变根节点，所以要重新获取下根节点
        root = __remove(root,key);
    }

};

二叉搜索树 – 性能

二叉搜索树虽然具有左小右大的特性，但不一定是完全二叉树，甚至在最尴尬的情况下会变成一棵斜二叉树，也就是一个所有子节点都是左节点或都是右节点，说穿了就成了一个链表了；当键值从小到大插入时就会变成一棵右斜二叉树了，从大倒下插入则会变成一棵左斜二叉树，所以顺序插入会使二叉搜索树的性能退化成链表；所以一般情况下，也就是随机插入键值时，BST通常是优于二分查找法的，但是如果退化成链表，那就是一个O(n)级别的选手了，尴尬程度可想而知，所以在二叉搜索树后又催生了基于平衡的平衡二叉搜索树，如AVL和红黑树，下回分解~~