二叉搜尋樹查找，插入，删除

二叉排序樹的查找過程通常采取二叉連結清單作為二叉排序樹的存儲結構。中序周遊二叉排序樹可得到一個關鍵字的有序序列，一個無序列可以通過構造一棵二叉排序樹變成一個有序序列，構造樹的過程即為對無序列進行排序的過程。每次插入的新的結點都是二叉排序樹上新的葉子結點，在進行插入操作時，不必移動其它結點，隻需改動某個結點的指針，由空變為非空即可。搜尋,插入,删除的複雜度等于樹高，O(log(n)).

查找算法:

在二叉排序樹b中查找x的過程為：

若b是空樹，則搜尋失敗，否則：

若x等于b的根結點的資料域之值，則查找成功；否則：

若x小于b的根結點的資料域之值，則搜尋左子樹；否則：

查找右子樹。

插入算法:

向一個二叉排序樹b中插入一個結點s的算法，過程為：

若b是空樹，則将s所指結點作為根結點插入，否則：

若s->data等于b的根結點的資料域之值，則傳回，否則：

若s->data小于b的根結點的資料域之值，則把s所指結點插入到左子樹中，否則：

把s所指結點插入到右子樹中。

删除算法:

在二叉排序樹删去一個結點，分三種情況讨論：

（1）若*p結點為葉子結點，即PL(左子樹)和PR(右子樹)均為空樹。由于删去葉子結點不破壞整棵樹的結構，則隻需直接删去接點即可

二叉搜尋樹查找，插入，删除

（2）若*p結點隻有左子樹PL或右子樹PR，此時隻要令PL或PR直接成為其雙親結點*f的左子樹或右子樹即可，作此修改也不破壞二叉排序樹的特性。

二叉搜尋樹查找，插入，删除

（3）若*p結點的左子樹和右子樹均不空。

可分為兩種類型，一種是z的後繼y位于其右子樹中，但沒有左孩子，也就是說，右孩子y是其後繼。如下：

二叉搜尋樹查找，插入，删除

另外一種類型是，z的後繼y位于z的右子樹中，但并不是z的右孩子，此時，用y的右孩子替換y，然後再用y替換z。如下：

二叉搜尋樹查找，插入，删除

#include <iostream>
using namespace std;


template<class K, class V>
struct BinarySearchTreeNode
{
    BinarySearchTreeNode(const K& key, const V& value)
        : _pLeft(NULL)
        , _pRight(NULL)
        , _key(key)
        , _value(value)
    {}

    BinarySearchTreeNode<K, V>* _pLeft;
    BinarySearchTreeNode<K, V>* _pRight;

    K _key;
    V _value;
};


template<class K, class V>
class BinarySearchTree
{
    typedef BinarySearchTreeNode<K, V> Node;
    typedef BinarySearchTree<K, V> Self;

public:
    BinarySearchTree()
        :_pRoot(NULL)
    {}


    BinarySearchTree(const Self& bst)
    {
        _pHead = _CopyTree(bst._pRoot);
    }

    Self& operator=(const Self& bst)
    {
        if(this != NULL)
        {
            _DestoryTree(_pRoot);
            _pRoot = _CopyTree(bst._pRoot);
            return *this;
        }
    }

    ~BinarySearchTree()
    {
        _DestoryTree(_pRoot);
    }

    // 查找遞歸和非遞歸
    bool Find_Nor(const K& key)
    {
        if(_pRoot == NULL)
            return false;

        Node* pCur = _pRoot;
        while(pCur)
        {
            if(_pRoot->_key == key)
                return true;
            else if(_pRoot->_key > key)
                pCur = pCur->_pRight;
            else
                pCur = pCur->_pLeft;
        }
        return false;
    }

    bool Find(const K& key)
    {
        return _Find(_pRoot, key);
    }

    // 插入遞歸和非遞歸
    bool Insert_Nor(const K& key, const V& value)
    {
        if (_pRoot == NULL)   
        {
            _pRoot = new Node(key, value);  
        }

        Node* pCur = _pRoot;
        Node* parent = NULL;

        //找到要插入節點的位置
        while(pCur)
        {
            if (pCur->_key > key)  
            {  
                parent = pCur;  
                pCur = pCur->_pLeft;  
            }  
            else if(pCur->_key < key)  
            {  
                parent = pCur;  
                pCur = pCur->_pRight;  
            }  
            else   //要麼節點已存在，要麼插入位置不合法  
                return false; 
        }
        //找到插入位置後，判斷插入父親節點是左還是右
        if(parent->_key > key)
            parent->_pLeft = new Node(key, value);
        else
            parent->_pRight = new Node(key, value);
    }

