C++ 詳解數(shù)據(jù)結(jié)構(gòu)中的搜索二叉樹(shù)

更新時(shí)間：2022年04月15日 10:55:32 作者：m0_52012656

搜索二叉樹(shù)是一種具有良好排序和查找性能的二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)，包括多種操作，本篇只介紹插入，排序（遍歷），和刪除操作，重點(diǎn)是刪除操作比較復(fù)雜

定義

搜索二叉樹(shù)，也稱(chēng)有序二叉樹(shù)，排序二叉樹(shù)，是指一棵空樹(shù)或者具有下列性質(zhì)的二叉樹(shù)：

1、若任意節(jié)點(diǎn)的左子樹(shù)不空，則左子樹(shù)上的所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值

2、若任意節(jié)點(diǎn)的右子樹(shù)不空，則右子樹(shù)上的所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值

3、任意節(jié)點(diǎn)的左右子樹(shù)也稱(chēng)為二叉查找樹(shù)。

4、沒(méi)有鍵值相等的節(jié)點(diǎn)。

5、搜索二叉樹(shù)中序遍歷為有序數(shù)組。

結(jié)構(gòu)代碼實(shí)現(xiàn)

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

查找某個(gè)元素

在搜索二叉樹(shù)b中查找x的過(guò)程

若樹(shù)是一個(gè)空樹(shù)，則搜索失敗，否則：
若x等于b的根節(jié)點(diǎn)的鍵值，則查找成功；否則：
若x小于b的根節(jié)點(diǎn)的鍵值，則搜索左子樹(shù)；否則：
若x大于b的根節(jié)點(diǎn)的鍵值，則搜索右子樹(shù)。

非遞歸實(shí)現(xiàn)

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;
}

遞歸實(shí)現(xiàn)

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;
    
}

構(gòu)造搜索二叉樹(shù)

若樹(shù)為空樹(shù)，則直接插入；否則
若插入值大于根節(jié)點(diǎn)的鍵值，則插入到右子樹(shù)中，以此遞歸；否則
若插入值小于根節(jié)點(diǎn)的鍵值，則插入到左子樹(shù)中

非遞歸實(shí)現(xiàn)：

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;
}

遞歸實(shí)現(xiàn)：

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;
}

往搜索二叉樹(shù)中插入元素

向一個(gè)二叉搜索樹(shù)b中插入一個(gè)節(jié)點(diǎn)s的算法，過(guò)程為：

若b是空樹(shù)，則將s所指結(jié)點(diǎn)作為根節(jié)點(diǎn)插入，否則：
若s->data等于b的根節(jié)點(diǎn)的數(shù)據(jù)域之值，則返回，否則：
若s->data小于b的根節(jié)點(diǎn)的數(shù)據(jù)域之值，則把s所指節(jié)點(diǎn)插入到左子樹(shù)中，否則：
把s所指節(jié)點(diǎn)插入到右子樹(shù)中。（新插入節(jié)點(diǎn)總是葉子節(jié)點(diǎn)）

搜索二叉樹(shù)刪除節(jié)點(diǎn)

重難點(diǎn)

二叉搜索樹(shù)的結(jié)點(diǎn)刪除比插入較為復(fù)雜，總體來(lái)說(shuō)，結(jié)點(diǎn)的刪除可歸結(jié)為三種情況：

如果結(jié)點(diǎn)z沒(méi)有孩子節(jié)點(diǎn)，那么只需簡(jiǎn)單地將其刪除，并修改父節(jié)點(diǎn)，用NULL來(lái)替換z；
如果結(jié)點(diǎn)z只有一個(gè)孩子，那么將這個(gè)孩子節(jié)點(diǎn)提升到z的位置，并修改z的父節(jié)點(diǎn)，用z的孩子替換z；
如果結(jié)點(diǎn)z有2個(gè)孩子，那么查找z的后繼y，此外后繼一定在z的右子樹(shù)中，然后讓y替換z

非遞歸實(shí)現(xiàn)

bool Erase(const K& key)
{
    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
        {
            //找到了，開(kāi)始刪除
            if(cur->_left==nullptr)
            {
                if(cur==_root)
                {
                    _root=cur->_right;
                }
                else
                {
                    if(parent->_left==cur)
                    {
                        parent->_left=cur->_right;
                    }
                    else
                    {
                        parent->_right=cur->_right;
                    }
                }
                delete cur;
            }
            else if(cur->_right==nullptr)
            {
                if(cur==_root)
                {
                    _root=cur->_left;
                }
                else
                {
                    if(parent->_left==cur)
                    {
                        parent->_left=cur->_left;
                    }
                    else
                    {
                        parent->_right=cur->_right;
                    }
                }
            }
            else   //左右都不為空
            {
                Node* minRight=cur->_right;
                while(minRight->_left)
                {
                    minRight=minRight->_left;
                }
                k min = minRight->_key;
                this->Erase(min);
                
                cur->_key=min;
            }
            return true;
        }
    }
    return false;
}

遞歸實(shí)現(xiàn)

// 如果樹(shù)中不存在key，返回false
// 存在，刪除后，返回true
bool _EraseR(Node*& root, const K& key)
{
    if(root==nullptr)
        return false;
    if(root->_key<key)
        return _EraseR(root->_right,key);
    else if(root->_key>key)
        return _EraseR(root->_left,key);
    else
    {
        //找到了，root就是要?jiǎng)h除的節(jié)點(diǎn)
        if(root->_left == nullptr)
        {
            Node* del=root;
            root=root->_right;
            delete del;
        }
        else if(root->_right==nullptr)
        {
            Node* del = root;
            root=root->_left;
            delete del;
        }
        else
        {
            Node* minRight=root->_right;
            while(minRight->_left)
            {
                minRight=minRight->_left;
            }
            K min=minRight->_key;
            
            //轉(zhuǎn)化為root的右子樹(shù)刪除min
            _EraseR(root->_right,min);
            root->_key=min;
            
        }
        return true;
    }
}

到此這篇關(guān)于C++ 詳解數(shù)據(jù)結(jié)構(gòu)中的搜索二叉樹(shù)的文章就介紹到這了,更多相關(guān)C++ 搜索二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: