পাইথনে একটি বাইনারি গাছ সম্পূর্ণ কিনা তা পরীক্ষা করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি গাছ আছে; এটি একটি সম্পূর্ণ বাইনারি গাছ কিনা তা আমাদের পরীক্ষা করতে হবে। যেমনটি আমরা জানি একটি সম্পূর্ণ বাইনারি ট্রিতে স্তরগুলি সম্ভবত শেষটি ছাড়া নোড দিয়ে ভরা হয় এবং শেষ স্তরের সমস্ত নোড যতটা সম্ভব বাকি থাকে৷

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে True

এটি সমাধান করার জন্য, আমরা এই পদক্ষেপগুলি অনুসরণ করব—

• q :=একটি ডবল শেষ সারি

• q

  এর শেষে রুট সন্নিবেশ করান

• পতাকা :=মিথ্যা

• q খালি না থাকার সময়, করুন

  • temp :=q

    এর বাম থেকে মুছে ফেলার পর উপাদান

  • যদি temp শূন্য হয়, তাহলে

    • পতাকা :=সত্য

  • অন্যথায় যখন পতাকা সেট করা হয় এবং তাপমাত্রা শূন্য হয় না, তখন

    • রিটার্ন ফলস

  • অন্যথায়,

    • q

      এর শেষে তাপমাত্রার বাম দিকে সন্নিবেশ করুন

    • q

      এর শেষে তাপমাত্রার ডানদিকে সন্নিবেশ করুন

• রিটার্ন ট্রু

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

from collections import deque
class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root):
      q = deque()
      q.append(root)
      flag = False
   while q:
      temp = q.popleft()
   if not temp:
      flag = True
      elif flag and temp:
   return False
   else:
      q.append(temp.left)
      q.append(temp.right)
   return True
ob = Solution()
root = TreeNode(9)
root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.left = TreeNode(6)
root.left.right = TreeNode(8)
print(ob.solve(root))

ইনপুট

root = TreeNode(9) root.left = TreeNode(7) root.right = TreeNode(10) root.left.left = TreeNode(6) root.left.right = TreeNode(8)

আউটপুট

True