二叉搜索树模拟实现

二叉搜索树是一种特殊的二叉树，查找、插入时间复杂度较低O(log n)，它有这几个性质：

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值
• 若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值
• 任意节点的左、右子树也分别为二叉搜索树
• 空树也是二叉搜索树

查找：
由于它的这些性质，所以在查找的时候从根节点开始查找
在二叉搜索树b中查找x的过程为：
若b是空树，则搜索失败
若x等于b节点数据域的值，则查找成功
若x小于b节点数据域的值，则搜索左子树
若x大于b节点数据域的值，则搜索右子树
由于搜索的长度为树的高度，所以在一个平衡的情况下搜索效率为O(log n)

插入：
向一个二叉搜索树b中插入一个节点s的算法，过程为：
若树是空树，则将s所指节点作为根节点插入
若s->data等于b的根节点的数据域之值，则返回
若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中
若s->data大于b的根节点的数据域之值，则把s所指节点插入到右子树中
同样插入效率为O(log n)

删除：

1. 若要删除的结点无孩子结点，直接删除即可
2. 若要删除的结点只有左孩子结点，使被删除节点的双亲结点指向被删除节点的左孩子结点
3. 若要删除的结点只有右孩子结点，使被删除节点的双亲结点指向被删除结点的右孩子结点
4. 若要删除的结点有左、右孩子结点，在它的右子树中寻找关键码最小或在左子树寻找关键码最大的节点，用它的值填补到被删除节点中，效率O(log n)

但这这样存在一些问题，当二叉搜索树退化为左右单支时，它的平均比较次数为n/2，这样二叉搜索树性能就失去了，所以我们可以通过别的办法来改进，如AVL树、红黑树…

// BSTree.hpp

#include <iostream>

template <class T>
struct BSTNode {
    BSTNode(const T& data = T())
        : _left(nullptr)
        , _right(nullptr)
        , _data(data) {}

    BSTNode<T>* _left;
    BSTNode<T>* _right;
    T _data;
};

template <class T>
class BSTree {
public:
    typedef BSTNode<T> Node;
    typedef Node* pNode;

    BSTree()
        : _root(nullptr) {}

    // 深拷贝
    BSTree(const BSTree<T>& bst) {
        _root = Copy(bst._root);
    }

    BSTree<T>& operator=(const BSTree<T>& bst) {
        if (this != &bst) {
            if (_root) {
                destroy(_root);
            }
            _root = Copy(bst._root);
        }
        return *this;
    }

    ~BSTree() {
        destroy(_root);
    }

    pNode Find(const T& data) {
        if (_root == nullptr) {
            return nullptr;
        }
        pNode cur = _root;
        while (cur) {
            if (cur->_data == data) {
                return cur;
            } else if (cur->_data > data) {
                cur = cur->_left;
            } else {
                cur = cur->_right;
            }
        }
        return nullptr;
    }

    bool Insert(const T& data) {
        if (_root == nullptr) {
            _root = new Node(data);
            return true;
        }
        pNode cur = _root;
        pNode parent = nullptr;
        while (cur) {
            parent = cur;
            if (cur->_data == data) {
                return false;
            } else if (cur->_data > data) {
                cur = cur->_left;
            } else {
                cur = cur->_right;
            }
        }
        // 插入新的节点
        cur = new Node(data);
        // 判断插入的位置
        if (parent->_data > data) {
            parent->_left = cur;
        } else {
            parent->_right = cur;
        }
        return true;
    }

    bool Erase(const T& data) {
        if (_root == nullptr) {
            return false;
        }
        pNode cur = _root;
        pNode parent = nullptr;
        while (cur) {
            if (cur->_data == data) {
                // 找到了要删除节点
                if (cur->_right == nullptr) {
                    // 要删除的节点右为空
                    if (cur != _root) {
                        if (parent->_left == cur) {
                            parent->_left = cur->_left;
                        } else {
                            parent->_right = cur->_left;
                        }
                    } else {
                        _root = cur->_left;
                    }
                    delete cur;
                    cur = nullptr;
                } else if (cur->_left == nullptr) {
                    // 要删除的节点左为空
                    if (cur != _root) {
                        if (parent->_left == cur) {
                            parent->_left = cur->_right;
                        } else {
                            parent->_right = cur->_right;
                        }
                    } else {
                        _root = cur->_right;
                    }
                    delete cur;
                    cur = nullptr;
                } else {
                    // 要删除的节点左右都不为空
                    // 寻找左子树最大节点，或右子树最小节点替换
                    pNode leftMax = cur->_left;
                    parent = cur;
                    // 寻找最右节点
                    while (leftMax->_right) {
                        parent = leftMax;
                        leftMax = leftMax->_right;
                    }
                    // 交换值 cur<-->左子树最右节点
                    cur->_data = leftMax->_data;
                    // 删除最右节点
                    if (parent->_left == leftMax) {
                        // 左子树的最右节点为左子树的根
                        parent->_left = leftMax->_left;
                    } else {
                        // 左子树的最右节点不为左子树的根
                        parent->_right = leftMax->_left;
                    }
                    delete leftMax;
                    leftMax = nullptr;
                }
                return true;
            }
            parent = cur;
            if (cur->_data > data) {
                cur = cur->_left;
            } else {
                cur = cur->_right;
            }
        }
        return false;
    }

    void Inorder() {
        _Inorder(_root);
        std::cout << std::endl;
    }
private:
    pNode Copy(pNode root) {
        if (root == nullptr) {
            return root;
        }
        pNode newRoot = new Node(root->_data);
        newRoot->_left = Copy(root->_left);
        newRoot->_right = Copy(root->_right);
        return newRoot;
    }

    void destroy(pNode root) {
        if (root != nullptr) {
            destroy(root->_left);
            destroy(root->_right);
            delete root;
            root = nullptr;
        }
    }

    void _Inorder(pNode root) {
        if (root != nullptr) {
            _Inorder(root->_left);
            std::cout << root->_data << " ";
            _Inorder(root->_right);
        }
    }

    pNode _root;
};