Model sudah ada. Sekarang kita mengubahnya menjadi grid karakter. Strategi umum untuk setiap struktur sama: hitung dimensi (baris × kolom), alokasikan std::vector<std::string> berisi spasi, lalu tulis karakter pada koordinat yang dihitung. Setelah selesai, cetak seluruh grid baris demi baris. Pola ini menghindari kebutuhan akan API moveCursor yang tidak portabel di terminal Unix maupun Windows.

Renderer Linked List #

Linked list adalah kasus paling sederhana: satu baris saja yang berisi node [a] -> [b] -> ... -> null. Kita bangun satu string dengan loop:

cpp 
#include <iostream>
#include <vector>
#include <string>

std::vector<std::string> renderList(const std::vector<std::string>& values) {
    std::string line;
    for (size_t i = 0; i < values.size(); ++i) {
        line += "[" + values[i] + "]";
        line += (i + 1 == values.size()) ? " -> null" : " -> ";
    }
    return { line };
}

Renderer Graph (Adjacency List) #

Graph di-render sebagai beberapa baris, satu baris per node. Format u -> v1, v2, ...:

cpp 
std::vector<std::string> renderGraph(
        const std::unordered_map<int, std::vector<int>>& adj, int n) {
    std::vector<std::string> lines;
    for (int u = 0; u < n; ++u) {
        std::string line = std::to_string(u) + " -> ";
        const auto& nbrs = adj.at(u);
        for (size_t i = 0; i < nbrs.size(); ++i) {
            line += std::to_string(nbrs[i]);
            line += (i + 1 == nbrs.size()) ? "" : ", ";
        }
        lines.push_back(line);
    }
    return lines;
}

Renderer Binary Tree (In-Order Layout) #

Ini bagian yang paling menantang. Kita menggunakan pendekatan rekursif dengan ide berikut:

  1. Hitung lebar setiap sub-tree dengan traversal in-order — setiap node mendapat satu slot kolom, dan anak-anaknya menempati kolom di kiri dan kanan.
  2. Hitung kedalaman tree untuk menentukan jumlah baris. Untuk tree setinggi h, kita butuh 2*h - 1 baris (node baris + edge baris berselang-seling).
  3. Alokasikan grid berisi spasi.
  4. Lakukan traversal pre-order untuk menulis label node dan karakter edge /\.

Kode Lengkap Bagian 3 #

Berikut program yang memadukan ketiga renderer. Untuk tree, kita pakai algoritma dua pass: pass pertama menghitung posisi kolom tiap node, pass kedua menulis ke grid.

cpp 
#include <algorithm>
#include <iostream>
#include <memory>
#include <string>
#include <unordered_map>
#include <vector>

struct TreeNode {
    std::string label;
    std::unique_ptr<TreeNode> left;
    std::unique_ptr<TreeNode> right;
    explicit TreeNode(std::string l) : label(std::move(l)) {}
};
using NodePtr = std::unique_ptr<TreeNode>;

NodePtr node(std::string label, NodePtr l = nullptr, NodePtr r = nullptr) {
    auto n = std::make_unique<TreeNode>(std::move(label));
    n->left  = std::move(l);
    n->right = std::move(r);
    return n;
}

// Hitung kedalaman tree.
int treeHeight(const TreeNode* p) {
    if (!p) return 0;
    return 1 + std::max(treeHeight(p->left.get()), treeHeight(p->right.get()));
}

// Pass 1: beri setiap node posisi kolom memakai in-order index.
void assignColumns(const TreeNode* p, int& col,
        std::vector<std::pair<const TreeNode*, int>>& positions) {
    if (!p) return;
    assignColumns(p->left.get(), col, positions);
    positions.push_back({p, col++});
    assignColumns(p->right.get(), col, positions);
}

// Pass 2: tulis node dan edge ke grid secara rekursif (pre-order).
void drawNode(const TreeNode* p, int depth, int nodeCol,
        std::vector<std::pair<const TreeNode*, int>>& positions,
        std::vector<std::string>& grid, int colUnit) {
    if (!p) return;
    int row = depth * 2;
    int col = nodeCol * colUnit;
    std::string lbl = "[" + p->label + "]";
    for (size_t i = 0; i < lbl.size(); ++i) {
        grid[row][col + i] = lbl[i];
    }
    if (p->left) {
        int lc = -1;
        for (auto& pr : positions) if (pr.first == p->left.get()) { lc = pr.second; break; }
        int midRow = row + 1;
        // Satu karakter '/' di kolom tengah antara parent dan left child.
        int slashCol = (col + lc * colUnit) / 2;
        if (slashCol >= 0) grid[midRow][slashCol] = '/';
        drawNode(p->left.get(), depth + 1, lc, positions, grid, colUnit);
    }
    if (p->right) {
        int rc = -1;
        for (auto& pr : positions) if (pr.first == p->right.get()) { rc = pr.second; break; }
        int midRow = row + 1;
        // Satu karakter '\' di kolom tengah antara parent dan right child.
        int slashCol = (col + rc * colUnit) / 2;
        if (slashCol < (int)grid[midRow].size()) grid[midRow][slashCol] = '\\';
        drawNode(p->right.get(), depth + 1, rc, positions, grid, colUnit);
    }
}

