โปรแกรมพิมพ์โหนดในมุมมองบนสุดของต้นไม้แบบทวิภาคด้วย C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมที่พิมพ์โหนดทั้งหมดที่ปรากฏในมุมมองบนสุด (Top View) ของต้นไม้แบบทวิภาค (Binary Tree) ที่กำหนด

แนวคิดของมุมมองบนสุด

สำหรับต้นไม้แบบทวิภาค โหนดจะปรากฏในมุมมองบนสุดหากมันเป็นโหนดแรกที่ระยะแนวนอน (Horizontal Distance) นั้นๆ ระยะแนวนอนสำหรับโหนดซ้ายของโหนด x คือ x-1 และสำหรับโหนดขวาคือ x+1

วิธีการแก้ปัญหา

เราจะใช้การท่องระดับ (Level Order Traversal) เพื่อให้ได้โหนดบนสุดสำหรับระดับแนวนอนแต่ละระดับก่อนโหนดอื่นๆ นอกจากนี้ เรายังใช้แฮชแมป (Hashing) เพื่อตรวจสอบว่าโหนดที่เลือกสามารถมองเห็นได้ในมุมมองบนสุดหรือไม่

ตัวอย่างโค้ด

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

struct Node {
    Node *left;
    Node *right;
    int h_dist;
    int data;
};

Node* create_node(int key) {
    Node* node = new Node();
    node->left = node->right = NULL;
    node->data = key;
    return node;
}

void print_topview(Node* root) {
    if (root == NULL)
        return;

    queue<Node*> q;
    map<int, int> m;
    int h_dist = 0;
    root->h_dist = h_dist;
    q.push(root);

    cout << "Top View for the given tree:" << endl;

    while (q.size()) {
        h_dist = root->h_dist;
        if (m.count(h_dist) == 0)
            m[h_dist] = root->data;

        if (root->left) {
            root->left->h_dist = h_dist - 1;
            q.push(root->left);
        }
        if (root->right) {
            root->right->h_dist = h_dist + 1;
            q.push(root->right);
        }
        q.pop();
        root = q.front();
    }

    for (auto i = m.begin(); i != m.end(); i++) {
        cout << i->second << " ";
    }
}

int main() {
    Node* root = create_node(11);
    root->left = create_node(23);
    root->right = create_node(35);
    root->left->right = create_node(47);
    root->left->right->right = create_node(59);
    root->left->right->right->right = create_node(68);
    print_topview(root);
    return 0;
}

ผลลัพธ์

Top View for the given tree: 23 11 35 68