Kiểm tra xem một Cây nhị phân nhất định có phải là SumTree trong C ++ hay không

Ở đây chúng ta sẽ xem cách kiểm tra một cây nhị phân có phải là cây tổng hay không. Bây giờ câu hỏi là cây tổng hợp là gì. Cây tổng hợp là một cây nhị phân trong đó một nút sẽ giữ giá trị tổng của các nút con của nó. Gốc của cây sẽ chứa toàn bộ tổng của tất cả các phần tử bên dưới nó. Đây là một ví dụ về cây tổng hợp -

Để kiểm tra điều này, chúng ta sẽ làm theo một thủ thuật đơn giản, chúng ta sẽ tìm tổng các phần tử của cây con bên trái và bên phải nếu giá trị tổng giống với gốc thì đó là sum-tree. Đây sẽ là một cách tiếp cận đệ quy.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class node {
   public:
   int data;
   node* left, *right;
};
int sum_of_nodes(node *root) {
   if(root == NULL)
      return 0;
   return sum_of_nodes(root->left) + root->data + sum_of_nodes(root->right);
}
int isSumTree(node* node) {
   int left_sum, right_sum;
   if(node == NULL || (node->left == NULL && node->right == NULL))
      return 1;
   left_sum = sum_of_nodes(node->left);
   right_sum = sum_of_nodes(node->right);
   if((node->data == left_sum + right_sum) && isSumTree(node->left) && isSumTree(node->right))
      return 1;
   return 0;
}
node* getNode(int data) {
   node* newNode = new node();
   newNode->data = data;
   newNode->left = newNode->right = NULL;
   return newNode;
}
int main() {
   node *root = getNode(26);
   root->left = getNode(10);
   root->right = getNode(3);
   root->left->left = getNode(4);
   root->left->right = getNode(6);
   root->right->right = getNode(3);
   if(isSumTree(root))
      cout << "The tree is Sum Tree";
   else
      cout << "The tree is not a Sum Tree";
}

Đầu ra

The tree is Sum Tree