In Tất Cả Nút Phao (Internal Nodes) Của 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à phải in tất cả các nút phao (internal nodes) của cây.

Cây nhị phân là cây mà mỗi nút có tối đa 2 nút con. Nút có thể không có con, có 1 con hoặc 2 con.

Ví dụ:

Nút phao (Internal Node) là nút có ít nhất một con, tức là nút không phải lá.

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

Đầu ra – 7 4 9

Để giải quyết, ta duyệt cây nhị phân bằng BFS (duyệt theo chiều rộng).

Trong quá trình duyệt, ta đẩy nút vào hàng đợi. Khi lấy phần tử từ hàng đợi, in tất cả nút không phải lá (có ít nhất một con).

Ví Dụ

Mã triển khai logic:

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int data) {
        left = right = NULL;
        this->data = data;
    }
};

void printNonLeafNodes(Node* root) {
    queue<Node*> treeNodes;
    treeNodes.push(root);
    while (!treeNodes.empty()) {
        Node* curr = treeNodes.front();
        treeNodes.pop();
        bool isInternal = 0;
        if (curr->left) {
            isInternal = 1;
            treeNodes.push(curr->left);
        }
        if (curr->right) {
            isInternal = 1;
            treeNodes.push(curr->right);
        }
        if (isInternal)
            cout << curr->data << "\t";
    }
}

int main() {
    Node* root = new Node(43);
    root->left = new Node(12);
    root->right = new Node(78);
    root->left->left = new Node(4);
    root->right->left = new Node(9);
    root->right->right = new Node(1);
    root->right->right->right = new Node(50);
    root->right->right->left = new Node(25);
    cout << "Tất cả nút phao của cây nhị phân là:\n";
    printNonLeafNodes(root);
    return 0;
}

Đầu Ra

Tất cả nút phao của cây nhị phân là: 43 12 78 1