मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें इस बाइनरी ट्री में अधिकतम पूर्ण उप-वृक्ष का आकार खोजना होगा। जैसा कि हम जानते हैं कि एक पूर्ण बाइनरी ट्री एक बाइनरी ट्री है यदि सभी स्तर पूरी तरह से बिना संभावित अंतिम स्तर के भरे हुए हैं और अंतिम स्तर में यथासंभव सभी कुंजियाँ हैं।
तो, अगर इनपुट पसंद है
तो आउटपुट 4 आकार के रूप में होगा और इनऑर्डर ट्रैवर्सल 10, 45, 60, 70,
होगाइसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- isComplete, isPerfect जैसे कुछ मापदंडों के साथ वापसी प्रकार को परिभाषित करें, ये शुरू में झूठे हैं, फिर आकार और रूटट्री, आकार शुरू में 0 है और रूटट्री शून्य है।
- ret_type :=returnType
- यदि रूट रिक्त है, तो
- ret_type.isPerfect :=True
- ret_type.isComplete :=True
- ret_type.size:=0
- ret_type.rootTree :=कोई नहीं
- रिटर्न रिट_टाइप
- left_tree :=checkCompletness(root.left)
- right_tree :=checkCompletness(root.right)
- अगर (left_tree.isPerfect सही है और right_tree.isComplete सही है और बाएं और दाएं पेड़ की ऊंचाई समान है, तो
- ret_type.isComplete :=True
- ret_type.isPerfect :=right_tree.isPerfect
- ret_type.size:=left_tree.size + right_tree.size + 1
- ret_type.rootTree :=root
- रिटर्न रिट_टाइप
- अगर (left_tree.isComplete is True और right_tree.isPerfect सही है और बाएं और दाएं पेड़ की ऊंचाई समान है, तो
- ret_type.isComplete :=True
- ret_type.isPerfect :=False
- ret_type.size:=left_tree.size + right_tree.size + 1
- ret_type.rootTree :=root
- रिटर्न रिट_टाइप
- ret_type.isPerfect :=False
- ret_type.isComplete:=असत्य
- ret_type.size :=अधिकतम left_tree.size, right_tree.size
- अगर left_tree.size> right_tree.size, तो
- ret_type.rootTree :=left_tree.rootTree
- अन्यथा,
- ret_type.rootTree :=right_tree.rootTree
- रिटर्न रिट_टाइप
पायथन
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
import math
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
class returnType :
def __init__(self):
self.isPerfect = None
self.isComplete = None
self.size = 0
self.rootTree = None
def getHeight(size):
return int(math.ceil(math.log(size + 1)/math.log(2)))
def checkCompleteness(root) :
ret_type = returnType()
if (root == None):
ret_type.isPerfect = True
ret_type.isComplete = True
ret_type.size = 0
ret_type.rootTree = None
return ret_type
left_tree = checkCompleteness(root.left)
right_tree = checkCompleteness(root.right)
if (left_tree.isPerfect == True and right_tree.isComplete == True and getHeight(left_tree.size) == getHeight(right_tree.size)) :
ret_type.isComplete = True
ret_type.isPerfect = right_tree.isPerfect
ret_type.size = left_tree.size + right_tree.size + 1
ret_type.rootTree = root
return ret_type
if (left_tree.isComplete == True and right_tree.isPerfect == True and getHeight(left_tree.size) == getHeight(right_tree.size) + 1):
ret_type.isComplete = True
ret_type.isPerfect = False
ret_type.size = left_tree.size + right_tree.size + 1
ret_type.rootTree = root
return ret_type
ret_type.isPerfect = False
ret_type.isComplete = False
ret_type.size =max(left_tree.size, right_tree.size)
if(left_tree.size > right_tree.size ):
ret_type.rootTree = left_tree.rootTree
else:
ret_type.rootTree = right_tree.rootTree
return ret_type
def print_tree(root):
if root is not None:
print_tree(root.left)
print(root.data, end = ', ')
print_tree(root.right)
root = TreeNode(50)
root.left = TreeNode(30)
root.right = TreeNode(60)
root.left.left = TreeNode(5)
root.left.right = TreeNode(20)
root.right.left = TreeNode(45)
root.right.right = TreeNode(70)
root.right.left.left = TreeNode(10)
ans = checkCompleteness(root)
print( "Size:" , ans.size )
print("Inorder Traversal: ", end = '')
print_tree(ans.rootTree) इनपुट
root = TreeNode(50) root.left = TreeNode(30) root.right = TreeNode(60) root.left.left = TreeNode(5) root.left.right = TreeNode(20) root.right.left = TreeNode(45) root.right.right = TreeNode(70) root.right.left.left = TreeNode(10)
आउटपुट:
Size: 4 Inorder Traversal: 10, 45, 60, 70,