7-二叉搜索树

二叉搜索树（Binary Search Tree）

是应用非常广泛的一种二叉树，简称BST，又被称为二叉查找树、二叉排序树

特点如下：
任意一个节点的值都大于其左子树所有节点的值
任意一个节点的值都小于其右子树所有节点的值
它的左右子树也都是一棵二叉搜索树
二叉搜索树存储的元素必须具备可比较性，不允许为null

template<class E>
class BinarySearchTree {

private:
    template<class E1>
    //节点类
    class TreeNode {
    public:
        explicit TreeNode(E ele, TreeNode* par = nullptr):val(ele),parent(par) {

        }
        E val;
        TreeNode<E1> *left{nullptr};
        TreeNode<E1> *right{nullptr};
        TreeNode<E1> *parent{nullptr};

    };
    //成员信息
    TreeNode<E> *m_root{nullptr};
    int m_size{0};
    std::function<bool (const E&, const E&)> m_comparator;

public:
    //默认构造，调取 e1>e2 即元素需要可比较或者重载>运算符
    BinarySearchTree():m_comparator([](const E& e1, const E& e2) { return e1 > e2; }) {

    }
    //传入比较器的构造
    explicit BinarySearchTree(std::function<bool (const E&, const E&)> comp): m_comparator(comp) {

    }

    ~BinarySearchTree() {
        delete m_root;
    }
    //添加元素
    void add(E ele) {
        if (m_root == nullptr) {
            m_root = new TreeNode<E>(ele);
            m_size++;

        } else {
            //1-找到父节点 以及属于左/右节点
            TreeNode<E> *note = m_root;
            int com = 0;
            while (true) {
                com = compare(ele, note->val);
                if (com > 0) {
                    TreeNode<E> *right = note->right;
                    if (right == nullptr) {
                        break;
                    } else {
                        note = right;
                    }
                } else if (com < 0) {
                    TreeNode<E> *left = note->left;
                    if (left == nullptr) {
                        break;
                    } else {
                        note = left;
                    }
                } else {//相同则不处理
                    return;
                }
            }
            if (com > 0) {
                note->right = new TreeNode<E>(ele, note);
            } else {
                note->left = new TreeNode<E>(ele, note);
            }
            m_size++;
        }
    }
    int size() {
        return m_size;
    }
    bool isEmpty() {
        return m_size == 0;
    }
    int compare(E e1, E e2) {
        if (m_comparator(e1, e2)) {
            return 1;
        } else if (m_comparator(e2, e1)) {
            return -1;
        }
        return 0;
    }

public:
    void toString() {
        innerToString(m_root, "");
    }
private:
    void innerToString(TreeNode<E> *ele, std::string prefix) {
        if (ele == nullptr) return;

        std::cout << prefix << " " << ele->val << std::endl;
        innerToString(ele->left, prefix+"[L]");
        innerToString(ele->right, prefix+"[R]");
    }
}

二叉树的遍历：

前序遍历：树状结构展示
中序遍历：二叉搜索树的中序遍历按升序或降序处理节点
后序遍历：适用一些先子后父的操作
层序遍历：计算二叉树的高度，判断一棵树是否为完全二叉树

#include <queue>
//用于遍历时，迭代每个元素
template<typename E>
class Visitor {
public:
    bool stop = false;
    std::function<bool(E)> visit;
};

template<class E>
class BinarySearchTree {
    //前序遍历
public:
    void preorder(Visitor<E> &vi) {
        innerPreorder(m_root, vi);
    }
private:
    void innerPreorder(TreeNode<E> *ele, Visitor<E> & vi) {
        if (ele == nullptr || vi.stop) return;

        vi.stop = vi.visit(ele->val);
        innerPreorder(ele->left, vi);
        innerPreorder(ele->right, vi);
    }

    //中序遍历
public:
    void inorder(Visitor<E> &vi) {
        innerInorder(m_root, vi);
    }
private:
    void innerInorder(TreeNode<E> *ele, Visitor<E> &vi) {
        if (ele == nullptr || vi.stop) return;

        innerInorder(ele->left, vi);
        if (vi.stop) return;
        vi.stop = vi.visit(ele->val);
        innerInorder(ele->right, vi);
    }

    //后序遍历
public:
    void postorder(Visitor<E>& vi) {
        innerPostorder(m_root, vi);
    }
private:
    void innerPostorder(TreeNode<E> *ele, Visitor<E>& vi) {
        if (ele == nullptr || vi.stop) {
            return;
        }
        innerPostorder(ele->left, vi);
        innerPostorder(ele->right, vi);
        if (vi.stop) return;
        vi.stop = vi.visit(ele->val);
    }

    //层序遍历
public:
    void levelorder(Visitor<E>& vi) {
        innerLevelorder(m_root, vi);
    }
private:
    void innerLevelorder(TreeNode<E> *ele, Visitor<E>& vi) {
        if (ele == nullptr) {
            return;
        }
        std::queue<TreeNode<E> *> queue;
        queue.push(ele);
        while (!queue.empty()) {
            TreeNode<E> *e = queue.front();
            queue.pop();
            vi.stop = vi.visit(e->val);
            if (vi.stop) {
                break;
            }
            if (e->left != nullptr) {
                queue.push(e->left);
            }
            if (e->right != nullptr) {
                queue.push(e->right);
            }
        }
    }
};

计算二叉树的高度

    //获取树的高度
public:
    int height() {
//        return heightWithRecursion(m_root);
        return heightWithItreation2(m_root);
    }
