二叉搜索树

左子树<=根，右子树>=根

根据需求不同，等于的元素可能会被去重也可能会被留下

这样查找一个数就可以只遍历一次，数大选哪个右走，小往左走

查找效率：ologn~on

改进：AVL树，红黑树，B树系列，查找效率：ologn

模拟实现（不多插入相同元素）

---

一．Key结构

1. 节点的定义

代码语言：javascript

AI代码解释

template<class K>
struct bsnode
{
    K _key;
    bsnode* _left;
    bsnode* _right;
    bsnode(const K& key)
        :_key(key)
        ,_left(nullptr)
        ,_right(nullptr)
    {}
};

2. 成员

代码语言：javascript

AI代码解释

typedef bsnode<K> node;
node* _root = nullptr;

代码语言：javascript

AI代码解释

这样，可以不用写构造函数

3. 二叉树的插入

代码语言：javascript

AI代码解释

bool insert(const K& key)
{
    if (_root == nullptr)
    {
        _root = new node(key);
        return 1;
    }
    node* cur = _root;
    node* par = nullptr;
    while (cur != nullptr)
    {
        if (cur->_key < key)
        {
            par = cur;
            cur = cur->_right;
        }
        else if (cur->_key > key)
        {
            par = cur;
            cur = cur->_left;
        }
        else
        {
            return 0;
        }
    }
    node* newnode = new node(key);
    if (par->_key < key)
    {
        par->_right = newnode;
    }
    else
    {
        par->_left = newnode;
    }
    return 1;
}

方案：定一个cur的指针，当根节点小于插入元素，向右走，大于则向左走

如果已经有这个数了，则返回false

如果cur为空，则构造一个节点，和cur最后一次经过的节点连接，返回true

那么，cur已经指向空了，怎么才能知道cur最后一次经过的节点？

在额外弄一个par指针尾随cur即可

4. 树排序

二叉搜索树的中序遍历（左->中->右）的特点：为从小到大的数组

因此，可以中序遍历得到有序数组，叫做树排序

代码语言：javascript

AI代码解释

void inorder()
{
    _inorder(_root);
}

void _inorder(node* root)
{
    if (root == nullptr)return;
    _inorder(root->_left);
    std::cout << root->_key << " ";
    _inorder(root->_right);
}

5. 查找

和插入同理，但是要找的值大于节点向右走，小于往左走

代码语言：javascript

AI代码解释

bool find(const K& _key)
{
    node* cur = _root;
    while (cur)
    {
        if (_key < cur->_key)
        {
            cur = cur->_left;
        }
        else if (_key > cur->_key)
        {
            cur = cur->_right;
        }
        else
        {
            return 1;
        }
    }
    return 0;
}

6. 删除（重要）

删除的集中情况（设删除节点的名称为M）

1. M子节点左右均空：直接删除即可
2. M子节点一个为空：M父节点指向M的一个子节点，再删除M
3. M左右节点都为空： 替换删除法：将M节点用下面的节点交换，再删除下面的数字节点 那么和哪个节点交换既可以做到快速删除又可以做到保持左子树<=根，右子树>=根的性质呢 和左子树的最右节点（最大节点）或右子树的最左节点（最小节点） （1）删除快速：由于两个情况都是最左或最右节点，因此一定满足删除方案1或2，因此删除简单 （2）由于两个情况要么是小的最大，要么是大的最小，因此性质也是满足的 下面用右边最左来演示

代码语言：javascript

AI代码解释

bool erase(const K& _key)
{
    node* par = nullptr;
    node* cur = _root;
    while (cur)
    {
        if (cur->_key < key)
        {
            par = cur;
            cur = cur->_right;
        }
        else if (cur->_key > key)
        {
            par = cur;
            cur = cur->_left;
        }
        else
        {
            if (cur->_left == nullptr)
            {
                if (cur == _root)
                {
                    _root = cur->_right;
                }
                else
                {
                    if (par->_left == cur)
                    {
                        par->_left = cur->_right;
                    }
                    else
                    {
                        par->_right = cur->_right;
                    }
                }
                delete cur;
            }
            else if (cur->_right == nullptr)
            {
                if (cur == _root)
                {
                    _root = cur->_left;
                }
                else
                {
                    if (par->_left == cur)
                    {
                        par->_left = cur->_left;
                    }
                    else
                    {
                        par->_right = cur->_left;
                    }
                }
                delete cur;
            }
            else
            {
                node* rp = cur;
                node* r = cur->_right;
                while (r->_left)
                {
                    rp = r;
                    r = r->_left;
                }
                cur->_key = r->_key;
                if (rp->_left == r)
                {
                    rp->_left = r->_right;
                }
                else
                {
                    rp->_right = r->_right;
                }
                delete r;
            }
            return 1;
        }
    }
    return 0;
}

代码逻辑

1. 先找值为val的节点（找不到返回0），设找到的节点为M
2. 节点M左为空： （1）节点M为根节点：直接将右节点设为根节点（有没有右节点都无所谓） （2）M不为根节点： A.M为左节点：M根节点连接M右节点，删M