C++ 二叉搜索樹原理及其實現(xiàn)

首先是概念：
二叉搜索樹又稱二叉排序樹，它具有以下的性質：

• 若是左子樹不為空，則左子樹上所有節(jié)點的值小于根節(jié)點的值
• 若是右子樹不為空，則右子樹上所有結點的值大于根節(jié)點的值
• 二叉搜索樹的左右子樹也是二叉搜索樹
• 二叉搜索樹的中序排列是一個有序數(shù)列

再下來是它的實現(xiàn)

首先是構造節(jié)點：

template<class K>
struct BStreeNode{
    BStreeNode(const K& date = K())    //節(jié)點的定義
    :leftC(nullptr),    // 初始化
    rightC(nullptr),
    date_(date)
    {}
    BStreeNode<K> *leftC;      //左孩子
    BStreeNode<K> *rightC;    //右孩子
    K date_;
};

二叉搜索樹類的實現(xiàn)：

template<class K>
class BStree{
    typedef BStreeNode<K> BsNode;
public:
    BStree() :
        _root(nullptr)    
    {}
    BsNode* Find(const K& date){       //查找節(jié)點
        BsNode* pNode = _root;
        while (pNode){
            if (pNode->date_ == date){
                return pNode;
            }
            else if (pNode->date_ > date){
                pNode = pNode->rightC;
            }
            else
                pNode = pNode->leftC;
        }
        return nullptr;
    }
    bool Insert(const K& date){
        BsNode *pNode = _root;
        BsNode *parent=nullptr;
        if (_root == nullptr){      //空樹時開辟空間定義為根節(jié)點
            _root = new BsNode(date);
            return true;
        }
        else if (Find(date)){   //存在相同結點不進行插入
            return false;
        }
        else{
            while (pNode){         //找到插入位置，但是這里循環(huán)結束后只確認了父母結點，是做左孩子還是右孩子不確認( 因為此時值為nullptr )
                parent = pNode;
                if (pNode->date_ > date){
                    pNode = pNode->leftC;
                }
                else{
                    pNode = pNode->rightC;
                }
            }
            pNode = new BsNode(date);    //構造結點
            if (parent->date_ > date){       //確認是做左孩子還是右孩子
                parent->leftC = pNode;
            }
            else{
                parent->rightC = pNode;
            }
            return true;
        }
    }

    bool Delete(const K& date){
        BsNode *pNode = _root;
        BsNode *parent = nullptr;
        if (pNode == nullptr){    //空樹情況
            return false;
        }
        while (pNode){      //找到要刪除的結點
            if (pNode->date_ == date){
                break;
            }
            else if (pNode->date_ < date){
                parent = pNode;
                pNode = pNode->rightC;
            }
            else{
                parent = pNode;
                pNode = pNode->leftC;
            }
        }
        //BsNode *pdel=pNode;
        if (pNode == parent){      //要刪除的點是根節(jié)點
            if (pNode->leftC){
                pNode = pNode->leftC;
            }
            else if (pNode->rightC){
                pNode = pNode->rightC;
            }
            else{
                pNode = nullptr;
            }
        }
        if (pNode == nullptr){   // 沒有找到要刪除的節(jié)點
            return false;
        }
        if (pNode->rightC && pNode->leftC == nullptr){  //結點只有右子樹
            if (pNode == parent->leftC){
                parent->leftC = pNode->rightC;
            }
            else{
                parent->rightC = pNode->rightC;
            }
        }
        else if (pNode->leftC && pNode->rightC == nullptr){   //結點只有左子樹
            if (pNode == parent->leftC){
                parent->leftC = pNode->leftC;
            }
            else{
                parent->rightC = pNode->leftC;
            }
        }
        else if (pNode->leftC && pNode->rightC){    //兒女俱全
            if (pNode == parent->leftC){   //要刪除的節(jié)點是父母節(jié)點的左孩子，刪除后的位置要由原先節(jié)點的右孩子替代
                pNode->rightC->leftC = pNode->leftC;
                parent->leftC = pNode->rightC;
            }
            else{
                pNode->leftC->rightC= pNode->rightC;  //要刪除的節(jié)點是父母節(jié)點的右孩子，刪除后的位置要由原先節(jié)點的左孩子替代
                parent->rightC = pNode->leftC;
            }
        }
        else{                                        //無子可依
            if (pNode == parent->leftC){
                parent->leftC = nullptr;
            }
            else{
                parent->rightC = nullptr;
            }
        }
        delete pNode;     //在連接完成后最后再進行刪除
        return true;
    }

    BsNode* IfLeftMost(){
        if (_root == nullptr){
            return nullptr;
        }
        BsNode *pNode = _root;
        while (pNode->leftC){
            pNode = pNode->leftC;
        }
        return pNode;
    }
    BsNode* IfRightMost(){
        if (_root == nullptr){
            return nullptr;
        }
        BsNode *pNode = _root;
        while (pNode->rightC){
            pNode = pNode->rightC;
        }
        return pNode;
    }
    void InOrder(){  //定義一個借口給外部調用，因為根節(jié)點在這里是private權限
        InOrder(_root);
        cout << endl;
    }

private:
    void InOrder(BsNode *pNode){    //二叉樹的中序遍歷，用來檢查結果（二叉搜索樹中序遍歷應該是一個有序序列）
        if (pNode){
            InOrder(pNode->leftC);
            cout << pNode->date_ << ' ';
            InOrder(pNode->rightC);
        }
    }
private:
    BsNode *_root;
};

測試函數(shù)這里就不提供了