Duyệt cây Level Order (Theo cấp độ) trong cấu trúc dữ liệu

Phần này trình bày kỹ thuật duyệt level-order (theo cấp độ) cho cây tìm kiếm nhị phân.

Ví dụ cây:

Thứ tự duyệt level-order: 10, 5, 16, 8, 15, 20, 23

Thuật toán

levelOrderTraverse(root):
Begin
    define queue que
    insert root into que
    while que not empty:
        item := front of queue
        print item value
        if left of item not null: insert left into que
        if right of item not null: insert right into que
        delete front from que
    done
End

Ví dụ 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);
};

// get_node, insert_node giống bài BST

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();
    }
}

int main() {
    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);
}

Kết quả

Level-Order Traversal: 10 5 16 8 15 20 23