นับโหนดครึ่ง (Half Nodes) ใน Binary Tree แบบ Iterative และ Recursive ใน C++

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

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

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

ตัวอย่าง

อินพุต–

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

คำอธิบาย – ในต้นไม้ที่กำหนด มี 2 โหนด คือ 40 และ 50 ที่มีลูกเพียงข้างเดียว (half 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) OR (temp->left AND !temp->right) แล้วเพิ่ม count ขึ้น 1
• ตรวจสอบ IF (temp->left != NULL) ทำ qu.push(temp->left)
• คืนค่า count
• พิมพ์ผลลัพธ์

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

// Program to count half nodes in a Binary Tree
#include <iostream>
#include <queue>
using namespace std;

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

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

เอาต์พุต

count is: 2

วิธี Recursive

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

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

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

// Recursive program to count half nodes
#include <bits/stdc++.h>
using namespace std;

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

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

เอาต์พุต

count is: 2