นับครึ่งโหนดในทรีไบนารี (วนซ้ำและวนซ้ำ) ใน C ++

เราได้รับไบนารีทรีและภารกิจคือการคำนวณจำนวนโหนดครึ่งหนึ่งที่มีอยู่ในทรีไบนารีโดยใช้วิธีการวนซ้ำและแบบเรียกซ้ำ Half nodes คือโหนดที่มีลูกเพียงคนเดียวและลูกอีกคนหนึ่งเป็นโมฆะ โปรดทราบว่าในครึ่งโหนดเราไม่พิจารณาโหนดปลายสุด

Binary Tree เป็นโครงสร้างข้อมูลพิเศษที่ใช้เพื่อการจัดเก็บข้อมูล ต้นไม้ไบนารีมีเงื่อนไขพิเศษที่แต่ละโหนดสามารถมีลูกได้สูงสุดสองคน ต้นไม้ไบนารีมีประโยชน์ของทั้งอาร์เรย์ที่เรียงลำดับและรายการที่เชื่อมโยง เนื่องจากการค้นหานั้นรวดเร็วเหมือนกับในอาร์เรย์ที่เรียงลำดับ และการแทรกหรือการลบทำได้เร็วเท่ากับในรายการที่เชื่อมโยง โหนดที่ไม่ใช่โหนดลีฟเรียกอีกอย่างว่าโหนดหลัก เนื่องจากมีโหนดย่อยมากกว่า 0 รายการและโหนดย่อยน้อยกว่า 2 รายการ

โครงสร้างของไบนารีทรีแสดงไว้ด้านล่าง -

ตัวอย่าง

ป้อนข้อมูล −

ผลผลิต − นับเป็น 2

คำอธิบาย - ในทรีที่กำหนดมี 2 โหนดคือ 40 และ 50 โดยมีโหนดลูกหนึ่งโหนดหรือครึ่งโหนด โหนดอื่นอาจมีลูกสองคนหรือไม่มีลูก

วนซ้ำ

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

• สร้างโครงสร้างของโหนดที่มีส่วนข้อมูล ตัวชี้ซ้าย และตัวชี้ขวา

• สร้างฟังก์ชันเพื่อแทรกโหนดในไบนารีทรี

• สร้างฟังก์ชันนับครึ่งโหนด

• ภายในฟังก์ชัน ให้ตรวจสอบ IF !node แล้วกลับมา เนื่องจากไม่มีโหนดในทรี

• ประกาศการนับตัวแปรชั่วคราวเพื่อเก็บการนับครึ่งโหนด

• สร้างตัวแปรประเภทคิว สมมุติว่า qu

• กดโหนดในคิวเป็น qu.push(โหนด)

• วนรอบในขณะที่ !qu.empty()

• สร้างตัวแปรชั่วคราว สมมุติว่า temp ของ Node type และเริ่มต้นมันด้วยqueue.front()

• ป๊อปองค์ประกอบโดยใช้ qu.pop()

• ตรวจสอบว่า IF (!temp-> leftAND temp-> right) หรือ (temp->left AND !temp->right) จากนั้นเพิ่มจำนวนขึ้น 1

• ตรวจสอบว่า IF (temp->left !=NULL) จากนั้นดำเนินการ qu.push(temp->left)

• คืนจำนวน

• พิมพ์ผลลัพธ์

ตัวอย่าง

// Program to count half nodes in a Binary Tree
#include <iostream>
#include <queue>
using namespace std;
struct Node{
   int data;
   struct Node* left, *right;
};
// Function to get the count of half Nodes
int halfcount(struct Node* node){
   // If tree is empty
   if (!node)
   return 0;
   int result = 0; // Initialize count of half nodes
   // Do level order traversal starting from root
   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;
}
/* To allocate new Node with the given data and NULL left
and right pointers. */
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

แบบเรียกซ้ำ

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

• สร้างโครงสร้างของโหนดที่มีส่วนข้อมูล ตัวชี้ซ้าย และตัวชี้ขวา

• สร้างฟังก์ชันเพื่อแทรกโหนดในไบนารีทรี

• สร้างฟังก์ชันนับครึ่งโหนด

• ภายในฟังก์ชัน ให้ตรวจสอบ IF !node แล้วกลับมา เนื่องจากไม่มีโหนดในทรี

• ประกาศการนับตัวแปรชั่วคราวเพื่อเก็บการนับครึ่งโหนด

• ตรวจสอบว่า (root -> left =NULL AND root->right !=NULL) หรือ (root -> left !=NULL AND root->right ==NULL) จากนั้นให้เพิ่มจำนวนขึ้น 1

• Set count =count + recursive_call_to_this_function(root->left) +recursive_call_to_this_function(root->right)

• คืนจำนวน

• พิมพ์ผลลัพธ์

ตัวอย่าง

// Recursive program to count half nodes
#include <bits/stdc++.h>
using namespace std;
// A binary tree Node has data, pointer to left
// child and a pointer to right child
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;
}
/* to allocate a new Node with the given data and NULL left
and right pointers. */
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