พิมพ์ระดับ (Level) ของทุกโหนดใน Binary Tree ด้วย C++

กำหนด Binary Tree ภารกิจคือพิมพ์ระดับที่เกี่ยวข้องกับแต่ละคีย์ที่จัดเก็บในโหนด เริ่มจาก 1 ถึง n

ในต้นไม้ข้างต้น โหนดต่างๆ คือ:

10 อยู่ระดับ 1
3 และ 211 อยู่ระดับ 2
140, 162, 100 และ 146 อยู่ระดับ 3

เมื่อได้รับคีย์ โปรแกรมต้องพิมพ์ระดับของคีย์นั้นๆ

ตัวอย่าง

Input: 10 3 211 140 162 100 146
Output:
    level of 10 is 1
    Level of 3 is 2
    Level of 211 is 2
    Level of 140 is 3
    Level of 162 is 3
    Level of 100 is 3
    Level of 146 is 3

อัลกอริทึม

START
ขั้นตอนที่ 1: สร้างโครงสร้างโหนด struct node { node *left, *right; int data; }
ขั้นตอนที่ 2: ฟังก์ชันสร้างโหนด newnode(int data)
ขั้นตอนที่ 3: ฟังก์ชันหาระดับของโหนด levels(Node* root)
    ถ้า root=NULL Return
    สร้าง queue<pair<struct Node*, int> > que
    que.push({root, 1})
    สร้าง pair<struct Node*, int> par
    Loop While !que.empty()
        par = que.front()
        que.pop()
        พิมพ์ par.first->data และ par.second
        ถ้า par.first->left que.push({par.first->left, par.second + 1})
        ถ้า par.first->right que.push({par.first->right, par.second + 1})
    End
STOP

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

#include <bits/stdc++.h>
using namespace std;

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

void levels(Node* root) {
    if (root == NULL)
        return;
    queue<pair<struct Node*, int> > que;
    que.push({root, 1});
    pair<struct Node*, int> par;
    while (!que.empty()) {
        par = que.front();
        que.pop();
        cout << "Level of " << par.first->data << " is " << par.second << "\n";
        if (par.first->left)
            que.push({par.first->left, par.second + 1});
        if (par.first->right)
            que.push({par.first->right, par.second + 1});
    }
}

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

int main() {
    Node* root = NULL;
    root = newnode(34);
    root->left = newnode(12);
    root->right = newnode(50);
    root->left->left = newnode(11);
    root->left->right = newnode(54);
    levels(root);
    return 0;
}

ผลลัพธ์

Level of 34 is 1
Level of 12 is 2
Level of 50 is 2
Level of 11 is 3
Level of 54 is 3