【算法】BST的非递归插入，删除，查询

BST

        所谓二叉搜索树（Binary Search Tree，简称 BST）大家应该都不陌生，它是一种特殊的二叉树。对于二叉树上的每一个节点，如果满足左孩子的值 < 父节点的值 < 右孩子的值，把满足上面性质的二叉树就称作BST树，Binary Search/Sort Tree。

        有了BST的这种特性，就可以在二叉树中做类似二分搜索的操作，搜索一个元素的效率很高。

特点：

1. 有序性：对于BST中的每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。
2. 递归性：BST的每个子树也是BST，即子树中的节点仍然满足有序性和递归性。
3. 无重复值：BST中不允许存在相同值的节点。

        由于BST的有序性，它具有快速的查找、插入和删除操作的特点，因此被广泛应用于数据结构和算法中。

BSTree的数据定义：

// BSTREE代码实现
template <typename T, typename Compare = less<T>>
class BSTree
{
private:
    /* data */
    // 节点定义
    struct Node
    {
        Node(T data = T())
            : data_(data), left_(nullptr), right_(nullptr)
        {
        }
        T data_;
        Node *left_;
        Node *right_;
    };

    Node *root_;

public:
    BSTree()
        : root_(nullptr)
    {
    }
    ~BSTree()
    {
    }
};

        使用类模板，使它可以存入各种不同数据类型，而且c++中提供Compare函数对象，可以根据用户需要，来比较不同类型的数据。

BST树的非递归插入

root => 根节点 nullptr

BST如果为空，root => 新生成的节点来存放插入的数据

BST如果不为空，从根节点开始比较，找到合适的位置，生成新的节点，并把节点的地址写入父节点相应的地址域当中。

BSTree非递归插入操作：

	void n_insert(const T &val)
    {
        // 树为空，生成根节点
        if (root_ == nullptr)
        {
            root_ = new Node(val);
            return;
        }

        // 搜索合适位置，记录父节点位置
        Node *parent = nullptr;
        Node *cur = root_;
        while (cur != nullptr)
        {
            if (cur->data_ > val)
            {
                parent = cur;
                cur = cur->left_;
            }
            else if (cur->data_ < val)
            {
                parent = cur;
                cur = cur->right_;
            }
            else
            {
                // 不插入元素相同的值
                return;
            }
        }
        // 把新节点插入到parent节点的孩子上
        if(val < parent->data_)
        {
            parent->left_ = new Node(val);
        }
        else
        {
            parent->right_ = new Node(val);
        }
    }

BST树的非递归删除

1.没有孩子的节点，父节点地址域nullptr

2.有一个孩子，把孩子写入父节点地址域

3.删除的节点有两个孩子，找待删除节点的前驱节点（或者后继节点），用前驱或者后继节点的值把待删除节点的值覆盖掉，然后直接删除前驱或者后继节点就可以了。

前驱节点：当前节点左子树中值最大的节点。

后继节点：当前节点右子树中值最小的节点。

// 非递归的删除操作
    void n_remove(const T &val)
    {
        if(root_ == nullptr)
        {
            return ;
        }
        Node *parent = nullptr;
        Node *cur = root_;
        while(cur != nullptr)
        {
            if(cur->data_ == val)
            {
                break;
            }
            else if(!Compare(cur->data_, val))
            {
                parent = cur;
                cur = cur->left_;
            }
            else
            {
                parent = cur;
                cur = cur->right_;
            }
        }
        if(cur == nullptr)
        {
            return; // 没找到待删除节点
        }
        if(cur->left_ != nullptr && cur->right_ != nullptr)
        {
            parent = cur;
            Node *pre = cur->left_;
            while(pre->right_ != nullptr)
            {
                parent = pre;
                pre = pre->right_;
            }
            cur->data_ = pre->data_;
            cur = pre; // 让cur指向前驱节点，转化成情况1，2
        }
        // cur指向删除节点，parent指向其父节点，统一处理情况1，2
        Node *child = cur->left_;
        if(child == nullptr)
        {
            child = cur->right_;
        }
        if(parent == nullptr)
        {
            root_ = child;
        }
        else
        {
            if (parent->left_ == cur)
            {
                parent->left_ = child;
            }
            else
            {
                parent->right_ = child;
            }
        }
        delete cur;
    }

BST树的非递归查询

// 非递归查询操作
    bool n_query(const T& val)
    {
        Node *cur = root_;
        while(cur != nullptr)
        {
            if(cur->data_ == val)
            {
                return ture;
            }
            else if(Compare(cur->data_, val))
            {
                cur = cur->right_;
            }
            else
            {
                cur = cur->left_;
            }
        }
        return false;
    }