    bool Insert(const K& key, const V& value)
    {
        return _Insert(_pRoot, key, value);
    }

    // 删除遞歸和非遞歸
    bool Remove_Nor(const K& key)
    {
        //二叉搜尋樹中沒有節點
        if(_pRoot == NULL)
            return false;

        //二叉搜尋樹中隻有根節點
        if(_pRoot->_pLeft == NULL && _pRoot->_pRight == NULL)
        {
            if(_pRoot->_key == key)
            {
                delete _pRoot;
                _pRoot = NULL;
                return true;
            }
            return false;
        }

        Node* pCur = _pRoot;
        Node* parent = NULL;

        //周遊查找要删除節點的位置
        while(pCur)
        {
            Node* pDel = NULL; 
            if(pCur->_key < key)
            {
                parent = pCur;
                pCur = pCur->_pRight;
            }
            else if(pCur->_key > key)
            {
                parent = pCur;
                pCur = pCur->_pLeft;
            }
            else
            {
                //要删除節點的左子樹為空
                if(pCur->_pLeft == NULL)
                {
                    //判斷父節點是否為空，若為空，則要删除的節點為根節點
                    if (parent == NULL)  
                    {  
                        _pRoot = pCur->_pRight;  
                        delete pCur;  
                        pCur = NULL;  
                        return true;  
                    } 

                    else if(parent->_key < key)  //右子樹
                    {
                        pDel = pCur;
                        parent->_pRight = pCur->_pRight;
                        delete pDel;
                        pDel = NULL;
                        return true;
                    }
                    else  //左子樹
                    {
                        pDel = pCur;
                        parent->_pLeft = pCur->_pRight;
                        delete pDel;
                        pDel = NULL;
                        return true;
                    }
                }
                //要删除節點的右子樹為空
                else if(pCur->_pRight == NULL)
                {
                    //判斷父節點是否為空，若為空，則要删除的節點為根節點
                    if (parent == NULL)  
                    {  
                        _pRoot = pCur->_pLeft;  
                        delete pCur;  
                        pCur = NULL;  
                        return true;  
                    } 
                    else if(parent->_key > key)  //左子樹
                    {
                        pDel = pCur;
                        parent->_pLeft = pCur->_pLeft;
                        delete pCur;
                        pCur = NULL;
                        return true;
                    }
                    else   //右子樹
                    {
                        pDel = pCur;
                        parent->_pRight = pCur->_pLeft;
                        delete pDel;
                        pDel = NULL;
                        return true;
                    }
                }
                //左右子樹都不為空
                //右子樹中序周遊第一個節點，用它的值替換被删除節點的值，在進行删除
                else
                {
                    Node* pDel = pCur;  
                    Node* parent = NULL;  
                    Node* RightFirst = pCur->_pRight; 

                    //右邊第一個節點的左子樹為空 
                    if (RightFirst->_pLeft == NULL)  
                    {  
                        swap(RightFirst->_key, pCur->_key);  
                        swap(RightFirst->_value, pCur->_value);
                        //交換删除節點與中序周遊第一個節點的值,即就是最左邊節點 
                        pDel = RightFirst;  
                        pCur->_pRight = RightFirst->_pRight;  
                        delete pDel;  
                        return true;  
                    } 

                    //右邊第一個節點的左子樹不為空  
                    while (RightFirst->_pLeft)  
                    {  
                        parent = RightFirst;  
                        RightFirst = RightFirst->_pLeft;  
                    }  
                    swap(RightFirst->_key, pCur->_key);  
                    swap(RightFirst->_value, pCur->_value);  
                    pDel = RightFirst;  
                    parent->_pLeft = RightFirst->_pRight;  
                    delete pDel;  
                    return true;    
                }
            }
        }
    }

    bool Remove(const K& key)
    {
        return _Remove(_pRoot, key);
    }

    void InOrder()
    {
        cout<<"中序周遊結果為:";
        _InOrder(_pRoot);
        cout<<endl;
    }

private:
    Node* _CopyTree(Node* pRoot)
    {
        if(pRoot)
        {
            Node* pNewNode = new Node(pRoot->_key, pRoot->_value);
            pNewNode->_pLeft = _CopyTree(pRoot->_pLeft);
            pNewNode->_pRight = _CopyTree(pRoot->_pRight);

            return pNewNode;
        }
        return NULL;
    }

    void _DestoryTree(Node*& pRoot)
    {
        if(pRoot)
        {
            _DestoryTree(pRoot->_pLeft);
            _DestoryTree(pRoot->_pRight);
            delete pRoot;
            pRoot = NULL;
        }
    }

