मान लीजिए हमारे पास एक बाइनरी सर्च ट्री (BST) है, हमें उसका माध्यिका ढूंढना है। हम जानते हैं कि सम संख्या में नोड्स के लिए, माध्यिका = ((n/2वां नोड + (n+1)/2वां नोड) / 2। विषम संख्या में नोड्स के लिए, माध्यिका = (n+1)/2वां नोड।
तो, यदि इनपुट इस तरह है
तो आउटपुट 7 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
यदि root, None के समान है, तो
0 वापस करें
node_count := ट्री में नोड्स की संख्या
count_curr := 0
current := root
जब current null नहीं है, करें
यदि current.left null है, तो
count_curr := count_curr + 1
यदि node_count mod 2, 0 नहीं है और count_curr, (node_count + 1) / 2 के समान है, तो
previous.data वापस करें
अन्यथा जब node_count mod 2, 0 है और count_curr, (node_count/2) + 1 के समान है, तो
(previous.data + current.data) / 2 वापस करें
previous := current
current := current.right
अन्यथा,
previous := current.left
जब previous.right null नहीं है और previous.right, current के समान नहीं है, करें
previous := previous.right
यदि previous.right null है, तो
previous.right := current
current := current.left
अन्यथा,
previous.right := None
previous := previous
count_curr := count_curr + 1
यदि node_count mod 2, 0 नहीं है और count_curr, (node_count + 1) / 2 के समान है, तो
current.data वापस करें
अन्यथा जब node_count mod 2, 0 है और count_curr, (node_count / 2) + 1 के समान है, तो
(previous.data+current.data) / 2 वापस करें
previous := current
current := current.right
उदाहरण
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None def number_of_nodes(root): node_count = 0 if (root == None): return node_count current = root while (current != None): if (current.left == None): node_count+=1 current = current.right else: previous = current.left while (previous.right != None and previous.right != current): previous = previous.right if(previous.right == None): previous.right = current current = current.left else: previous.right = None node_count += 1 current = current.right return node_count def calculate_median(root): if (root == None): return 0 node_count = number_of_nodes(root) count_curr = 0 current = root while (current != None): if (current.left == None): count_curr += 1 if (node_count % 2 != 0 and count_curr == (node_count + 1)//2): return previous.data elif (node_count % 2 == 0 and count_curr == (node_count//2)+1): return (previous.data + current.data)//2 previous = current current = current.right else: previous = current.left while (previous.right != None and previous.right != current): previous = previous.right if (previous.right == None): previous.right = current current = current.left else: previous.right = None previous = previous count_curr+= 1 if (node_count % 2 != 0 and count_curr == (node_count + 1) // 2 ): return current.data elif (node_count%2 == 0 and count_curr == (node_count // 2) + 1): return (previous.data+current.data)//2 previous = current current = current.right root = TreeNode(7) root.left = TreeNode(4) root.right = TreeNode(9) root.left.left = TreeNode(2) root.left.right = TreeNode(5) root.right.left = TreeNode(8) root.right.right = TreeNode(10) print(calculate_median(root))
इनपुट
root = TreeNode(7) root.left = TreeNode(4) root.right = TreeNode(9) root.left.left = TreeNode(2) root.left.right = TreeNode(5) root.right.left = TreeNode(8) root.right.right = TreeNode(10)
आउटपुट
7