private:
    //使用递归的方式
    int heightWithRecursion(TreeNode<E> *ele) {
        if (ele == nullptr) return 0;
        return 1 + max(heightWithRoot(ele->left), heightWithRoot(ele->right));
    }
    //使用迭代的方式1
    int heightWithItreation(TreeNode<E> *ele) {
        if (ele == nullptr) return 0;
        std::queue<TreeNode<E>*> queue;
        queue.push(ele);
        int h = 0;
        int c = 1;
        while (!queue.empty()) {
            int temp_c = c;
            c = 0;
            for (int i = 0; i < temp_c; i++) {
                TreeNode<E> *e = queue.front();
                queue.pop();
                if (e->left != nullptr) {
                    queue.push(e->left);
                    c++;
                }
                if (e->right != nullptr) {
                    queue.push(e->right);
                    c++;
                }
            }
            h++;
        }
        return h;
    }
    //使用迭代的方式2
    int heightWithItreation2(TreeNode<E> *ele) {
        if (ele == nullptr) return 0;
        std::queue<TreeNode<E>*> queue;
        queue.push(ele);
        int h = 0;
        int ls = 1;
        while (!queue.empty()) {
            TreeNode<E> *e = queue.front();
            queue.pop();
            ls--;
            if (e->left != nullptr) {
                queue.push(e->left);
            }
            if (e->right != nullptr) {
                queue.push(e->right);
            }
            if (ls == 0) {
                ls = queue.size();
                h++;
            }

        }
        return h;
    }

判断是否为完全二叉树

    //判断树是否完全二叉树
public:
    bool isComplete() {
        if (m_root == nullptr) return false;

        std::queue<TreeNode<E>*> queue;
        queue.push(m_root);
        bool needLeafage = false;//是否必须为叶子节点
        while (!queue.empty()) {
            TreeNode<E> *e = queue.front();
            queue.pop();

            if (needLeafage) {
              if (e->left != nullptr || e->right != nullptr) {
                return false;
              }
            }

            if (e->left != nullptr && e->right != nullptr) {
                queue.push(e->left);
                queue.push(e->right);

            } else if (e->left == nullptr && e->right != nullptr) {
                return false;//

            } else if (e->left == nullptr && e->right == nullptr) {
                needLeafage = true;//标记后续都需为叶子

            } else if (e->left != nullptr && e->right == nullptr) {
                needLeafage = true;//标记后续都需为叶子
                queue.push(e->left);
            }
        }
        return true;
    }

根据遍历结构重构二叉树

前序遍历+中序遍历
后序遍历+中序遍历
——>可保证重构出唯一的一棵二叉树

前序遍历+后序遍历
若它是一棵真二叉树，结果唯一
否则结果不唯一

前驱节点

中序遍历时的前一个节点
如果是二叉搜索树，前驱节点就是前一个比它小的节点

    TreeNode<E>* predecessor(TreeNode<E> *ele) {

        if (ele->left == nullptr) {
            //左节点为空，则顺着父节点找，当找到属于父节点的右子树下时，此时的父节点则为前驱节点
            TreeNode<E> *p = ele->parent;
            if (p == nullptr) return p;
            while (p->parent != nullptr && p == p->parent->left) {
                p = p->parent;
            }
            return p->parent;

        } else {
            //左节点不为空情况下，找左子树的最右边那个节点
            TreeNode<E> *l = ele->left;
            while (l->right != nullptr) {
                l = l->right;
            }
            return l;
        }
    }

后继节点

中序遍历时的后一个节点

    TreeNode<E>* successor(TreeNode<E> *ele) {
        if (ele->right != nullptr) {
            TreeNode<E>* r = ele->right;
            while (r->left != nullptr) {
                r = r->left;
            }
            return r;

        } else {
            TreeNode<E>* p = ele->parent;
            if (p == nullptr) return p;
            while (p->parent != nullptr && p == p->parent->right) {
                p = p->parent;
            }
            return p->parent;
        }
    }

删除指定节点

    TreeNode<E>* node(E ele) {
        auto n = m_root;
        while (n != nullptr) {
            int cmp = compare(n->val, ele);
            if (cmp == 0) {
                return n;
            } else if (cmp > 0) {
                n = n->left;
            } else {
                n = n->right;
            }
        }
        return nullptr;
    }

    void remove(E ele) {
        //如果节点度为2，覆盖节点的值为前驱/后继节点， 删除该前驱/后继节点
        //如果节点度为1，让节点的子节点 成为其父节点下的节点
        //如果节点度为0，直接删除该节点
        auto n = node(ele);
        if (n == nullptr) return;

        m_size--;
        if (n->hasTwo()) {
            auto pre = predecessor(n);
            n->val = pre->val;
            if (pre->parent && pre == pre->parent->left) {
                pre->parent->left = nullptr;
            } else if (pre->parent && pre == pre->parent->right) {
                pre->parent->right = nullptr;
            }
            pre->parent = nullptr;

        } else if (n->isLeaf()) {

            if (n->parent == nullptr) {//根节点
                m_root = nullptr;
                return;
            }
            if (n->parent && n == n->parent->left) {
                n->parent->left = nullptr;
            } else { // (n->parent && n == n->parent->right)
                n->parent->right = nullptr;
            }
            n->parent = nullptr;

        } else {
            auto next = n->left != nullptr ? n->left : n->right;
            next->parent = n->parent;

            if (n->parent == nullptr) {//根节点
                m_root = next;
            } else {
                if (n == n->parent->left) {
                    n->parent->left = next;
                } else {//if (n->parent && n == n->parent->right)
                    n->parent->right = next;
                }
                n->parent = nullptr;
            }

        }
    }