ต้นไม้ต่อเนื่องใน C++

ต้นไม้ต่อเนื่องถูกกำหนดให้เป็นต้นไม้ที่มีเส้นทางจากโหนดรูทไปยังโหนดปลายสุดซึ่งมีค่าหรือน้ำหนักของโหนด ดังนั้นความแตกต่างที่แน่นอนระหว่างโหนดหลักและโหนดไดเร็กต์ไชน์ทั้งหมดจะเป็น 1 เสมอ

หากเราเลือกโหนดใด ๆ บนเส้นทางจากรากหนึ่งไปยังอีกใบ

|น้ำหนักของโหนด-น้ำหนักของโหนดย่อยด้านซ้าย|=|น้ำหนักของโหนดย่อย-น้ำหนักของโหนด| =1 สิ่งนี้ถือเป็นจริงสำหรับเด็กที่ใช่ด้วย

|น้ำหนักของโหนด-น้ำหนักของโหนดย่อยที่ถูกต้อง|=|น้ำหนัก lof น้ำหนักโหนดลูกที่ถูกต้อง-น้ำหนักของโหนด| =1

แผนภาพ

ให้เราเข้าใจด้วยตัวอย่าง

ต้นไม้ด้านล่างมีความต่อเนื่องเนื่องจากความแตกต่างโดยสิ้นเชิงระหว่างโหนดหลักและโหนดย่อยคือ 1

ต้นไม้ด้านล่างไม่มีคุณสมบัติเป็นต้นไม้ต่อเนื่อง

อัลกอริทึมในการค้นหาว่าต้นไม้มีความต่อเนื่องหรือไม่

• หากรูทเป็น NULL ให้คืนค่า 1

• หากเป็นโหนดลีฟ ให้คืนค่า 1 เนื่องจากต้นไม้เป็นแบบต่อเนื่อง นั่นคือสาเหตุที่ใบโหนดถูกแยกออก

• หากทรีย่อยด้านซ้ายว่างเปล่า ให้ตรวจสอบความต่อเนื่องของโหนดปัจจุบันกับชายด์ที่ถูกต้อง (คำนวณความแตกต่างสัมบูรณ์ของน้ำหนัก) และดำเนินการต่อสำหรับทรีย่อยด้านขวาแบบวนซ้ำ

• หากทรีย่อยด้านขวาว่างเปล่า ให้ตรวจสอบความต่อเนื่องของโหนดปัจจุบันกับโหนดย่อยด้านซ้าย (คำนวณความแตกต่างของน้ำหนักที่แน่นอน) และดำเนินการต่อสำหรับทรีย่อยด้านซ้ายแบบวนซ้ำ

• อย่างอื่น คำนวณผลต่างสัมบูรณ์ด้วยน้ำหนักของลูกซ้ายและขวา และดำเนินการต่อสำหรับทรีย่อยซ้ายและขวา แบบวนซ้ำ

รหัสเทียม

// Function to check tree is continuous or not
struct btreeNode{
   int data;
   btreeNode* left, * right;
};
int isContinuous(btreeNode *root){
   // if node is NULL return 1, exit condition
   if (root == NULL)
      return 1;
   //if leaf node is reached then tree must be continous during this path
   if (root->left == NULL && root->right == NULL)
      return 1;
   // if no left child
   if (root->left == NULL)
      return (abs(root->data - root->right->data) == 1) && isContinuous(root->right);
   // if no right child
   if (root->right == NULL)
      return (abs(root->data - root->left->data) == 1) && isContinuous(root->left);
      // calculate absoute difference
      return abs(root->data - root->left->data)==1 && abs(root->data - root->right->data)==1 &&
   isContinuous(root->left) && isContinuous(root->right);
}