ค้นหาทรีย่อยที่สมบูรณ์ที่สุดใน Binary Tree ที่กำหนดใน C++

แนวคิด

สำหรับต้นไม้ไบนารีที่กำหนด ภารกิจคือการกำหนดขนาดของทรีย่อยที่สมบูรณ์สูงสุดในต้นไม้ไบนารีที่กำหนด

Complete Binary Tree – ต้นไม้ไบนารีจะถือว่าเป็นต้นไม้ไบนารีที่สมบูรณ์ หากระดับทั้งหมดถูกเติมเต็มโดยสมบูรณ์โดยไม่มีระดับสุดท้ายและระดับสุดท้ายมีคีย์ทั้งหมดที่เหลืออยู่เท่าที่จะเป็นไปได้ มีข้อสังเกตว่าต้นไม้ไบนารีที่สมบูรณ์แบบทั้งหมดเป็นต้นไม้ไบนารีที่สมบูรณ์ แต่ ย้อนกลับในไม่จริง จะเห็นได้ว่าถ้าต้นไม้ไม่สมบูรณ์ มันก็จะไม่ใช่ Perfect Binary Tree ด้วย

ป้อนข้อมูล

      2
     / \
    3   4
   / \  / \
  5   6 7  8
 / \ /
9 10 11

ผลผลิต

Size : 10
Inorder Traversal : 9 5 10 3 11 6 2 7 4 8
The above given tree is a complete binary tree.

ป้อนข้อมูล

      51
     / \
   31    61
   / \   / \
  6 21 46   71
 /
11

ผลผลิต

Size : 4(With respect of right subtree)
Inorder Traversal : 11 46 61 71
The above given tree is not a complete binary tree.

วิธีการ

เพียงแค่เยี่ยมชมต้นไม้ในลักษณะจากล่างขึ้นบน ต่อไปเกี่ยวกับการเรียกซ้ำจาก child ไปยัง parent เราสามารถถ่ายโอนข้อมูลเกี่ยวกับ sub-tree ไปยัง parent พาเรนต์สามารถใช้ข้อมูลที่ถ่ายโอนเพื่อทำการทดสอบทรีสมบูรณ์ (สำหรับโหนดพาเรนต์) ในเวลาคงที่เท่านั้น ในกรณีนี้ ต้นไม้ย่อยทั้งซ้ายและขวาจำเป็นต้องบอกข้อมูลพาเรนต์ว่าสมบูรณ์หรือไม่สมบูรณ์หรือไม่ และยังต้องส่งคืนขนาดสูงสุดของต้นไม้ไบนารีที่สมบูรณ์ที่พบจนถึงปัจจุบัน

เราควรสังเกตว่าแผนผังย่อยจำเป็นต้องถ่ายโอนข้อมูลต่อไปนี้ขึ้นบนทรีเพื่อกำหนดโครงสร้างย่อยที่สมบูรณ์ที่ใหญ่ที่สุด เพื่อให้เราสามารถเปรียบเทียบขนาดสูงสุดกับข้อมูลของพาเรนต์เพื่อตรวจสอบคุณสมบัติ Complete Binary Tree

• ควรมีตัวแปรบูลเพื่อตรวจสอบว่าทรีย่อยด้านซ้ายหรือแผนผังย่อยย่อยที่ถูกต้องสมบูรณ์และสมบูรณ์หรือไม่

• อีกครั้ง เราต้องตรวจสอบอีกครั้งว่าจากการเรียกลูกซ้ายและขวาในการเรียกซ้ำ เราจะพบว่าทรีย่อยพาเรนต์เสร็จสมบูรณ์หรือไม่โดยทำตาม 3 กรณี -

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

  • จะเห็นได้ว่าถ้าทรีย่อยด้านซ้ายสมบูรณ์และด้านขวาสมบูรณ์ และความสูงของด้านซ้ายมากกว่าด้านขวาทีละหนึ่ง รูทของทรีย่อยย่อยก็จะเป็นทรีย่อยแบบไบนารีที่สมบูรณ์โดยมีขนาดเท่ากับผลรวมของทรีย่อยด้านซ้ายและขวา บวกหนึ่ง (สำหรับรูทปัจจุบัน) . แต่ไม่สามารถประกาศทรีย่อยของรูทเป็นทรีย่อยไบนารีที่สมบูรณ์แบบได้ เพราะในกรณีนี้ ลูกด้านซ้ายของมันไม่สมบูรณ์แบบ

  • มิฉะนั้นทรีย่อยนี้ไม่สามารถถือเป็นไบนารีทรีที่สมบูรณ์ได้ และเพียงแค่ส่งคืนทรีย่อยที่สมบูรณ์ที่มีขนาดที่ใหญ่ที่สุดเท่าที่พบจนถึงขณะนี้ในทรีย่อยทางซ้ายหรือขวา ดังนั้นสรุปได้ว่าหากทรีไม่สมบูรณ์ ก็ไม่เป็นเช่นนั้น สมบูรณ์แบบอีกด้วย

