พิมพ์ Full Nodes ใน Binary Tree ใน C++

ภาพรวมปัญหา

ได้รับ Binary Tree ต้องพิมพ์โหนดที่เป็น Full Nodes ทั้งหมด

Full Node คืออะไร?

โหนดที่มีลูกซ้ายและลูกขวาครบทั้งคู่ (มีลูก 2 ตัว)

ตัวอย่าง

ในต้นไม้นี้ โหนด 4 และ 9 เป็น Full Nodes

วิธีแก้ปัญหา

Traversal แบบใดก็ได้ (Inorder, Preorder, Postorder) ตรวจสอบแต่ละโหนดว่า left != NULL และ right != NULL

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

#include <iostream>
using namespace std;

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

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

void printFullNode(Node* root) {
    if (root != NULL) {
        printFullNode(root->left);
        if (root->left != NULL && root->right != NULL)
            cout << root->data << "\t";
        printFullNode(root->right);
    }
}

int main() {
    Node* root = insertNode(100);
    root->left = insertNode(56);
    root->right = insertNode(12);
    root->left->left = insertNode(89);
    root->right->left = insertNode(32);
    root->right->right = insertNode(45);
    cout << "All full nodes of the tree are:\n";
    printFullNode(root);
    return 0;
}

ผลลัพธ์ (Output)

All full nodes of the tree are:
100 12