std::vector<std::string> renderTree(const TreeNode* root) {
    if (!root) return { "<empty tree>" };
    int col = 0;
    std::vector<std::pair<const TreeNode*, int>> positions;
    assignColumns(root, col, positions);
    int nNodes = (int)positions.size();
    int colUnit = 4;
    int width = std::max(1, nNodes * colUnit);
    int h = treeHeight(root);
    int rows = std::max(1, 2 * h - 1);
    std::vector<std::string> grid(rows, std::string(width, ' '));
    int rootCol = 0;
    for (auto& pr : positions) if (pr.first == root) { rootCol = pr.second; break; }
    drawNode(root, 0, rootCol, positions, grid, colUnit);
    // Trim trailing spaces.
    for (auto& line : grid) {
        while (!line.empty() && line.back() == ' ') line.pop_back();
    }
    return grid;
}

std::vector<std::string> renderList(const std::vector<std::string>& values) {
    std::string line;
    for (size_t i = 0; i < values.size(); ++i) {
        line += "[" + values[i] + "]";
        line += (i + 1 == values.size()) ? " -> null" : " -> ";
    }
    return { line };
}

std::vector<std::string> renderGraph(
        const std::unordered_map<int, std::vector<int>>& adj, int n) {
    std::vector<std::string> lines;
    for (int u = 0; u < n; ++u) {
        std::string line = std::to_string(u) + " -> ";
        const auto& nbrs = adj.at(u);
        for (size_t i = 0; i < nbrs.size(); ++i) {
            line += std::to_string(nbrs[i]);
            line += (i + 1 == nbrs.size()) ? "" : ", ";
        }
        lines.push_back(line);
    }
    return lines;
}

void printLines(const std::vector<std::string>& lines) {
    for (const auto& l : lines) std::cout << l << "\n";
}

int main() {
    std::vector<std::string> listVals = {"a", "b", "c", "d"};
    std::cout << "== Linked List ==\n";
    printLines(renderList(listVals));

    auto tree = node("1",
        node("2", node("4"), node("5")),
        node("3", node("6"), node("7"))
    );
    std::cout << "\n== Binary Tree ==\n";
    printLines(renderTree(tree.get()));

    std::unordered_map<int, std::vector<int>> adj;
    adj[0] = {1, 2};
    adj[1] = {2};
    adj[2] = {0};
    std::cout << "\n== Graph ==\n";
    printLines(renderGraph(adj, 3));
    return 0;
}

Output yang Dihasilkan:

text 
== Linked List ==
[a] -> [b] -> [c] -> [d] -> null

== Binary Tree ==
            [1]
        /       \
    [2]             [3]
  /   \           /   \
[4]     [5]     [6]     [7]

== Graph ==
0 -> 1, 2
1 -> 2
2 -> 0

Bedah Baris Penting #

  1. assignColumns(): traversal in-order memberi setiap node nomor kolom berurutan 0, 1, 2, .... In-order dipilih karena menjamin anak kiri selalu dapat kolom lebih kecil dari parent, dan anak kanan dapat kolom lebih besar — persis seperti yang diharapkan tampilan tree.
  2. colUnit = 4: setiap slot kolom dialokasikan 4 karakter, memberi ruang untuk label [N] (3 karakter) plus spasi pemisah. Bila label lebih panjang dari 1 karakter, perlu skala lebih besar — ini batasan yang akan kita uji pada Bagian 4.
  3. grid[row][col + i] = lbl[i]: menulis karakter label satu per satu ke sel grid. Karena grid sudah diisi spasi sebelumnya, karakter yang tidak ditulis tetap menjadi spasi — tidak perlu menggambar spasi eksplisit.
  4. int slashCol = (col + lc * colUnit) / 2: edge digambar sebagai satu karakter / atau \ pada kolom tengah antara parent dan child. Pendekatan ini menghasilkan tree yang ramping tanpa deretan karakter berulang; bayangan /\ langsung terbaca sebagai percabangan.
  5. Trim trailing spaces: setelah semua sel ditulis, kita memangkas spasi di akhir setiap baris agar output tidak berisi trailing whitespace yang tidak perlu dan menyulitkan perbandingan pada test.

Kompilasi dan Pengujian #

bash 
g++ -std=c++17 -O2 -Wall -Wextra -o render.bin render.cpp
./render.bin

Pastikan output persis sama dengan blok di atas. Pada Bagian 4 kita menguji kasus edge yang akan menyingkap kelemahan renderer ini.