交付查插删中序一起验收

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

这是这条路线的最终作品。把 BST 写完整（insert / contains / inorder / erase，外加析构时释放全部节点），然后一次验完五条：插完五个数，中序是 5 个；contains(23) 为真、contains(20) 为假；中序是 13、15、17、23、24；删掉叶子 13 之后中序第一个是 15；再删掉有两个孩子的 17 之后中序是 15、23、24。五条全过输出 验收通过，否则输出 验收失败。

（本题用 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); }

bool contains(int val) const {
        // TODO: 从 root 出发，比当前小往左、大往右，相等就返回 true
        return false;
    }

static BNode* del(BNode* node, int val) {
        // TODO: 找到 val：叶子直接删、一个孩子让孩子顶上、两个孩子用右子树最小值替换（删掉的节点要 delete）
        return node;
    }

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

static void walk(BNode* node, vector<int>& out) {
        // TODO: 中序遍历：左、自己、右，把值依次放进 out
    }

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

static void free_all(BNode* node) {
        if (node == nullptr) return;
        free_all(node->left);
        free_all(node->right);
        delete node;
    }

~BST() { free_all(root); }
};

int main() {
    BST t;
    for (int v : {17, 24, 15, 13, 23}) t.insert(v);
    bool ok = t.inorder().size() == 5;
    ok = ok && t.contains(23) && !t.contains(20);
    ok = ok && t.inorder() == vector<int>{13, 15, 17, 23, 24};
    t.erase(13);
    ok = ok && t.inorder().front() == 15;
    t.erase(17);
    ok = ok && t.inorder() == vector<int>{15, 23, 24};
    cout << (ok ? "验收通过" : "验收失败") << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

交付查插删中序一起验收

更多题目

全部评论