又来学新知识啦：二叉搜索树的遍历！

#include<iostream>
#include<vector>
#include<queue>
using namespace std;


struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};






class BinarySearchTree {//定义树类
private:
    TreeNode* root;

    //查找指定树节点
    TreeNode* search(int num) {
        TreeNode* cur = root;
        while (cur != nullptr) {
            if (cur->val < num)
                cur = cur->right;
            else if (cur->val > num)
                cur = cur->left;
            else
                break;
        }
        return cur;
    }

public:
    BinarySearchTree() : root(nullptr) {}

    ~BinarySearchTree() {
        destroyTree(root);
    }

    //插入树节点
    void insert(int num) {
        if (root == nullptr) {
            root = new TreeNode(num);
            return;
        }
        TreeNode* cur = root, * pre = nullptr;//cur在前探路，
//pre在后保驾护航，以免cur找不到其父节点
        while (cur != nullptr) {//如果cur找到要入元素的位置，
//就不更新pre到他的位置，形成一前一后的状态（cur：你退后，我来！/doge）
            if (cur->val == num)
                return;
            pre = cur;
            if (cur->val < num)
                cur = cur->right;
            else
                cur = cur->left;
        }
        TreeNode* node = new TreeNode(num);
        if (pre->val < num)//选择插入节点的哪个孩子，遵循左<中<右的搜索树规则
            pre->right = node;
        else
            pre->left = node;
    }

    //删除树节点
    void remove(int num) {
        if (root == nullptr)
            return;
        TreeNode* cur = root, * pre = nullptr;
        while (cur != nullptr && cur->val != num) {//和插入元素一样，
//找到要删除的元素就形成一前一后的位置关系
            pre = cur;
            if (cur->val < num)
                cur = cur->right;
            else
                cur = cur->left;
        }

        if (cur == nullptr)//空树直接返回，因为没有节点可以删除
            return;


        // 子节点数量 = 0 or 1
        if (cur->left == nullptr || cur->right == nullptr) {
            TreeNode* child = cur->left != nullptr ? cur->left : cur->right;
//指向要删除节点的孩子节点，孩子是无辜的，所以要保护它
            if (cur != root) {
                if (pre->left == cur)
                    pre->left = child;
                else
                    pre->right = child;
            }
            else {
                root = child;
            }
            delete cur;
        }



        // 子节点数量 = 2
        //两种方案
        //1.用左树的最右边（最大那个）来代替要实现删除的的节点
        //2.用右树的最左边（最小那个）来代替要实现删除的的节点
        //这里采用方案2
        else {
            //用右树的最左边
            TreeNode* tmp = cur->right;
            TreeNode* parent = cur;
            while (tmp->left != nullptr) {
                parent = tmp;
                tmp = tmp->left;
            }
            //执行替换操作
            int tmpVal = tmp->val;
            remove(tmpVal);
            cur->val = tmpVal;
        }
    }

    //广度优先搜索二叉搜索树，返回搜索到的树节点值，用vector容器储存
    vector<int> levelOrder() {
        vector<int> vec;
        if (!root)//如果根节点为空，直接返回，因为树里面没有节点
            return vec;
        //使用队列，先进先出（深搜则无需使用）
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            vec.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        return vec;
    }


    //析构函数，用于释放new的空间
    void destroyTree(TreeNode* node) {
        if (node != nullptr) {
            destroyTree(node->left);
            destroyTree(node->right);
            delete node;
        }
    }
};



int main() {
    //定义一颗树成员
    BinarySearchTree bst;
    //构建树
    bst.insert(1);
    bst.insert(2);
    bst.insert(3);
    bst.insert(4);
    bst.insert(5);
    //广度优先遍历删除前的二叉搜索树
    vector<int> result = bst.levelOrder();
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;
    //删除操作
    int deletenum;
    cout << "输入你要删除的节点值（输入-1结束）：" << endl;
    while (cin >> deletenum && deletenum != -1) //实现多次删除
    {
        bst.remove(deletenum);
        //广度优先遍历删除后的二叉搜索树
       vector<int> result1 = bst.levelOrder();
        for (int val : result1) {
            cout << val << " ";
        }
        cout << endl;
    }

    return 0;
}