นับโหนดที่ไม่ใช่ใบในต้นไม้แบบทวิภาคใน C++

เราได้รับต้นไม้แบบทวิภาค (Binary Tree) งานคือการนับจำนวนโหนดที่ไม่ใช่ใบ (non-leaf nodes) ซึ่งหมายถึงโหนดที่มีลูกอย่างน้อยหนึ่งข้าง

โครงสร้างต้นไม้แบบทวิภาค

โหนดแต่ละตัวมีสูงสุด 2 ลูก (ซ้ายและขวา) โหนดที่ไม่ใช่ใบเรียกว่าโหนดพาเรนต์ (parent nodes)

ตัวอย่าง

Input − ต้นไม้ที่มีโหนด 27, 14, 35 เป็นโหนดที่ไม่ใช่ใบ

Output − count of non-leaf nodes is: 3

แนวทางการแก้ปัญหา (Recursive)

• สร้างโครงสร้าง Node มี data, left, right
• ฟังก์ชันสร้างโหนดใหม่
• ฟังก์ชันนับโหนดไม่ใช่ใบแบบเรียกซ้ำ:
  • ถ้า root เป็น NULL หรือเป็นใบ (left และ right เป็น NULL) คืนค่า 0
  • คืนค่า 1 + เรียกซ้ำด้านซ้าย + เรียกซ้ำด้านขวา

ตัวอย่างโค้ด 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 = nullptr;
    return node;
}

int countNonLeaf(Node* root) {
    if (root == nullptr || (root->left == nullptr && root->right == nullptr))
        return 0;
    return 1 + countNonLeaf(root->left) + countNonLeaf(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: " << countNonLeaf(root);
    return 0;
}

ผลลัพธ์

count of non-leaf nodes is: 2