Kiểm tra Thuộc tính Sum Con trong Cây Nhị phân trong C ++

Giả sử chúng ta có một cây nhị phân. Cây nhị phân hợp lệ khi nó đáp ứng thuộc tính sau.

• Mỗi nút phải chứa giá trị dữ liệu giống như tổng các giá trị con bên trái và bên phải. Nếu không có con nào ở bên thì coi như bằng 0.

Giả sử có một cây như bên dưới, đáp ứng thuộc tính đã cho.

Không có thủ thuật nào như vậy để kiểm tra điều này, chúng ta phải duyệt qua cây một cách đệ quy, nếu nút và cả hai nút con của nó thỏa mãn thuộc tính thì trả về true, ngược lại là false.

Ví dụ

#include <iostream>
using namespace std;
class node {
   public:
   int data;
   node* left;
   node* right;
};
bool isValidBinaryTree(node* nd) {
   int left_data = 0, right_data = 0;
   if(nd == NULL || (nd->left == NULL && nd->right == NULL))
      return 1;
   else{
      if(nd->left != NULL)
         left_data = nd->left->data;
      if(nd->right != NULL)
         right_data = nd->right->data;
      if((nd->data == left_data + right_data)&& isValidBinaryTree(nd->left) && isValidBinaryTree(nd->right))
         return true;
      else
         return false;
   }
}
node* getNode(int data) {
   node* newNode = new node();
   newNode->data = data;
   newNode->left = NULL;
   newNode->right = NULL;
   return newNode;
}
int main() {
   node *root = getNode(10);
   root->left = getNode(8);
   root->right = getNode(2);
   root->left->left = getNode(3);
   root->left->right = getNode(5);
   root->right->right = getNode(2);
   if(isValidBinaryTree(root))
      cout << "The tree satisfies the children sum property ";
   else
      cout << "The tree does not satisfy the children sum property ";
}

Đầu ra

The tree satisfies the children sum property