นับโหนดที่ไม่ใช่ Leaf ใน Binary Tree ใน C++

เราได้รับไบนารีทรีและภารกิจคือการคำนวณจำนวนโหนดที่ไม่ใช่ใบไม้ที่มีอยู่ในต้นไม้ไบนารี

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

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

ตัวอย่าง

ป้อนข้อมูล −

ผลผลิต − จำนวนโหนดที่ไม่ใช่ใบคือ:3

คำอธิบาย − ในทรีที่กำหนด เรามี 27, 14 และ 35 เป็นโหนดที่ไม่ใช่ใบไม้ เนื่องจากมีลูกมากกว่า 0 ลูกและลูกน้อยกว่า 2 ลูก

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

• สร้างโครงสร้างของไบนารีทรีประกอบด้วย ตัวชี้ไปยังโหนดด้านซ้าย ตัวชี้ไปยังโหนดด้านขวา และส่วนข้อมูลที่เก็บอยู่ในโหนด

• สร้างฟังก์ชันที่จะแทรกโหนดทุกครั้งที่เรียกใช้ฟังก์ชันนี้ สำหรับสิ่งนั้น ให้แทรกข้อมูลในโหนดใหม่และตั้งค่าตัวชี้ขวาและซ้ายของโหนดใหม่เป็น NULL แล้วส่งคืนโหนด

• สร้างฟังก์ชันเรียกซ้ำที่จะนับจำนวนโหนดที่ไม่ใช่ใบไม้ในไบนารีทรี

  • ตรวจสอบว่า root เป็น NULL หรือด้านซ้ายของ root เป็น NULL และด้านขวาของ root เป็น NULL ให้คืนค่า 0
  • ส่งคืน 1 + การเรียกซ้ำไปยังฟังก์ชันนี้ด้วยตัวชี้ด้านซ้าย + การเรียกซ้ำไปยังฟังก์ชันนี้ด้วยตัวชี้ด้านขวา

• พิมพ์จำนวน

ตัวอย่าง

#include <iostream>
using namespace std;
// Node's structure
struct Node {
   int data;
   struct Node* left;
   struct Node* right;
};
// To define the new node
struct Node* newNode(int data){
   struct Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
// Count the non leaf nodes.
int nonleaf(struct Node* root){
   if (root == NULL || (root->left == NULL && root->right == NULL)){
      return 0;
   }
   return 1 + nonleaf(root->left) + nonleaf(root->right);
}
// Main function
int main(){
   struct Node* root = newNode(10);
   root->left = newNode(21);
   root->right = newNode(33);
   root->left->left = newNode(48);
   root->left->right = newNode(51);
   cout << nonleaf(root);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

count of non-leaf nodes is: 2