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

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

ในที่นี้ เราจะได้รับระดับต่ำ (Low Level) และระดับสูง (High Level) สำหรับต้นไม้แบบทวิภาคเฉพาะเจาะจง และเราต้องพิมพ์สมาชิกทั้งหมดระหว่างระดับที่กำหนด

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

เราสามารถใช้การท่องระดับแบบคิว (Queue-based Level Traversal) ขณะเคลื่อนที่ผ่านการท่องอินออร์เดอร์ (Inorder) เราสามารถมีโหนดทำเครื่องหมาย (Marking Node) ที่จุดสิ้นสุดของแต่ละระดับ จากนั้นเราสามารถไปยังแต่ละระดับและพิมพ์โหนดของมันหากโหนดทำเครื่องหมายอยู่ระหว่างระดับที่กำหนด

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

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

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

// ฟังก์ชันพิมพ์โหนดระหว่างระดับ
void print_nodes(Node* root, int low, int high) {
    queue <Node *> Q;
    // สร้างโหนดทำเครื่องหมาย
    Node *marker = new Node;
    int level = 1;
    Q.push(root);
    Q.push(marker);

    while (Q.empty() == false) {
        Node *n = Q.front();
        Q.pop();

        // ตรวจสอบจุดสิ้นสุดของระดับ
        if (n == marker) {
            cout << endl;
            level++;
            if (Q.empty() == true || level > high)
                break;
            Q.push(marker);
            continue;
        }

        if (level >= low)
            cout << n->data << " ";

        if (n->left != NULL) Q.push(n->left);
        if (n->right != NULL) Q.push(n->right);
    }
}

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

int main() {
    struct Node *root = create_node(20);
    root->left = create_node(8);
    root->right = create_node(22);
    root->left->left = create_node(4);
    root->left->right = create_node(12);
    root->left->right->left = create_node(10);
    root->left->right->right = create_node(14);
    cout << "Elements between the given levels are :";
    print_nodes(root, 2, 3);
    return 0;
}

ผลลัพธ์

Elements between the given levels are : 8 22 4 12