In Tất Cả Nút Đầy Đủ (Full 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. Nhiệm vụ là in tất cả các nút của cây là nút đầy đủ (full nodes).

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 đầy đủ (Full node) là nút có cả con trái và con phải. Nói cách khác, nút có cả hai con là nút đầy đủ. Trong cây trên, 4 và 9 là nút đầy đủ.

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

Đầu ra – 4 9

Cách đơn giản: duyệt cây bằng thuật toán duyệt bất kỳ. Kiểm tra nút hiện tại có cả con trái và phải không. Nếu có in giá trị nút, ngược lại bỏ qua.

Ví Dụ

Chương trình minh họa giải pháp:

#include <iostream>
using namespace std;

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

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

void printFullNode(Node* root) {
    if (root != NULL) {
        printFullNode(root->left);
        if (root->left != NULL && root->right != NULL)
            cout << root->data << "\t";
        printFullNode(root->right);
    }
}

int main() {
    Node* root = insertNode(100);
    root->left = insertNode(56);
    root->right = insertNode(12);
    root->left->left = insertNode(89);
    root->right->left = insertNode(32);
    root->right->right = insertNode(45);
    cout << "Tất cả nút đầy đủ của cây là:\n";
    printFullNode(root);
    return 0;
}

Đầu Ra

Tất cả nút đầy đủ của cây là: 100 12