交付建树四种遍历和 Trie

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

这是这条路线的最终作品。把树建出来、四种遍历都写上、再写一棵 Trie，最后把整棵树释放干净，一次验完五条：节点总数是 6、叶子是 3；前序第一个是「总部」、后序最后一个也是「总部」；中序第一个是「北京」；层序第 4 个是「北京」、一共 3 层；Trie 里 card 在、ca 不在。五条全过输出 验收通过，否则输出 验收失败。

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

提交你的答案

请登录后提交答案。

去登录

← 第四步再写一棵前缀树递归太深会发生什么 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

struct TNode {
    string name;
    TNode* left = nullptr;
    TNode* right = nullptr;
};

TNode* build() {
    TNode* root = new TNode{"总部"};
    root->left = new TNode{"华北"};
    root->right = new TNode{"华南"};
    root->left->left = new TNode{"北京"};
    root->left->right = new TNode{"天津"};
    root->right->right = new TNode{"广州"};
    return root;
}

#include <map>

int count_nodes(TNode* n) { return n ? 1 + count_nodes(n->left) + count_nodes(n->right) : 0; }
int leaves(TNode* n) {
    if (!n) return 0;
    if (!n->left && !n->right) return 1;
    return leaves(n->left) + leaves(n->right);
}

vector<string> order;

void pre(TNode* n) {
    if (!n) return;
    order.push_back(n->name);
    pre(n->left);
    pre(n->right);
}

void mid(TNode* n) {
    if (!n) return;
    mid(n->left);
    order.push_back(n->name);
    mid(n->right);
}

void post(TNode* n) {
    if (!n) return;
    post(n->left);
    post(n->right);
    order.push_back(n->name);
}

string first_of(void (*walk)(TNode*), TNode* root) {
    order.clear();
    walk(root);
    return order.empty() ? "空" : order.front();
}

string last_of_post(TNode* root) {
    order.clear();
    post(root);
    return order.back();
}

vector<string> level_order(TNode* root, int& lv) {
    // TODO: 用队列一层一层地走：返回层序遍历的名字序列，并把层数写进 lv
    lv = 0;
    return {};
}

void free_tree(TNode* n) {
    if (!n) return;
    free_tree(n->left);
    free_tree(n->right);
    delete n;
}

struct Trie {
    map<char, Trie*> next;
    bool end = false;
};

void trie_insert(Trie* t, const string& w) {
    // TODO: 逐个字符往下走，孩子不存在就 new 一个，走完把 end 标成 true
}

bool trie_search(Trie* t, const string& w) {
    // TODO: 逐个字符往下走，缺了就返回 false；走完看 end
    return false;
}

int main() {
    TNode* root = build();
    int lv = 0;
    vector<string> lvl = level_order(root, lv);
    Trie* t = new Trie;
    for (const string& w : {"cat", "car", "card", "dog"}) trie_insert(t, w);
    bool ok = count_nodes(root) == 6 && leaves(root) == 3
           && first_of(pre, root) == "总部" && last_of_post(root) == "总部"
           && first_of(mid, root) == "北京"
           && lvl.size() > 3 && lvl[3] == "北京" && lv == 3
           && trie_search(t, "card") && !trie_search(t, "ca");
    free_tree(root);
    cout << (ok ? "验收通过" : "验收失败") << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

交付建树四种遍历和 Trie

更多题目

全部评论