पायथन में बाइनरी ट्री में दो नोड्स के बीच की दूरी खोजने का प्रोग्राम

मान लीजिए हमें एक बाइनरी ट्री दिया गया है और हमें बाइनरी ट्री में दो नोड्स के बीच की दूरी ढूंढनी है। हम दो नोड्स के बीच के एज को ग्राफ की तरह ढूंढते हैं और उनके बीच एज की संख्या या दूरी वापस करते हैं। ट्री के नोड की संरचना नीचे दी गई है:

data: 
right: 
left: 

उदाहरण के लिए, यदि इनपुट है:

और जिन नोड्स के बीच हमें दूरी ढूंढनी है वे 2 और 8 हैं; तो आउटपुट 4 होगा।

दो नोड्स 2 और 8 के बीच के एज हैं: (2, 3), (3, 5), (5, 7), और (7, 8)। उनके बीच पथ में 4 एज हैं, इसलिए दूरी 4 है।

हल करने के चरण

1. findLca() फ़ंक्शन परिभाषित करें। यह root, p, q लेगा:
   • यदि root is None, तो None वापस करें।
   • यदि root का डेटा (p,q) में से कोई है, तो root वापस करें।
   • left := findLca(root.left, p, q)
   • right := findLca(root.right, p, q)
   • यदि left और right दोनों नॉन-नल हैं, तो root वापस करें।
   • left or right वापस करें।
2. findDist() फ़ंक्शन परिभाषित करें। यह root, data लेगा:
   • queue := नया deque
   • (root, 0) जोड़ी को queue के अंत में डालें
   • queue खाली न होने तक व्हाइल लूप चलाएं:
     • current := queue में सबसे बाईं जोड़ी का पहला मान
     • dist := queue में सबसे बाईं जोड़ी का दूसरा मान
     • यदि current का डेटा data के बराबर है, तो dist वापस करें।
     • यदि current.left नॉन-नल है, तो (current.left, dist+1) जोड़ी को queue में जोड़ें।
     • यदि current.right नॉन-नल है, तो (current.right, dist+1) जोड़ी को queue में जोड़ें।
3. node := findLca(root, p, q)
4. findDist(node, p) + findDist(node, q) वापस करें।

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

import collections
class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def insert(temp, data):
    que = []
    que.append(temp)
    while len(que):
        temp = que[0]
        que.pop(0)
        if not temp.left:
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

def search_node(root, element):
    if root is None:
        return None
    if root.data == element:
        return root
    res1 = search_node(root.left, element)
    if res1:
        return res1
    res2 = search_node(root.right, element)
    return res2

def findLca(root, p, q):
    if root is None:
        return None
    if root.data in (p, q):
        return root
    left = findLca(root.left, p, q)
    right = findLca(root.right, p, q)
    if left and right:
        return root
    return left or right

def findDist(root, data):
    queue = collections.deque()
    queue.append((root, 0))
    while queue:
        current, dist = queue.popleft()
        if current.data == data:
            return dist
        if current.left:
            queue.append((current.left, dist + 1))
        if current.right:
            queue.append((current.right, dist + 1))

def solve(root, p, q):
    node = findLca(root, p, q)
    return findDist(node, p) + findDist(node, q)

root = make_tree([5, 3, 7, 2, 4, 6, 8])
print(solve(root, 2, 8))

इनपुट

root = make_tree([5, 3, 7, 2, 4, 6, 8]) print(solve(root, 2, 8))

आउटपुट

4