ตรวจสอบคุณสมบัติ Children Sum ใน Binary Tree ใน C ++

สมมติว่าเรามีต้นไม้ไบนารี ต้นไม้ไบนารีถูกต้องเมื่อตรงตามคุณสมบัติต่อไปนี้

• แต่ละโหนดควรมีค่าข้อมูลเหมือนกับผลรวมของค่าลูกซ้ายและขวา หากไม่มีลูกอยู่ข้างใดข้างหนึ่ง จะถือว่าเป็น 0

สมมติว่ามีต้นไม้อยู่ด้านล่างซึ่งตรงกับคุณสมบัติที่กำหนด

ไม่มีเคล็ดลับในการตรวจสอบ เราต้องสำรวจต้นไม้ซ้ำๆ หากโหนดและลูกทั้งสองมีคุณสมบัติตรงตามคุณสมบัติ คืนค่าจริง ไม่เช่นนั้นจะเป็นเท็จ

ตัวอย่าง

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

ผลลัพธ์

The tree satisfies the children sum property