Cho cây nhị phân, in cấp độ của mỗi khóa trong nút, cấp độ bắt đầu từ 1.
Trong cây trên:
10 ở cấp 1 3 và 211 ở cấp 2 140, 162, 100, 146 ở cấp 3
Cho khóa, in cấp độ của khóa đó.
Ví dụ
Input: 10 3 211 140 162 100 146
Output:
cấp của 10 là 1
cấp của 3 là 2
cấp của 211 là 2
cấp của 140 là 3
cấp của 162 là 3
cấp của 100 là 3
cấp của 146 là 3 Thuật toán
BẮT ĐẦU
BƯỚC 1: CẤU TRÚC NÚT: struct node { node *left, *right; int data; }
BƯỚC 2: HÀM TẠO NÚT newnode(int data)
BƯỚC 3: HÀM TÌM CẤP ĐỘ levels(Node* root)
NẾU root==NULL TRẢ VỀ
TẠO queue<pair<Node*, int> > que, que.push({root, 1})
TẠO pair<Node*, int> par
WHILE !que.empty()
par = que.front(); que.pop()
IN par.first->data VÀ par.second
NẾU par.first->left que.push({par.first->left, par.second+1})
NẾU par.first->right que.push({par.first->right, par.second+1})
KẾT THÚC Ví dụ mã C++
#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 << "Cấp của " << par.first->data << " là " << 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;
} Kết quả
Chạy chương trình cho kết quả:
Cấp của 34 là 1 Cấp của 12 là 2 Cấp của 50 là 2 Cấp của 11 là 3 Cấp của 54 là 3