पायथन में बाइनरी ट्री पूर्ण है या नहीं यह जांचने के लिए प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें यह जांचना होगा कि यह पूर्ण बाइनरी ट्री है या नहीं। जैसा कि हम एक पूर्ण बाइनरी ट्री में जानते हैं कि संभवतः अंतिम को छोड़कर स्तर नोड्स से भरे हुए हैं और अंतिम स्तर में सभी नोड्स जितना संभव हो सके छोड़े गए हैं।

तो, अगर इनपुट पसंद है

तो आउटपुट सही होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे-

• q :=एक डबल एंडेड कतार

• q के अंत में रूट डालें

• झंडा :=झूठा

• जबकि q खाली नहीं है, करें

  • अस्थायी:=क्यू के बाईं ओर से हटाने के बाद तत्व

  • अगर अस्थायी शून्य है, तो

    • झंडा :=सच

  • अन्यथा जब ध्वज सेट होता है और अस्थायी शून्य नहीं होता है, तब

    • झूठी वापसी

  • अन्यथा,

    • 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