C++ 詳解資料結構中的搜尋二元樹

2022-04-15 13:01:05

定義

搜尋二元樹，也稱有序二元樹，排序二元樹，是指一棵空樹或者具有下列性質的二元樹：

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