二叉搜索树 (BST) 的定义

二叉搜索树 (Binary Search Tree)的结点定义一般如下

typedef struct Node 
{
	int key;			//节点关键值
	Node* left;			//左子树指针
	Node* right; 		//右子树指针
} *BSTree;

BST 具有以下特征:

左子树非空时, 左子树所有结点的 key, 均小于根结点的 key
右子树非空时, 右子树所有结点的 kay, 均大于根结点的 kay
任意结点的左右子树也是一颗二叉搜索树
没有结点值相等的

缺点

BST的层数越少, 查找时间越少, 但是当数据增多时BST并不能保证树的高度一直是最优的, 甚至在极端情况下 : 一个已经有序的数列-----会导致BST变成一个单链表.

平衡树: AVL树以及应用更为广泛的红黑树解决了这个问题

代码实现:

//没有考虑太多, 很简单的封装
class BSTree
{
public:
    BSTree() : root_(nullptr) {}
    ~BSTree() { release(root_); }
    BSTNode* root() { return root_; }
    BSTNode* insert(int key, BSTNode* node);
    BSTNode* search(int key, BSTNode* node);
    int findMaxKeyInLef(BSTNode* node);
    BSTNode* delNode(int key, BSTNode* node);
    bool isBST(BSTNode* node);
    void show(BSTNode* node);

    BSTNode* root_;

private:
    void release(BSTNode* node) noexcept;
};

BST 的构建

BST的构建过程就是将一个无序数列变成有序数列的过程

BST 的插入

BSTNode* BSTree::insert(int key, BSTNode* node) 
{
    //新插入结点总是叶子结点
    if (node == nullptr) 
    {
        node = new BSTNode(key);
        if (root_ == nullptr)
            root_ = node;
        return node; 
    }
    else 
    {
        if (key > node->key)
            node->right = insert(key, node->right);
        else 
           node->left = insert(key, node->left);
        return node;
    }
}

BST 的查询

BSTNode* BSTree::search(int key, BSTNode* node) 
{
    if (node == nullptr)
        return node;
    if (key < node->key) 
        return search(key, node->left);
    else if (key > node->key) 
        return search(key, node->right);
    else if (key == node->key)
        return node;
}

BST 的删除

BST的删除是最为难处理的, 他分为四种情况 :

叶子结点 :

直接删除

右子树非空

让父节点指向被删除结点的左子树

左子树非空

让父结点指向被删除结点的右子树

左右子树非空

可以交换被删除结点和其左子树中的最大值结点
也可以交换被删除结点和其右子树中的最小值结点
然后删除被删除节点

int BSTree::findMaxKeyInLef(BSTNode* node) 
{
    if (node == nullptr)
        return 0;
    else if (node->right == nullptr)
        return node->key;
    return findMaxKeyInLef(node->right);
}
BSTNode* BSTree::delNode(int key, BSTNode* node) 
{
    if (node == nullptr) 
        return nullptr;
    else if (key < node->key)
    {
        node->left = delNode(key, node->left);
        return node;
    }
    else if (key > node->key)
    {
        node->right = delNode(key, node->right);
        return node;
    }
    else if (key == node->key)
    {
        //如果是叶子结点
        if (node->left == nullptr && node->right == nullptr) 
        {
            delete node;
            node = nullptr;
            return node;;
        }
        //如果左子树非空,将右子树续接到父结点
        else if (node->left != nullptr) 
        {
            BSTNode* tmp = node->left;
            delete node;
            return tmp;
        }
        //如果右子树非空,将左子树续接到父结点
        else if (node->right != nullptr) 
        {
            BSTNode* tmp = node->right;
            delete node;
            return tmp;
        }
        //左右子树皆非空
        else 
        {
            //寻找左子树中最大结点,即左子树中最右结点
            //(也可以寻找右子树中最小结点,即右子树中最左结点)
            int maxVal = findMaxKeyInLef(node->left);
            //交换这两个节点
            node->key = maxVal;
            //删除那个用来交换的节点
            node->left = delNode(maxVal, node->left);
            return node;
        }
    }
}

BST 的检验

对BST进行中序遍历, 如果遍历结果不是生序的, 则不是BST
进一步优化可以不用保存遍历结果, 而是在中序遍历的时候, 保存前驱结点, 如果当前节点小于前驱结点, 则不是BST

bool BSTree::isBST(BSTNode* node) 
{
    static BSTNode *prev = NULL;  
    // 中序遍历这棵树，并保存前驱结点至prev中  
    if (node != nullptr) 
    {  
         if (isBST(node->left) == false)  
              return false;  
         //当前节点小于前驱结点,这棵树就不是BST 
         if (prev != NULL && node->key <= prev->key)  
              return false;  
         prev = node;  
         //右子树  
         return isBST(node->right);  
    }  
  
    return true;  
}