In Tất Cả Nút Giữa Hai Mức Cho Trước Trong Cây Nhị Phân Trong C++

Trong bài toán này, chúng ta được cho một cây nhị phân và hai mức trong cây (trên và dưới) và phải in tất cả nút giữa mức trên và mức dưới của cây.

Cây nhị phân là cây đặc biệt mà mỗi nút có tối đa 2 nút con.

Ví dụ để hiểu vấn đề:

mức trên – 1

mức dưới – 3

Đầu ra:

6 3 9 7 4 8 10

Để giải quyết, ta in nút của cây tại một mức cho trước. Gọi hàm đệ quy trong vòng lặp từ mức trên đến mức dưới.

Thuật toán đơn giản nhưng độ phức tạp O(n²).

Giải pháp hiệu quả hơn: duyệt inorder dùng hàng đợi (queue). In nút trong khoảng mức trên và mức dưới.

Ví Dụ

Chương trình triển khai giải pháp:

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

struct Node {
    int key;
    struct Node* left, *right;
};

void printNodesAtLevel(Node* root, int low, int high) {
    queue<Node*> Q;
    Node* marker = new Node;
    int level = 1;
    Q.push(root);
    Q.push(marker);
    while (!Q.empty()) {
        Node* n = Q.front();
        Q.pop();
        if (n == marker) {
            cout << endl;
            level++;
            if (Q.empty() || level > high) break;
            Q.push(marker);
            continue;
        }
        if (level >= low)
            cout << n->key << " ";
        if (n->left != NULL) Q.push(n->left);
        if (n->right != NULL) Q.push(n->right);
    }
}

Node* insertNode(int key) {
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}

int main() {
    struct Node* root = insertNode(6);
    root->left = insertNode(3);
    root->right = insertNode(9);
    root->left->left = insertNode(7);
    root->left->right = insertNode(4);
    root->left->right->left = insertNode(8);
    root->left->right->right = insertNode(10);
    root->left->right->right->left = insertNode(5);
    root->left->right->right->right = insertNode(1);
    root->left->right->left->left = insertNode(14);
    root->left->right->left->right = insertNode(26);
    int upper = 3;
    int lower = 1;
    cout << "Các nút theo mức giữa mức " << lower << " và " << upper << " là:\n";
    printNodesAtLevel(root, lower, upper);
    return 0;
}

Đầu Ra

Các nút theo mức giữa mức 1 và 3 là: 6 3 9 7 4