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

學無先后，達者為師

網站首頁 編程語言 正文

C++?詳解數據結構中的搜索二叉樹_C 語言

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

定義

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

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

非遞歸實現

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

遞歸實現

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

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

欄目分類
最近更新