C++ 详解数据结构中的搜索二叉树

定义

搜索二叉树，也称有序二叉树，排序二叉树，是指一棵空树或者具有下列性质的二叉树：

1、若任意节点的左子树不空，则左子树上的所有节点的值均小于它的根节点的值

2、若任意节点的右子树不空，则右子树上的所有节点的值均大于它的根节点的值

3、任意节点的左右子树也称为二叉查找树。

4、没有键值相等的节点。

5、搜索二叉树中序遍历为有序数组。

结构代码实现

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

查找某个元素

在搜索二叉树b中查找x的过程

若树是一个空树，则搜索失败，否则：
若x等于b的根节点的键值，则查找成功；否则：
若x小于b的根节点的键值，则搜索左子树；否则：
若x大于b的根节点的键值，则搜索右子树。

非递归实现

typrdef BSTreeNode<K> Node;
?
Node* find(const K& key)
{
    Node*cur =_root;
    while(cur)
    {
        if(cur->_key<key)
            cur=cur->right;
        else if(cur->_key>key)
            cur=cur->left;
        else
            return cur;
    }
    return nullptr;
}

递归实现

typrdef BSTreeNode<K> Node;
?
Node* _findr(Node* root,const K& key)
{
    if(root==nullptr)
    {
        return nullptr;
    }
    if(root->_key<key)
    {
        return _findr(root->_right);
    }
    else if(root->_key>key)
    {
        return _findr(root->_left);
    }
    else
        return root;
    
}

构造搜索二叉树

若树为空树，则直接插入；否则
若插入值大于根节点的键值，则插入到右子树中，以此递归；否则
若插入值小于根节点的键值，则插入到左子树中

非递归实现：

bool insert(const K& key)
{
    if(_root==nullptr)
    {
        _root=new Node(key);
        return true;
    }
    Node* parent=nullptr;
    Node* cur=_root;
    while(cur)
    {
        if(cur->_key<key)
        {
            parent=cur;
            cur=cur->_right;
        }
        else if(cur->_key>key)
        {
            parent=cur;
            cur=cur->_left;
        }
        else
            return false;
    }
    cur=new Node(key);
    if(parent->_key<key)
    {
        parent->_right=cur;
    }
    else
        parent->_left=cur;
    return true;
}

递归实现：

bool _insertR(Node* &root,const K&key)
{
    if(root==NULL)
    {
        root=new Node(key);
        return true;
    }
    if(root->_key<key)
        return _insertR(root->_right,key);
    else if(root->_key>key)
        return _insertR(root->_left,key);
    else
        return false;
}

往搜索二叉树中插入元素

向一个二叉搜索树b中插入一个节点s的算法，过程为：

若b是空树，则将s所指结点作为根节点插入，否则：
若s->data等于b的根节点的数据域之值，则返回，否则：
若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则：
把s所指节点插入到右子树中。（新插入节点总是叶子节点）

搜索二叉树删除节点

重难点

二叉搜索树的结点删除比插入较为复杂，总体来说，结点的删除可归结为三种情况：

如果结点z没有孩子节点，那么只需简单地将其删除，并修改父节点，用NULL来替换z；
如果结点z只有一个孩子，那么将这个孩子节点提升到z的位置，并修改z的父节点，用z的孩子替换z；
如果结点z有2个孩子，那么查找z的后继y，此外后继一定在z的右子树中，然后让y替换z