学习建议

先备份源代码。

将某个函数删除，按自己的理解实现。

测试，并对比差异。

代码

#pragma once
#include <algorithm>
#include <cstdint>
#include <functional>
#include <optional>
#include <queue>

namespace ds {
    template<typename T>
    class BinarySearchTree;

    template<typename T>
    class BinarySearchTreeNode {
    public:
        friend class BinarySearchTree<T>;//直接访问节点元素

    public:
        BinarySearchTreeNode() = default;

        explicit BinarySearchTreeNode(const T& key) : key_(key) {}
        //固定写法：不允许常量引用 引用的引用
        BinarySearchTreeNode(const BinarySearchTreeNode&) = delete;
        BinarySearchTreeNode(BinarySearchTreeNode&&) = delete;
        BinarySearchTreeNode& operator=(const BinarySearchTreeNode&) = delete;
        BinarySearchTreeNode& operator=(BinarySearchTreeNode&&) = delete;

        ~BinarySearchTreeNode() = default;
        T key_;

    private:
        BinarySearchTreeNode* left_{ nullptr };
        BinarySearchTreeNode* right_{ nullptr };
        int height_{ 1 };
    };

    template<typename T>
    class BinarySearchTree {
    public:
        using callback_t = std::function<void(const T&)>;//定义visit函数

    public:
        BinarySearchTree() = default;
        BinarySearchTree(std::initializer_list<T> keys);

        //一样的
        BinarySearchTree(const BinarySearchTree&) = delete;
        BinarySearchTree(BinarySearchTree&&) = delete;
        ~BinarySearchTree();
        BinarySearchTree& operator=(const BinarySearchTree&) = delete;
        BinarySearchTree& operator=(BinarySearchTree&&) = delete;

        //基本遍历
        void pre_order_traversal(callback_t callback);
        void in_order_traversal(callback_t callback);
        void post_order_traversal(callback_t callback);
        void level_order_traversal(callback_t callback);

        //主要功能
        void insert(const T& key);
        template<typename U>
        void remove(const U& key);
        template<typename U>
        auto search(const U& key);
        auto minimum();
        auto maximum();
        auto height();
        auto size();
        void clear();

    private:
        //helper 使用指针，方便进行递归
        void pre_order_traversal_helper(BinarySearchTreeNode<T>* root, callback_t callback);
        void in_order_traversal_helper(BinarySearchTreeNode<T>* root, callback_t callback);
        void post_order_traversal_helper(BinarySearchTreeNode<T>* root, callback_t callback);
        void breadth_first_traversal_helper(BinarySearchTreeNode<T>* root, callback_t callback);

        BinarySearchTreeNode<T>* insert_helper(BinarySearchTreeNode<T>* root, const T& key);
        template<typename U>
        BinarySearchTreeNode<T>* remove_helper(BinarySearchTreeNode<T>* root, const U& key);
        template<typename U>
        BinarySearchTreeNode<T>* search_helper(BinarySearchTreeNode<T>* root, const U& key);


        BinarySearchTreeNode<T>* minimum_helper(BinarySearchTreeNode<T>* root);
        BinarySearchTreeNode<T>* maximum_helper(BinarySearchTreeNode<T>* root);
        auto height_helper(const BinarySearchTreeNode<T>* root);
        auto size_helper(const BinarySearchTreeNode<T>* root);
        void clear_helper(BinarySearchTreeNode<T>* root);
        BinarySearchTreeNode<T>* root_{ nullptr };
    };

    template<typename T>
    BinarySearchTree<T>::BinarySearchTree(std::initializer_list<T> keys) {
        for (auto key : keys) {
            insert(key);
        }
    }

    template<typename T>
    BinarySearchTree<T>::~BinarySearchTree() { clear(); }

    //常见套路 公有函数不涉及指针（用户友好），而另加一个helper函数操作指针
    template<typename T>
    void BinarySearchTree<T>::pre_order_traversal(BinarySearchTree::callback_t callback) {
        pre_order_traversal_helper(root_, callback);
    }

    template<typename T>
    void BinarySearchTree<T>::in_order_traversal(BinarySearchTree::callback_t callback) {
        in_order_traversal_helper(root_, callback);
    }

    template<typename T>
    void BinarySearchTree<T>::post_order_traversal(BinarySearchTree::callback_t callback) {
        post_order_traversal_helper(root_, callback);
    }

