พิมพ์ Internal Nodes ของ Binary Tree ใน C++

ภาพรวมปัญหา

ได้รับ Binary Tree ต้องพิมพ์ Internal Nodes ทั้งหมด (โหนดที่มีลูกอย่างน้อย 1 ตัว = ไม่ใช่ Leaf)

ตัวอย่าง

Output: 7 4 9

วิธีแก้ปัญหา (BFS Traversal)

1. ใช้ Queue สำหรับ BFS
2. Pop โหนด ตรวจสอบว่ามีลูกซ้ายหรือขวา
3. ถ้ามีลูกอย่างน้อย 1 ตัว → เป็น Internal Node → พิมพ์
4. Push ลูกเข้า Queue

ตัวอย่างโค้ด C++

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

struct Node {
    int data;
    Node *left, *right;
    Node(int data) {
        left = right = NULL;
        this->data = data;
    }
};

void printNonLeafNodes(Node* root) {
    queue<Node*> treeNodes;
    treeNodes.push(root);
    while (!treeNodes.empty()) {
        Node* curr = treeNodes.front();
        treeNodes.pop();
        bool isInternal = false;
        if (curr->left) {
            isInternal = true;
            treeNodes.push(curr->left);
        }
        if (curr->right) {
            isInternal = true;
            treeNodes.push(curr->right);
        }
        if (isInternal)
            cout << curr->data << "\t";
    }
}

int main() {
    Node* root = new Node(43);
    root->left = new Node(12);
    root->right = new Node(78);
    root->left->left = new Node(4);
    root->right->left = new Node(9);
    root->right->right = new Node(1);
    root->right->right->right = new Node(50);
    root->right->right->left = new Node(25);
    cout << "All internal Nodes of the binary tree are:\n";
    printNonLeafNodes(root);
    return 0;
}

ผลลัพธ์ (Output)

All internal Nodes of the binary tree are:
43 12 78 1