Giả sử chúng ta có một cây nhị phân. Ta phải duyệt cây theo thứ tự cấp độ (level order). Ví dụ cây:
Thứ tự duyệt: [10, 5, 16, 8, 15, 20, 23]
Để giải quyết, ta làm theo các bước:
- định nghĩa hàng đợi que lưu nút
- thêm root vào que
- while que không rỗng
- item := phần tử ở đầu hàng đợi
- in giá trị item
- nếu left của item không null, thêm left vào que
- nếu right của item không null, thêm right vào que
- xóa phần tử đầu que
Ví dụ (C++)
Hãy xem triển khai sau:
#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; //khởi tạo 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; //tạo nút mới động new_node->h_left = 0; new_node->h_right = 0; new_node->bf = 0; new_node->value = key; //lưu giá trị từ 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); //thêm root trước while(!que.empty()){ item = que.front(); //lấy phần tử đầu cout << item->value << " "; if(item->left != NULL) //khi có con trái, thêm vào queue que.push(item->left); if(item->right != NULL) //khi có con phải, thêm vào queue que.push(item->right); que.pop(); //xóa phần tử khỏi queue } } node *tree::insert_node(node *root, int key){ if(root == NULL){ return (get_node(key)); //khi cây rỗng, tạo nút làm root } if(key < root->value){ //key nhỏ hơn root, đi trái root->left = insert_node(root->left, key); } else if(key > root->value){ //key lớn hơn root, đi phải root->right = insert_node(root->right, key); } return root; //key đã có, không chèn lại } main(){ node *root; tree my_tree; //Chèn một số khóa vào cây. 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 << "Duyệt theo cấp độ: "; my_tree.levelorder_traversal(my_tree.root); }Input
[10,5,16,null,8,15,20,null,null,null,null,null,null,null,23]
Output
Duyệt theo cấp độ: 10 5 16 8 15 20 23