    template<typename T>
    void BinarySearchTree<T>::level_order_traversal(BinarySearchTree::callback_t callback) {
        breadth_first_traversal_helper(root_, callback);
    }

    template<typename T>
    void BinarySearchTree<T>::insert(const T& key) { root_ = insert_helper(root_, key); }

    template<typename T>
    template<typename U>
    void BinarySearchTree<T>::remove(const U& key) {
        root_ = remove_helper(root_, key);
    }

    template<typename T>
    template<typename U>
    auto BinarySearchTree<T>::search(const U& key) {
        auto res = search_helper(root_, key);
        return res ? std::optional<std::reference_wrapper<T>>{res->key_}
        : std::nullopt;
    }

    template<typename T>
    auto BinarySearchTree<T>::minimum() {
        auto min = minimum_helper(root_);
        return min ? std::optional<std::reference_wrapper<T>>{min->key_}
        : std::nullopt;
    }

    template<typename T>
    auto BinarySearchTree<T>::maximum() {
        auto max = maximum_helper(root_);
        return max ? std::optional<std::reference_wrapper<T>>{max->key_}
        : std::nullopt;
    }

    template<typename T>
    auto BinarySearchTree<T>::height() { return height_helper(root_); }

    template<typename T>
    auto BinarySearchTree<T>::size() { return size_helper(root_); }

    template<typename T>
    void BinarySearchTree<T>::clear() {
        clear_helper(root_);
        root_ = nullptr;
    }


    //递归实现二叉树的遍历
    template<typename T>
    void BinarySearchTree<T>::pre_order_traversal_helper(BinarySearchTreeNode<T>* root,
        BinarySearchTree::callback_t callback) {
        if (!root) return;
        callback(root->key_);
        pre_order_traversal_helper(root->left_, callback);
        pre_order_traversal_helper(root->right_, callback);
    }

    template<typename T>
    void BinarySearchTree<T>::in_order_traversal_helper(BinarySearchTreeNode<T>* root,
        BinarySearchTree::callback_t callback) {
        if (!root) return;
        in_order_traversal_helper(root->left_, callback);
        callback(root->key_);
        in_order_traversal_helper(root->right_, callback);
    }

    template<typename T>
    void BinarySearchTree<T>::post_order_traversal_helper(BinarySearchTreeNode<T>* root,
        BinarySearchTree::callback_t callback) {
        if (!root) return;
        post_order_traversal_helper(root->left_, callback);
        post_order_traversal_helper(root->right_, callback);
        callback(root->key_);
    }

    //bfs
    template<typename T>
    void BinarySearchTree<T>::breadth_first_traversal_helper(BinarySearchTreeNode<T>* root,
        BinarySearchTree::callback_t callback) {
        if (!root) return;
        std::queue<BinarySearchTreeNode<T>*> queue;
        queue.push(root);
        while (!queue.empty()) {
            BinarySearchTreeNode<T>* current{ queue.front() };
            callback(current->key_);
            queue.pop();
            if (current->left_) queue.push(current->left_);
            if (current->right_) queue.push(current->right_);
        }
    }

    //保证插入数据没有重复值
    template<typename T>
    BinarySearchTreeNode<T>* BinarySearchTree<T>::insert_helper(BinarySearchTreeNode<T>* root, const T& key) {
        if (!root) return new BinarySearchTreeNode(key);
        if (key < root->key_)
            root->left_ = insert_helper(root->left_, key);
        else if (root->key_ < key)
            root->right_ = insert_helper(root->right_, key);
        root->height_ = std::max(height_helper(root->left_), height_helper(root->right_)) + 1;
        return root;
    }

