Chúng ta được cung cấp một cây nhị phân và nhiệm vụ là tính số lượng nửa nút có sẵn trong cây nhị phân bằng cách sử dụng phương pháp lặp lại và đệ quy. Một nửa nút là những nút chỉ có một nút con và một nút con khác là null. Lưu ý rằng trong một nửa nút, chúng tôi không xem xét các nút lá.
Cây nhị phân là một cấu trúc dữ liệu đặc biệt được sử dụng cho mục đích lưu trữ dữ liệu. Một cây nhị phân có điều kiện đặc biệt là mỗi nút có thể có tối đa hai nút con. Cây nhị phân có những lợi ích của cả mảng có thứ tự và danh sách được liên kết vì tìm kiếm nhanh như trong một mảng được sắp xếp và thao tác chèn hoặc xóa cũng nhanh như trong danh sách được liên kết. Các nút không phải lá còn được gọi là nút cha vì chúng có nhiều hơn 0 nút con và ít hơn hai nút con.
Cấu trúc của cây nhị phân được đưa ra dưới đây -
Ví dụ
Đầu vào -
Đầu ra - số đếm là 2
Giải thích - trong cây đã cho, có 2 nút, tức là 40 và 50 với đúng một nút con hoặc một nửa nút các nút khác có thể có hai nút con hoặc không có nút con.
Lặp lại
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Tạo cấu trúc của một nút chứa một phần dữ liệu, con trỏ trái và con trỏ phải.
-
Tạo một hàm để chèn các nút trong cây nhị phân.
-
Tạo một hàm để đếm các nửa nút.
-
Bên trong một hàm, hãy kiểm tra nút IF!, Sau đó trả về vì không có nút nào trong cây.
-
Khai báo số lượng biến tạm thời để lưu trữ số lượng của một nửa nút
-
Tạo một biến loại hàng đợi, giả sử như qu
-
Đẩy các nút vào hàng đợi dưới dạng qu.push (nút)
-
Vòng lặp trong khi! Qu.empty ()
-
Tạo một biến tạm thời, giả sử tạm thời của loại Node và khởi tạo nó vớiqueue.front ()
-
Bật các phần tử bằng qu.pop ()
-
Kiểm tra IF (! Temp-> leftAND temp-> right) OR (temp-> left AND! Temp-> right) rồi tăng số đếm lên 1
-
Kiểm tra IF (temp-> left! =NULL) sau đó thực hiện qu.push (temp-> left)
-
Trả lại số lượng
-
In kết quả.
Ví dụ
// 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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -
Số lượngcount is: 2
Đệ quy
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Tạo cấu trúc của một nút chứa một phần dữ liệu, con trỏ trái và con trỏ phải.
-
Tạo một hàm để chèn các nút trong cây nhị phân.
-
Tạo một hàm để đếm các nửa nút.
-
Bên trong một hàm, hãy kiểm tra nút IF!, Sau đó trả về vì không có nút nào trong cây.
-
Khai báo số lượng biến tạm thời để lưu trữ số lượng của một nửa nút
-
Kiểm tra IF (root -> left =NULL AND root-> right! =NULL) OR (root -> left! =NULL AND root-> right ==NULL) sau đó tăng số lượng lên 1
-
Đặt count =count + recursive_call_to_this_ Chức năng (gốc-> trái) + recursive_call_to_this_ Chức năng (root-> phải)
-
Trả lại số lượng
-
In kết quả.
Ví dụ
// 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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -
Số lượngcount is: 2