C++ 二叉搜索树原理及其实现

首先是概念：
二叉搜索树又称二叉排序树，它具有以下的性质：

• 若是左子树不为空，则左子树上所有节点的值小于根节点的值
• 若是右子树不为空，则右子树上所有结点的值大于根节点的值
• 二叉搜索树的左右子树也是二叉搜索树
• 二叉搜索树的中序排列是一个有序数列

再下来是它的实现

首先是构造节点：

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

二叉搜索树类的实现：

template<class K>
class BStree{
    typedef BStreeNode<K> BsNode;
public:
    BStree() :
        _root(nullptr)    
    {}
    BsNode* Find(const K& date){       //查找节点
        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){      //空树时开辟空间定义为根节点
            _root = new BsNode(date);
            return true;
        }
        else if (Find(date)){   //存在相同结点不进行插入
            return false;
        }
        else{
            while (pNode){         //找到插入位置，但是这里循环结束后只确认了父母结点，是做左孩子还是右孩子不确认( 因为此时值为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){      //要删除的点是根节点
            if (pNode->leftC){
                pNode = pNode->leftC;
            }
            else if (pNode->rightC){
                pNode = pNode->rightC;
            }
            else{
                pNode = nullptr;
            }
        }
        if (pNode == nullptr){   // 没有找到要删除的节点
            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){   //要删除的节点是父母节点的左孩子，删除后的位置要由原先节点的右孩子替代
                pNode->rightC->leftC = pNode->leftC;
                parent->leftC = pNode->rightC;
            }
            else{
                pNode->leftC->rightC= pNode->rightC;  //要删除的节点是父母节点的右孩子，删除后的位置要由原先节点的左孩子替代
                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(){  //定义一个借口给外部调用，因为根节点在这里是private权限
        InOrder(_root);
        cout << endl;
    }
 
private:
    void InOrder(BsNode *pNode){    //二叉树的中序遍历，用来检查结果(二叉搜索树中序遍历应该是一个有序序列)
        if (pNode){
            InOrder(pNode->leftC);
            cout << pNode->date_ << ' ';
            InOrder(pNode->rightC);
        }
    }
private:
    BsNode *_root;
};

测试函数这里就不提供了