    template<typename T>
    template<typename U>
    BinarySearchTreeNode<T>* BinarySearchTree<T>::remove_helper(BinarySearchTreeNode<T>* root, const U& key) {
        if (!root) return nullptr;
        if (key < root->key_)
            root->left_ = remove_helper(root->left_, key);
        else if (root->key_ < key)
            root->right_ = remove_helper(root->right_, key);
        else {
            if (!root->left_ && !root->right_) {//是叶子
                delete root;
                root = nullptr;
            }
            else if (!root->left_) {
                BinarySearchTreeNode<T>* tmp{ root };
                root = root->right_;
                delete tmp;
            }
            else if (!root->right_) {
                BinarySearchTreeNode<T>* tmp{ root };
                root = root->left_;
                delete tmp;
            }
            else {
                //左右都不空
                BinarySearchTreeNode<T>* min{ minimum_helper(root->right_) };
                root->key_ = min->key_;//最小值覆盖根节点
                root->right_ = remove_helper(root->right_, min->key_);//删除叶子
                //BinarySearchTreeNode<T> *max{maximum(root->left_)};
                //root->key_ = max->key_;
                //root->left_ = remove(root->left_, max->key_);
            }
        }

        if (!root) return nullptr;

        root->height_ = std::max(height_helper(root->left_), height_helper(root->right_)) + 1;

        return root;
    }

    template<typename T>
    template<typename U>
    BinarySearchTreeNode<T>* BinarySearchTree<T>::search_helper(BinarySearchTreeNode<T>* root, const U& key) {
        //左儿子 < 根 < 右儿子
        while (root) {
            if (root->key_ < key)
                root = root->right_;
            else if (key < root->key_)
                root = root->left_;
            else
                return root;
        }
        return nullptr;
    }

    //easy
    template<typename T>
    BinarySearchTreeNode<T>* BinarySearchTree<T>::minimum_helper(BinarySearchTreeNode<T>* root) {
        if (!root) return nullptr;
        while (root->left_) root = root->left_;
        return root;
    }

    template<typename T>
    BinarySearchTreeNode<T>* BinarySearchTree<T>::maximum_helper(BinarySearchTreeNode<T>* root) {
        if (!root) return nullptr;
        while (root->right_) root = root->right_;
        return root;
    }

    template<typename T>
    auto BinarySearchTree<T>::height_helper(const BinarySearchTreeNode<T>* root) {
        if (!root) return 0;
        return root->height_;
    }

    template<typename T>
    auto BinarySearchTree<T>::size_helper(const BinarySearchTreeNode<T>* root) {
        if (!root) return 0;
        return size_helper(root->left_) + size_helper(root->right_) + 1;
    }

    template<typename T>
    void BinarySearchTree<T>::clear_helper(BinarySearchTreeNode<T>* root) {
        if (!root) return;
        if (root->left_) clear_helper(root->left_);
        if (root->right_) clear_helper(root->right_);
        delete root;
    }
}

test

#include"BSTree.h"

#include <iostream>
#include <string>
#include <utility>

class Node {
public:
    Node() = default;
    Node(int key, std::string value) : key_(key), value_(std::move(value)) {};
    ~Node() = default;
    bool operator<(const Node& other) const { return key_ < other.key_; }
    friend bool operator<(const Node&, int);
    friend bool operator<(int, const Node&);
    friend std::ostream& operator<<(std::ostream&, const Node&);
    int key_ = 0;
    std::string value_;
};

bool operator<(const Node& lhs, const int rhs) { return lhs.key_ < rhs; }

bool operator<(const int lhs, const Node& rhs) { return lhs < rhs.key_; }

std::ostream& operator<<(std::ostream& os, const Node& node) {
    os << "(" << node.key_ << ", " << node.value_ << ")" << " _ ";
    return os;
}

int main() {
    ds::BinarySearchTree<Node> tree;

    tree.insert(Node(2, "Thor"));
    tree.insert(Node(4, "Odin"));
    tree.insert(Node(90, "Loki"));
    tree.insert(Node(3, "Baldr"));
    tree.insert(Node(0, "Frigg"));
    tree.insert(Node(14, "Eir"));
    tree.insert(Node(45, "Heimdall"));

    tree.remove(2);

    if (auto res = tree.search(2)) { std::cout << res->get() << std::endl; }

    tree.pre_order_traversal([](auto node) { std::cout << node << " "; });
    std::cout << std::endl;

    /*
    tree.in_order_traversal([](auto node) { std::cout << node << std::endl; });
    tree.post_order_traversal([](auto node) { std::cout << node << std::endl; });
    tree.level_order_traversal([](auto node) { std::cout << node << std::endl; });

    if (auto min = tree.minimum()) { std::cout << min->get() << std::endl; }
    if (auto max = tree.maximum()) { std::cout << max->get() << std::endl; }

    std::cout << tree.size() << std::endl;

    std::cout << tree.height() << std::endl;
    */
    tree.clear();

    return 0;
}