第四步接上删除

👁️ 0 人浏览 💬 0 人评论 ❤️ 添加收藏

加上 erase（删下来的节点要 delete），删掉有两个孩子的根 17，然后中序走一遍，把剩下的拼起来输出。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 第三步接上中序交付查插删中序一起验收 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

struct BNode {
    int val;
    BNode* left = nullptr;
    BNode* right = nullptr;
};

struct BST {
    BNode* root = nullptr;

static BNode* ins(BNode* node, int val) {
        if (node == nullptr) return new BNode{val};
        if (val < node->val) node->left = ins(node->left, val);
        else if (val > node->val) node->right = ins(node->right, val);
        return node;
    }

void insert(int val) { root = ins(root, val); }

static BNode* del(BNode* node, int val) {
        if (node == nullptr) return nullptr;
        if (val < node->val) {
            node->left = del(node->left, val);
        } else if (val > node->val) {
            node->right = del(node->right, val);
        } else {
            // TODO: 最多一个孩子：记下孩子、delete node、返回孩子
            // TODO: 两个孩子：抄右子树最小值上来，再去右子树里删掉它
        }
        return node;
    }

void erase(int val) { root = del(root, val); }

static void walk(BNode* node, vector<int>& out) {
        if (node == nullptr) return;
        walk(node->left, out);
        out.push_back(node->val);
        walk(node->right, out);
    }

vector<int> inorder() const {
        vector<int> out;
        walk(root, out);
        return out;
    }
};

string join(const vector<int>& v) {
    string s;
    for (size_t i = 0; i < v.size(); i++) s += (i ? "/" : "") + to_string(v[i]);
    return s;
}

int main() {
    BST t;
    for (int v : {17, 24, 15, 13, 23}) t.insert(v);
    t.erase(17);
    cout << join(t.inorder()) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

第四步接上删除

更多题目

全部评论