Đếm các nút đầy đủ trong cây nhị phân (Lặp lại và Đệ quy) trong C ++

Chúng ta được cung cấp một cây nhị phân và nhiệm vụ là tính toán số lượng các nút đầy đủ 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. Các nút đầy đủ là những nút có cả nút con và không nút con nào là rỗng. Lưu ý rằng trong các nút đầy đủ, chúng tôi coi các nút có chính xác hai nút con.

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. Cây nhị phân có một đ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à 10 và 20 có đúng hai nút con hoặc các nút đầy đủ các nút khác hoặc có một 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út đầy đủ.

• 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ác nút đầy đủ

• 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-> left AND temp-> right) sau đó tăng số lượng lên 1

• Kiểm tra IF (temp-> left! =NULL) sau đó thực hiện qu.push (temp-> left)

• Kiểm tra IF (temp-> right! =NULL) rồi đến qu.push (temp-> right)

• Trả lại số lượng

• In kết quả.

Ví dụ

// 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;
}

Đầ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 -

count 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út đầy đủ.

• 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 (gốc -> trái VÀ gốc-> phải) 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 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;
}

Đầ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 -

count is: 2