เราได้รับไบนารีทรีและภารกิจคือการคำนวณจำนวนโหนดทั้งหมดที่มีอยู่ในแผนผังไบนารีโดยใช้วิธีการวนซ้ำและแบบเรียกซ้ำ โหนดเต็มคือโหนดที่มีทั้งลูกและไม่มีลูกใดเป็นโมฆะ โปรดทราบว่าในโหนดเต็ม เราจะพิจารณาโหนดที่มีลูกสองคนพอดี
Binary Tree เป็นโครงสร้างข้อมูลพิเศษที่ใช้เพื่อการจัดเก็บข้อมูล ต้นไม้ไบนารีมีเงื่อนไขพิเศษที่แต่ละโหนดสามารถมีลูกได้สูงสุดสองคน ต้นไม้ไบนารีมีประโยชน์ของทั้งอาร์เรย์ที่เรียงลำดับและรายการที่เชื่อมโยง เนื่องจากการค้นหานั้นรวดเร็วเหมือนกับในอาร์เรย์ที่เรียงลำดับ และการแทรกหรือการลบทำได้เร็วเท่ากับในรายการที่เชื่อมโยง โหนดที่ไม่ใช่โหนดลีฟเรียกอีกอย่างว่าโหนดหลัก เนื่องจากมีโหนดย่อยมากกว่า 0 รายการและโหนดย่อยน้อยกว่า 2 รายการ
โครงสร้างของไบนารีทรีแสดงไว้ด้านล่าง -
ตัวอย่าง
ป้อนข้อมูล −
ผลผลิต − นับเป็น 2
คำอธิบาย - ในทรีที่กำหนดมี 2 โหนดคือ 10 และ 20 มีลูกสองหรือโหนดเต็ม โหนดอื่นมีลูกหนึ่งคนหรือไม่มีลูก
วนซ้ำ
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
สร้างโครงสร้างของโหนดที่มีส่วนข้อมูล ตัวชี้ซ้าย และตัวชี้ขวา
-
สร้างฟังก์ชันเพื่อแทรกโหนดในไบนารีทรี
-
สร้างฟังก์ชันเพื่อนับโหนดเต็ม
-
ภายในฟังก์ชัน ให้ตรวจสอบ IF !node แล้วกลับมา เนื่องจากไม่มีโหนดในทรี
-
ประกาศการนับตัวแปรชั่วคราวเพื่อเก็บจำนวนโหนดเต็ม
-
สร้างตัวแปรประเภทคิว สมมุติว่า qu
-
กดโหนดในคิวเป็น qu.push(โหนด)
-
วนรอบในขณะที่ !qu.empty()
-
สร้างตัวแปรชั่วคราว สมมุติว่า temp ของ Node type และเริ่มต้นมันด้วยqueue.front()
-
ป๊อปองค์ประกอบโดยใช้ qu.pop()
-
ตรวจสอบว่า IF (!temp-> left AND temp-> right) จากนั้นให้เพิ่มจำนวนขึ้น 1
-
ตรวจสอบว่า IF (temp->left !=NULL) จากนั้นดำเนินการ qu.push(temp->left)
-
ตรวจสอบ IF (temp->right !=NULL) จากนั้น qu.push(temp->right)
-
คืนจำนวน
-
พิมพ์ผลลัพธ์
ตัวอย่าง
// Iterative program to count full nodes
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// Function to count the full Nodes in a binary tree
int fullcount(struct Node* node){
// Check if tree is empty
if (!node){
return 0;
}
queue<Node *> myqueue;
// traverse using level order traversing
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
แบบเรียกซ้ำ
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
สร้างโครงสร้างของโหนดที่มีส่วนข้อมูล ตัวชี้ซ้าย และตัวชี้ขวา
-
สร้างฟังก์ชันเพื่อแทรกโหนดในไบนารีทรี
-
สร้างฟังก์ชันเพื่อนับโหนดเต็ม
-
ภายในฟังก์ชัน ให้ตรวจสอบ IF !node แล้วกลับมา เนื่องจากไม่มีโหนดในทรี
-
ประกาศการนับตัวแปรชั่วคราวเพื่อเก็บการนับครึ่งโหนด
-
ตรวจสอบว่า IF (root -> left AND root->right) แล้วเพิ่มจำนวนขึ้น 1
-
Set count =count + recursive_call_to_this_function(root->left) +recursive_call_to_this_function(root->right)
-
คืนจำนวน
-
พิมพ์ผลลัพธ์
ตัวอย่าง
// Recursive program to count full nodes
#include <iostream>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
// Function to get the count of full Nodes
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
