Đếm các nút không phải là lá trong cây nhị phân trong C ++

Chúng tôi được cung cấp với một cây nhị phân và nhiệm vụ là tính số lượng các nút không phải lá có sẵn trong một cây nhị phân.

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ố nút không phải lá là:3

Giải thích - Trong cây đã cho, chúng ta có 27, 14 và 35 là các nút không phải lá vì chúng có nhiều hơn 0 nút con và ít hơn 2 nút con.

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 cây nhị phân chứa, con trỏ tới nút trái, con trỏ tới nút phải và một phần dữ liệu được lưu trữ trong nút

• Tạo một hàm sẽ chèn một nút bất cứ khi nào hàm này được gọi. Để làm điều đó, hãy chèn dữ liệu vào một nút mới, đồng thời đặt con trỏ phải và trái của nút mới thành NULL và trả về nút.

• Tạo một hàm đệ quy sẽ đếm số lượng các nút không phải là lá trong cây nhị phân.

  • Kiểm tra Nếu gốc là NULL hoặc bên trái của gốc là NULL và bên phải của gốc là NULL thì trả về 0
  • Trả lại 1 + lời gọi đệ quy cho hàm này với con trỏ trái + lệnh gọi đệ quy tới hàm này với con trỏ phải

• In số lượng

Ví dụ

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

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

count of non-leaf nodes is: 2