Binary Tree Level Order Traversal - การท่องระดับใน C++

ภาพรวมปัญหา

ท่อง Binary Tree แบบ Level Order (BFS) - ระดับต่อระดับ จากซ้ายไปขวา

ตัวอย่าง: [10, 5, 16, 8, 15, 20, 23]

อัลกอริทึม (Queue)

1. สร้าง queue, ใส่ root เข้าไป
2. while queue ไม่ว่าง:
   • item = pop front
   • พิมพ์ค่า item
   • ถ้ามี left child → push เข้า queue
   • ถ้ามี right child → push เข้า queue

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

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

class node{
public:
    int h_left, h_right, bf, value;
    node *left, *right;
};

class tree{
private:
    node *get_node(int key);
public:
    node *root;
    tree(){ root = NULL; }
    void levelorder_traversal(node *r);
    node *insert_node(node *root, int key);
};

node *tree::get_node(int key){
    node *new_node = new node;
    new_node->h_left = 0; new_node->h_right = 0;
    new_node->bf = 0; new_node->value = key;
    new_node->left = NULL; new_node->right = NULL;
    return new_node;
}

void tree::levelorder_traversal(node *root){
    queue <node*> que;
    node *item;
    que.push(root);
    while(!que.empty()){
        item = que.front();
        cout << item->value << " ";
        if(item->left != NULL) que.push(item->left);
        if(item->right != NULL) que.push(item->right);
        que.pop();
    }
}

node *tree::insert_node(node *root, int key){
    if(root == NULL) return (get_node(key));
    if(key < root->value) root->left = insert_node(root->left, key);
    else if(key > root->value) root->right = insert_node(root->right, key);
    return root;
}

int main(){
    node *root;
    tree my_tree;
    my_tree.root = my_tree.insert_node(my_tree.root, 10);
    my_tree.root = my_tree.insert_node(my_tree.root, 5);
    my_tree.root = my_tree.insert_node(my_tree.root, 16);
    my_tree.root = my_tree.insert_node(my_tree.root, 20);
    my_tree.root = my_tree.insert_node(my_tree.root, 15);
    my_tree.root = my_tree.insert_node(my_tree.root, 8);
    my_tree.root = my_tree.insert_node(my_tree.root, 23);
    cout << "Level-Order Traversal: ";
    my_tree.levelorder_traversal(my_tree.root);
}

Input / Output

Input:  [10,5,16,null,8,15,20,null,null,null,null,null,null,null,23]
Output: Level-Order Traversal: 10 5 16 8 15 20 23