นับโหนดเต็ม (Full Nodes) ใน Binary Tree แบบ Iterative และ Recursive ใน C++

เราได้รับ binary tree และงานคือคำนวณจำนวนโหนดเต็ม (full nodes) ใน binary tree โดยใช้วิธี iterative และ recursive โหนดเต็มคือโหนดที่มีลูกทั้งสองข้าง และไม่มีลูกเป็น null หมายเหตุ: ในโหนดเต็ม เราพิจารณาเฉพาะโหนดที่มีลูกสองตัวเท่านั้น

Binary Tree เป็นโครงสร้างข้อมูลพิเศษใช้สำหรับเก็บข้อมูล Binary tree มีเงื่อนไขพิเศษคือแต่ละโหนดสามารถมีลูกได้สูงสุดสองตัว Binary tree มีประโยชน์ของทั้งอาร์เรย์ที่เรียงลำดับและ linked list เพราะการค้นหาเร็วเท่าอาร์เรย์ที่เรียง และการแทรก/ลบเร็วเท่า linked list โหนดที่ไม่ใช่ใบ (non-leaf nodes) เรียกอีกอย่างว่า parent nodes เพราะมีลูกมากกว่า 0 และน้อยกว่าสอง

โครงสร้างของ binary tree แสดงด้านล่าง –

ตัวอย่าง

อินพุต–

เอาต์พุต – count is 2

คำอธิบาย – ในต้นไม้ที่กำหนด มี 2 โหนด คือ 10 และ 20 ที่มีลูกสองตัว (full nodes) โหนดอื่นๆ มีลูกหนึ่งตัวหรือไม่มีลูก

วิธี Iterative

วิธีการที่ใช้ในโปรแกรมด้านล่าง

• สร้างโครงสร้างโหนดที่มีส่วนข้อมูล, พอยน์เตอร์ซ้าย และขวา
• สร้างฟังก์ชันแทรกโหนดใน binary tree
• สร้างฟังก์ชันนับโหนดเต็ม
• ในฟังก์ชัน ตรวจสอบ IF !node แล้วคืนค่า เพราะไม่มีโหนดในต้นไม้
• ประกาศตัวแปรชั่วคราว count เก็บจำนวนโหนดเต็ม
• สร้างคิว (queue) ให้เป็น qu
• Push โหนดลงคิว qu.push(node)
• ลูป while !qu.empty()
• สร้างตัวแปรชั่วคราว temp ประเภท Node เริ่มต้นที่ queue.front()
• Pop ออกมาโดย qu.pop()
• ตรวจสอบ IF (!temp->left AND temp->right) แล้วเพิ่ม count ขึ้น 1
• ตรวจสอบ IF (temp->left != NULL) ทำ qu.push(temp->left)
• ตรวจสอบ IF (temp->right != NULL) ทำ qu.push(temp->right)
• คืนค่า count
• พิมพ์ผลลัพธ์

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

// Iterative program to count full nodes
#include <iostream>
#include <queue>
using namespace std;

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

int fullcount(struct Node* node){
    if (!node){
        return 0;
    }
    queue<Node *> myqueue;
    int result = 0;
    myqueue.push(node);
    while (!myqueue.empty()){
        struct Node *temp = myqueue.front();
        myqueue.pop();
        if (temp->left && temp->right){
            result++;
        }
        if (temp->left != NULL){
            myqueue.push(temp->left);
        }
        if (temp->right != NULL){
            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(void){
    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: " << fullcount(root);
    return 0;
}

เอาต์พุต

count is: 2

วิธี Recursive

วิธีการที่ใช้ในโปรแกรมด้านล่าง

• สร้างโครงสร้างโหนดที่มีส่วนข้อมูล, พอยน์เตอร์ซ้าย และขวา
• สร้างฟังก์ชันแทรกโหนดใน binary tree
• สร้างฟังก์ชันนับโหนดเต็ม
• ในฟังก์ชัน ตรวจสอบ IF !node แล้วคืนค่า
• ประกาศตัวแปรชั่วคราว count เก็บจำนวนโหนดครึ่ง
• ตรวจสอบ IF (root -> left AND root->right) แล้วเพิ่ม count ขึ้น 1
• ตั้งค่า count = count + เรียกฟังก์ชันซ้ำ(root->left) + เรียกฟังก์ชันซ้ำ(root->right)
• คืนค่า count
• พิมพ์ผลลัพธ์

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

// Recursive program to count full nodes
#include <iostream>
using namespace std;

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

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

เอาต์พุต

count is: 2