ตัวอย่าง

//This is a C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Node structure of the tree
struct node1 {
   int data;
   struct node1* left;
   struct node1* right;
};
// For creating a new node
struct node1* newNode(int data){
   struct node1* node1 = (struct node1*)malloc(sizeof(struct node1));
   node1->data = data;
   node1->left = NULL;
   node1->right = NULL;
   return node1;
};
// Shows structure for return type of
// function findPerfectBinaryTree
struct returnType {
   // For storing if sub-tree is perfect or not
   bool isPerfect;
   // For storing if sub-tree is complete or not
   bool isComplete;
   // Indicates size of the tree
   int size1;
   // Root of biggest complete sub-tree
   node1* rootTree;
};
// Shows helper function that returns height
// of the tree given size
int getHeight(int size1){
   return ceil(log2(size1 + 1));
}
// Shows function to return the biggest
// complete binary sub-tree
returnType findCompleteBinaryTree(struct node1* root){
   // Declaring returnType that
   // needs to be returned
   returnType rt1;
   // If root is NULL then it is considered as both
   // perfect and complete binary tree of size 0
   if (root == NULL) {
      rt1.isPerfect = true;
      rt1.isComplete = true;
      rt1.size1 = 0;
      rt1.rootTree = NULL;
      return rt1;
   }
   // Shows recursive call for left and right child
   returnType lv1 = findCompleteBinaryTree(root->left);
   returnType rv1 = findCompleteBinaryTree(root->right);
   // CASE - A
   // It has been seen that if left sub-tree is perfect and right is
   // complete and there height is also same then sub-tree root
   // is also complete binary sub-tree with size equal to
   // sum of left and right subtrees plus one for current root
   if (lv1.isPerfect == true && rv1.isComplete == true && getHeight(lv1.size1) == getHeight(rv1.size1)) {
      rt1.isComplete = true;
      // It has been seen that if right sub-tree is perfect then
      // root is also perfect
      rt1.isPerfect = (rv1.isPerfect ? true : false);
      rt1.size1 = lv1.size1 + rv1.size1 + 1;
      rt1.rootTree = root;
      return rt1;
   }
   // CASE - B
   // It has been seen if left sub-tree is complete and right is
   // also perfect and the left height is greater than height of right by one
   // then sub-tree root will be a complete binary sub-tree with the size equal to
   // sum of left and right subtrees plus one for current root.
   // But sub-tree cannot be perfect binary sub-tree.
   if (lv1.isComplete == true && rv1.isPerfect == true && getHeight(lv1.size1) == getHeight(rv1.size1) + 1) {
      rt1.isComplete = true;
      rt1.isPerfect = false;
      rt1.size1 = lv1.size1 + rv1.size1 + 1;
      rt1.rootTree = root;
      return rt1;
   }
   // CASE - C
   // Otherwise this sub-tree cannot be a complete binary tree
   // and simply return the biggest sized complete sub-tree
   // found till now in the left or right sub-trees
   rt1.isPerfect = false;
   rt1.isComplete = false;
   rt1.size1 = max(lv1.size1, rv1.size1);
   rt1.rootTree = (lv1.size1 > rv1.size1 ? lv1.rootTree :
   rv1.rootTree);
   return rt1;
}
// Shows function to print the inorder traversal of the tree
void inorderPrint(node1* root){
   if (root != NULL) {
      inorderPrint(root->left);
      cout << root->data << " ";
      inorderPrint(root->right);
   }
}
// Driver code
int main(){
   // Creating the tree
   struct node1* root = newNode(50);
   root->left = newNode(30);
   root->right = newNode(60);
   root->left->left = newNode(5);
   root->left->right = newNode(20);
   root->right->left = newNode(45);
   root->right->right = newNode(70);
   root->right->left->left = newNode(10);
   // Getting the biggest sized complete binary sub-tree
   struct returnType ans1 = findCompleteBinaryTree(root);
   cout << "Size : " << ans1.size1 << endl;
   // Printing the inorder traversal of the found sub-tree
   cout << "Inorder Traversal : ";
   inorderPrint(ans1.rootTree);
   return 0;
}

ผลลัพธ์

Size : 4
Inorder Traversal : 10 45 60 70