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

作者: Peakmain | 来源:发表于2019-04-01 14:25 被阅读0次

数据结构算法之二分搜索树
Go语言数据结构和算法-BinarySearchTree(二叉搜
day17_选择排序_数组的搜索算法
算法草稿
无标题文章
数据结构之二叉堆、堆排序
手敲数据结构——使用二分搜索树实现Set
1-3 课程的注意事项
数据结构与算法--深度和广度优先搜索
AVL 树

定义

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

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);
    }