Đếm nút không phải lá trong cây nhị phân C++

Cho một cây nhị phân, nhiệm vụ là đếm số nút không phải lá (non-leaf nodes) - tức là các nút có ít nhất một con (con trái hoặc con phải hoặc cả hai).

Ví dụ

Output - count of non-leaf nodes is: 3

Giải thích - Các nút 27, 14, 35 là nút không phải lá vì có con.

Phương pháp tiếp cận (Đệ quy)

• Định nghĩa cấu trúc Node: data, left, right
• Hàm đệ quy nonleaf(root):
  • Nếu root == NULL hoặc (left == NULL và right == NULL) → trả về 0 (là nút lá)
  • Ngược lại: trả về 1 + nonleaf(left) + nonleaf(right)

Ví dụ code C++

#include <iostream>
using namespace std;

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

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

int nonleaf(Node* root) {
    if (root == NULL || (root->left == NULL && root->right == NULL))
        return 0;
    return 1 + nonleaf(root->left) + nonleaf(root->right);
}

int main() {
    Node* root = newNode(10);
    root->left = newNode(21);
    root->right = newNode(33);
    root->left->left = newNode(48);
    root->left->right = newNode(51);
    cout << "count of non-leaf nodes is: " << nonleaf(root);
    return 0;
}

Kết quả

count of non-leaf nodes is: 2