Đếm nút nửa (half nodes) trong cây nhị phân C++

Cho cây nhị phân. Đếm số nút nửa (half nodes) - nút có đúng một con (con kia là NULL). Không tính nút lá.

Ví dụ

Cây có nút 40, 50 mỗi nút 1 con → 2 nút nửa.

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

• Duyệt level order dùng queue.
• Nếu (!left && right) || (left && !right) → tăng count.

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

• Nếu root NULL → 0.
• count = ((left==NULL && right!=NULL) || (left!=NULL && right==NULL)) ? 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 halfcount(struct Node* node) {
    if (!node) return 0;
    int result = 0;
    queue<Node*> myqueue;
    myqueue.push(node);
    while (!myqueue.empty()) {
        struct Node* temp = myqueue.front();
        myqueue.pop();
        if ((!temp->left && temp->right) || (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: " << halfcount(root);
    return 0;
}

Đầu ra

count is: 2

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

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

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

int halfcount(struct Node* root) {
    if (root == NULL) return 0;
    int result = 0;
    if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right == NULL))
        result++;
    result += halfcount(root->left) + halfcount(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: " << halfcount(root);
    return 0;
}

Đầu ra

count is: 2