二叉搜索树 C++实现代码

#include<iostream>
#include<cassert>
#include<queue>
using namespace std;
//二叉搜索树 类似于字典  主要功能增 删 改 查 遍历
template<typename Key,typename Value>
class BST {
private:
    //定义基本成员 结点，结点属性，总的结点数
    struct Node {
        Key key;
        Value value;
        Node* left;
        Node* right;

        Node(Key key, Value value) {
            this->key = key;
            this->value = value;
            this->left = this->right = NULL;
        }
        Node(Node* node) {
            this->key = node->key;
            this->value = node->value;
            this->left = node->left;
            this->right = node->right;
        }
    };
    Node* root;
    int count;
public:
    BST() {
        root = NULL;
        count = 0;
    }
    ~BST() {
        destroy(root);
    }
    int Size() {
        return count;
    }
    bool empty() {
        return count == 0;
    }
    //增
    void insert(Key key, Value value) {
        root = insert(root, key, value);
    }

    //删
    //查找最小的键值
    Key minkey() {
        assert(count != 0);
        Node* minNode = minkey(root);
        return minNode->key;
    }
    //查找最大键值
    Key maxkey() {
        assert(count != 0);
        Node* maxNode = maxkey(root);
        return maxNode->key;
    }
    //删除最小的键值
    void removeMin() {
        root = removeMin(root);
    }
    //删除最大的键值
    void removeMax() {
        root = removeMax(root);
    }
    //删除任意键值
    void remove(Key key) {
        root = remove(root, key);
    }

    //改
    bool modify(Key key, Value value) {
        return modify(root, key, value);
    }
    //查
    //查找某一个键值是否存在
    bool contain(Key key) {
        return contain(root, key);
    }
    //查找任意一个键值的value值
    Value* search(Key key) {
        return search(root, key);
    }
    //前序遍历
    void preOrder() {
        preOrder(root);
    }
    //中序遍历
    void midOrder() {
        midOrder(root);
    }
    //后序遍历
    void lastOrder() {
        lastOrder(root);
    }
    //层序遍历
    void levelOrder() {
        queue<Node*>q;
        q.push(root);
        while (!q.empty()) {
            Node* node = q.front();
            q.pop();
            cout << node->key << "  ";
            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
        }
    }
    //析构函数释放空间
    void destroy(Node* node) {
        if (node != NULL) {
            destroy(node->left);
            destroy(node->right);
            delete node;
            count--;
        }
    }

private:
    //增
    Node* insert(Node* node, Key key, Value value) {
        if (node == NULL) {
            count++;
            return new Node(key, value);
        }

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

    //删
    //查找最小的键值
    Node* minkey(Node* node) {
        if (node->left)
            return minkey(node->left);
        else
            return node;
    }
    //查找最大的键值
    Node* maxkey(Node* node) {
        if (node->right)
            return maxkey(node->right);
        else
            return node;
    }
    //删除最小的键值
    Node* removeMin(Node* node) {
        if (node->left == NULL) {
            Node* rightNode = node->right;
            count--;
            delete node;
            return rightNode;
        }
        node->left = removeMin(node->left);
        return node;
    }
    //删除最大的键值
    Node* removeMax(Node* node) {
        if (node->right == NULL) {
            Node* leftNode = node->left;
            count--;
            delete node;
            return leftNode;
        }
        node->right = removeMax(node->right);
        return node;
    }
    //删除任意一个键值
    Node* remove(Node* node, Key key) {
        if (node == NULL)
            return NULL;
        if (key < node->key) {
            node->left = remove(node->left,key);
            return node;
        }
        else if (key > node->key) {
            node->right = remove(node->right,key);
            return node;
        }
        else {
            //key==node->key
            if (node->left == NULL) {
                Node* rightNode = node->right;
                count--;
                delete node;
                return rightNode;
            }
            else if (node->right == NULL) {
                Node* leftNode = node->left;
                count--;
                delete node;
                return leftNode;
            }
            else {//左右子树都不为空
                Node* successor = new Node(minkey(node->right));
                count++;
                successor->right = removeMin(node->right);
                successor->left = node->left;

                delete node;
                count--;
                return successor;
            }

        }
    }

    //改
    bool modify(Node* node,Key key, Value value) {
        if (node == NULL)
            return false;
        if (key == node->key) {
            node->value = value;
            return true;
        }
        else if (key < node->key)
            return modify(node->left, key, value);
        else
            return modify(node->right, key, value);
    }


    //查
    //查找某一个键值是否存在
    bool contain(Node* node,Key key) {
        if (node == NULL)
            return false;
        if (key == node->key)
            return true;
        else if (key < node->key)
            return contain(node->left, key);
        else
            return contain(node->right, key);
    }
    //查找任意一个键值的value值
    Value* search(Node* node, Key key) {
        if (node == NULL)
            return NULL;
        if (key == node->key)
            return &(node->value);
        else if (key < node->key)
            return search(node->left, key);
        else
            return search(node->right, key);
    }

    //前序遍历
    void preOrder(Node* node) {
        if (node != NULL) {
            cout << node->key << "  ";
            preOrder(node->left);
            preOrder(node->right);
        }
    }
    //中序遍历
    void midOrder(Node* node) {
        if (node != NULL) {
            midOrder(node->left);
            cout << node->key << "  ";
            midOrder(node->right);
        }
    }
    //后序遍历
    void lastOrder(Node* node) {
        if (node != NULL) {
            lastOrder(node->left);
            lastOrder(node->right);
            cout << node->key << "  ";
        }
    }

};

int main() {
    BST<int, string>bst;
    int arr[8] = { 50,27,68,1,35,65,78,99 };
    string s[8] = { "a","b","c","d","e","f","g","h" };
    //增
    for (int i = 0; i < 8; i++) {
        bst.insert(arr[i], s[i]);
    }


    //查
    cout << "键值为50：" << bst.contain(50) << "   " << "键值为19：" << bst.contain(19) << endl;
    cout << "键值为50的value：" << *(bst.search(50)) << "   " << "键值为65：" << *(bst.search(65)) << endl;

    //改
    cout<<"是否修改成功："<<bst.modify(50, "p")<<"    ";
    cout << "键值为50的value：" << *(bst.search(50)) << endl;
    //遍历
    cout << "前序遍历：";
    bst.preOrder();
    cout << endl;
    cout << "中序遍历：";
    bst.midOrder();
    cout << endl;
    cout << "后序遍历：";
    bst.lastOrder();
    cout << endl;
    cout << "层序遍历：";
    bst.levelOrder();
    cout << endl;

    //删
    //查找最小的键值
    cout << "最小键值：" << bst.minkey() << "    " << "最大键值：" << bst.maxkey() << endl;
    //删除最小键值和最大键值的线先序遍历
    bst.removeMin();
    bst.removeMax();
    cout << "删除最小/大键值后前序遍历：";
    bst.preOrder();
    cout << endl;
    //删除指定键值之后的前序排列
    bst.remove(68);
    cout << "删除指定键值后前序遍历：";
    bst.preOrder();
    cout << endl;
    system("pause");
    return 0;
}