日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學(xué)無先后，達(dá)者為師

網(wǎng)站首頁 編程語言 正文

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

作者：m0_52012656 ? 更新時(shí)間： 2022-06-15 編程語言

定義

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

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

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

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

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

5、搜索二叉樹中序遍歷為有序數(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è)元素

在搜索二叉樹b中查找x的過程

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

非遞歸實(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)造搜索二叉樹

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

非遞歸實(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;
}

往搜索二叉樹中插入元素

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

  • 若b是空樹，則將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)插入到左子樹中，否則：
  • 把s所指節(jié)點(diǎn)插入到右子樹中。（新插入節(jié)點(diǎn)總是葉子節(jié)點(diǎn)）

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

重難點(diǎn)

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

  • 如果結(jié)點(diǎn)z沒有孩子節(jié)點(diǎn)，那么只需簡(jiǎn)單地將其刪除，并修改父節(jié)點(diǎn)，用NULL來替換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的右子樹中，然后讓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
        {
            //找到了，開始刪除
            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)

// 如果樹中不存在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的右子樹刪除min
            _EraseR(root->_right,min);
            root->_key=min;
            
        }
        return true;
    }
}

原文鏈接：https://blog.csdn.net/m0_52012656/article/details/124174399

欄目分類
最近更新