数据结构算法之二分搜索树

定义

根结点的右结点一定比根结点大，左结点一定比根结点小。

image.png

如上图，我们若熟悉树的遍历我们可以从上图看出二叉搜索树的中序遍历就是从小到大排序。

定义结点

template<class K, class V>
struct TreeNode {
public:
    TreeNode(TreeNode<K, V> *pNode) {
        this->left = pNode->left;
        this->right = pNode->right;
        this->key = pNode->key;
        this->value = pNode->value;
    }

    TreeNode<K, V> *left = NULL;
    TreeNode<K, V> *right = NULL;
    K key;
    V value;

    TreeNode(K key, V value) {
        this->right = NULL;
        this->left = NULL;
        this->key = key;
        this->value = value;
    }
};

二分搜索树

首先需要一个根节点和个数

template<class K, class V>
class BST {
    TreeNode<K, V> *root;// 根节点
    int count;// 个数

public:
    BST() {
        root = NULL;
        count = 0;
    }

    ~BST() {

    }
}

判断一个树是否包含

    bool contains(K key) {
        TreeNode<K, V> *node = root;

        while (node) {
            if (node->key == key) {
                return node->value;
            } else if (node->key > key) {
                node = node->left;
            } else {
                node = node->right;
            }
        }

        return false;
    }

首先我们要判断该结点是否为空，若为空，则new一个，然后判断，如果key小于结点的key则放到左边，若大于则放右边，反之相等的时候，直接替换值就可以了。

添加一个树

  void put(K key, V value) {
        root = addNode(root, key, value);
    }
 // 返回一个节点 (
    TreeNode<K, V> *addNode(TreeNode<K, V> *pNode, K key, V value) {
        if (pNode == NULL) {
            count++;
            return new TreeNode<K, V>(key, value);
        }
        //当前的key小于结点的key，添加到左边
        if (key < pNode->key) {
            pNode->left = addNode(pNode->left, key, value);
        } else if (key > pNode->key) {
            pNode->right = addNode(pNode->right, key, value);
        } else {
            pNode->value = value;
        }

        return pNode;
    }

删除结点

删除结点总体分为四种情况
1.删除的结点的左右结点都为空,这种情况直接删除就可以了
2.删除的结点的左结点为空,返回右结点
3.删除的右结点为空，返回左结点
4.删除的结点左右都不为空

    // 删除
    void remove(K key) {
        // 分情况解决
        root = removeNode(root, key);
    }
TreeNode<K, V> *removeNode(TreeNode<K, V> *pNode, K key) {
        if (key < pNode->key) {
            pNode->left = removeNode(pNode->left, key);
        } else if (key > pNode->key) {
            pNode->right = removeNode(pNode->right, key);
        } else {// 相等
            count--;
            if (pNode->left == NULL && pNode->right == NULL) {
                delete pNode;
                return NULL;
            } else if (pNode->left == NULL) {
                TreeNode<K, V> *right = pNode->right;
                delete pNode;
                return right;
            } else if (pNode->right == NULL) {
                TreeNode<K, V> *left = pNode->left;
                delete pNode;
                return left;
            } else {
                // 左右两子树都不为空
               TreeNode<K, V> *successor = new TreeNode<K, V>(maximum(pNode->left));
                successor->left = deleteMax(pNode->left);
                count++;
                successor->right = pNode->right;
                delete (pNode);
                return successor;
            }
        }
        return pNode;
    }
    TreeNode<K, V> *deleteMax(TreeNode<K, V> *pNode) {
        //找到最大值
       if (pNode->right == NULL) {
            TreeNode<K, V> *left = pNode->left;
            delete (pNode);
            count--;
            return left;
        }
        pNode->right = deleteMax(pNode->right);
        return pNode;
    }

    // 查找当前树的最大值
    TreeNode<K, V> *maximum(TreeNode<K, V> *pNode) {
        // 不断的往右边找，直到找到右子树为空节点
        if (pNode->right == NULL) {
            return pNode;
        }
        return maximum(pNode->right);
    }

主要分析最后一种情况，比如上面删除的是2这个结点，我们首先去左边找到它的最大值也就是上面代码中的maximum方法，此时最大值是0这个结点，我们去new一个新节点，值为0(或者去它的右边找到它的最小值)。随后将移除的结点的右结点赋值给新节点的右结点，而将原本0结点的左结点重新赋值给新节点