Đếm nút đầy (full nodes) trong cây nhị phân C++

Cho cây nhị phân. Đếm số nút đầy (full nodes) - nút có cả hai con (không phải NULL).

Ví dụ

Cây có nút 10, 20 có 2 con → 2 nút đầy.

Phương pháp lặp (Iterative - BFS)

• Duyệt theo mức (level order) dùng queue.
• Nếu node->left && node->right → tăng count.

Phương pháp đệ quy (Recursive)

• Nếu root NULL → trả về 0.
• count = (root->left && root->right) ? 1 : 0.
• Trả về count + đệ quy trái + đệ quy phải.

Ví dụ minh họa - Lặp (C++)

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

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

int fullcount(struct Node* node) {
    if (!node) return 0;
    queue<Node*> myqueue;
    int result = 0;
    myqueue.push(node);
    while (!myqueue.empty()) {
        struct Node* temp = myqueue.front();
        myqueue.pop();
        if (temp->left && temp->right) result++;
        if (temp->left) myqueue.push(temp->left);
        if (temp->right) myqueue.push(temp->right);
    }
    return result;
}

struct Node* newNode(int data) {
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

int main() {
    struct Node* root = newNode(10);
    root->left = newNode(20);
    root->right = newNode(30);
    root->left->left = newNode(40);
    root->left->right = newNode(50);
    root->left->left->right = newNode(60);
    root->left->right->right = newNode(70);
    cout << "count is: " << fullcount(root);
    return 0;
}

Đầu ra

count is: 2

Ví dụ minh họa - Đệ quy (C++)

#include <iostream>
using namespace std;

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

int fullcount(struct Node* root) {
    if (root == NULL) return 0;
    int result = 0;
    if (root->left && root->right) result++;
    result += fullcount(root->left) + fullcount(root->right);
    return result;
}

struct Node* newNode(int data) {
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

int main() {
    struct Node* root = newNode(10);
    root->left = newNode(20);
    root->right = newNode(30);
    root->left->left = newNode(40);
    root->left->right = newNode(50);
    root->left->left->right = newNode(60);
    root->left->right->right = newNode(70);
    cout << "count is: " << fullcount(root);
    return 0;
}

Đầu ra

count is: 2