พิมพ์ Level Order Traversal แบบบรรทัดต่อบรรทัดใน C++

กำหนด Binary Tree ฟังก์ชันต้องหา Level Order Traversal ของต้นไม้แบบบรรทัดต่อบรรทัด (line by line)

Level Order Traversal: ซ้าย-ราก-ขวา (Left Root Right) หมายถึงพิมพ์ลูกซ้ายของโหนดก่อน แล้วค่าของราก แล้วไปลูกขวา แต่ที่นี่เราต้องทำแบบบรรทัดต่อบรรทัด เริ่มจากซ้ายจนถึงขวาของ Binary Tree ที่กำหนด

Binary Tree ข้างต้นจะสร้างผลลัพธ์ดังนี้:

Level 0: 3
Level 1: 2 1
Level 2: 10 20 30

อัลกอริทึม

START
ขั้นตอนที่ 1: สร้างโครงสร้างโหนด struct node { node *left, *right; int data; }
ขั้นตอนที่ 2: ฟังก์ชันสร้างโหนด newnode(int data)
ขั้นตอนที่ 3: ฟังก์ชัน inorder traversal levelorder(node *root)
    ถ้า root = NULL Return
    queue<node *> que, que.push(root)
    Loop While que.empty() == false
        int count = que.size()
        Loop While count > 0
            node *node = que.front()
            พิมพ์ node->data
            que.pop()
            ถ้า node->left != NULL que.push(node->left)
            ถ้า node->right != NULL que.push(node->right)
            ลด count ลง 1
        End
    End
ขั้นตอนที่ 4: ใน main() สร้างต้นไม้ เรียก levelorder(root)
STOP

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

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

struct node {
    struct node *left;
    int data;
    struct node *right;
};

void levelorder(node *root) {
    if (root == NULL)
        return;
    queue<node *> que;
    que.push(root);
    while (que.empty() == false) {
        int count = que.size();
        while (count > 0) {
            node *node = que.front();
            cout << node->data << " ";
            que.pop();
            if (node->left != NULL)
                que.push(node->left);
            if (node->right != NULL)
                que.push(node->right);
            count--;
        }
    }
}

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

int main() {
    node *root = newnode(3);
    root->left = newnode(2);
    root->right = newnode(1);
    root->left->left = newnode(10);
    root->left->right = newnode(20);
    root->right->right = newnode(30);
    levelorder(root);
    return 0;
}

ผลลัพธ์

3 2 1 10 20 30