    bool _Find(Node* pRoot, const K& key)
    {
        if(pRoot == NULL)
            return false;

        if(pRoot->_key == key)
            return true;

        if(pRoot->_key > key)
            _Find(pRoot->_pRight, key);

        if(pRoot->_key < key)
            _Find(pRoot->_pLeft, key);
    }

    bool _Insert(Node* &pRoot, const K& key, const V& value)
    {
        if(pRoot == NULL)
            pRoot = new Node(key, value);

        if(pRoot->_key > key)
            _Insert(pRoot->_pLeft, key, value);

        else if (pRoot->_key < key)
            _Insert(pRoot->_pRight, key, value);

        else 
            return false;
    }

    bool _Remove(Node*& pRoot, const K& key)
    {
        if(pRoot == NULL) //空樹
            return false;

        //隻有根節點
        if(pRoot->_pLeft == NULL && pRoot->_pRight == NULL)
        {
            if(pRoot->_key == key)
            {
                delete pRoot;
                pRoot = NULL;
                return true;
            }
            else
                return false;
        }

        //遞歸查找要删除節點的位置
        if(pRoot->_key >  key)
            _Remove(pRoot->_pLeft, key);
        else if(pRoot->_key < key)
            _Remove(pRoot->_pRight, key);
        else
        {
            Node* pDel = NULL;

            //要删除的節點隻有右孩子
            if(pRoot->_pLeft == NULL)
            {
                pDel = pRoot;
                pRoot = pRoot->_pRight;
                delete pDel;
                pDel = NULL;
                return true;
            }

            //要删除的節點隻有左孩子
            else if(pRoot->_pRight == NULL)
            {
                pDel = pRoot;
                pRoot = pRoot->_pLeft;
                delete pDel;
                pDel = NULL;
                return true;
            }

            //要删除的節點有左右孩子
            else
            {
                Node* RightFirst = pRoot->_pRight;
                while(RightFirst->_pLeft)
                    RightFirst = RightFirst->_pLeft;

                swap(pRoot->_key, RightFirst->_key);  
                swap(pRoot->_value, RightFirst->_value);  

                _Remove(pRoot->_pRight, key);  
                return true; 
            }
        }
        return false;
    }

    void _InOrder(Node* pRoot)
    {
        if(pRoot)
        {
            _InOrder(pRoot->_pLeft);
            cout<<pRoot->_key<<" ";
            _InOrder(pRoot->_pRight);
        }
    }
private:
    Node* _pRoot;
};

// 測試非遞歸的三種情況
void Test1()
{
    BinarySearchTree<int, int> bst;
    int a [] = {5,3,4,1,7,8,2,6,0,9,};
    int len = sizeof(a)/sizeof(a[]);

    for(size_t idx=0; idx<len; ++idx)
    {
        bst.Insert_Nor(a[idx], a[idx]);
    }

    bst.InOrder();
    bst.Find_Nor(2);
    bst.InOrder();
    bst.Find_Nor(0);
    bst.InOrder();
    bst.Find_Nor(5);
    bst.InOrder();
    bst.Find_Nor(10);
    bst.InOrder();

    //要删除節點左右子樹都為空
    bst.Remove_Nor(4);
    bst.InOrder();

    //要删除節點右子樹為空
    bst.Remove_Nor(9);
    bst.InOrder();

    bst.Remove_Nor(0);
    bst.InOrder();

    //要删除節點左子樹為空
    bst.Remove_Nor(4);
    bst.InOrder();

    //要删除節點左右子樹都不為空
    bst.Remove_Nor(5);
    bst.InOrder();
}


// 測試遞歸的三種情況
void Test2()
{
    BinarySearchTree<int, int> bst;
    int a [] = {5,3,4,1,7,8,2,6,0,9,};
    int len = sizeof(a)/sizeof(a[]);

    for(size_t idx=0; idx<len; ++idx)
    {
        bst.Insert(a[idx], a[idx]);
    }

    bst.InOrder();
    bst.Find(2);
    bst.InOrder();
    bst.Find(0);
    bst.InOrder();
    bst.Find(5);
    bst.InOrder();
    bst.Find(10);
    bst.InOrder();

    //要删除節點左右子樹都為空
    bst.Remove(4);
    bst.InOrder();

    //要删除節點右子樹為空
    bst.Remove(9);
    bst.InOrder();

    bst.Remove(0);
    bst.InOrder();

    //要删除節點左子樹為空
    bst.Remove(4);
    bst.InOrder();

    //要删除節點左右子樹都不為空
    bst.Remove(5);
    bst.InOrder();
}

int main()
{
    //Test1();
    Test2();

    system("pause");
    return 0;
}

二叉搜尋樹查找，插入，删除

查找算法:

插入算法:

删除算法:

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器