Нахождение расстояния бинарного дерева поиска от root до заданного ключа c - PullRequest
Новая
       48

Нахождение расстояния бинарного дерева поиска от root до заданного ключа c

2 голосов
/ 16 марта 2020 
def distance(self, rootOfTree, key):

    if rootOfTree is None:

        return -1

    totalDist = -1

    if rootOfTree.key is key:
        return totalDist + 1

    else:
        totalDist = self.distance(rootOfTree.left, key)

        if totalDist >= 0:

            return totalDist + 1

        totalDist = self.distance(rootOfTree.right, key)

        if totalDist >= 0:

            return totalDist + 1

    return totalDist

Привет! Я пытаюсь закодировать с помощью рекурсии, найдя расстояние от root до заданного c узла, указанного в параметре "ключ". Но мне удалось только ввести два параметра в функцию, которая является root моего BST и ключ, который я хочу найти. Можно ли просто указать «ключ» и пройти через BST и найти «ключ» в функции

Это 2-я часть моего кода

print("Depth:", bst.distance(root, "I"))

1 Ответ

0 голосов
/ 17 марта 2020

Расстояние равно глубине, которую вам нужно пройти, чтобы найти ключевой узел. Вы должны увеличиваться на единицу на каждом уровне, но только если этот уровень содержит ключ. 

class Tree:
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None

def distance(root, key):
    if root is None:
        return -1
    if root.data is key: # it's the key
        return 0
    else:
        dl = distance(root.left, key)
        dr = distance(root.right, key)
        if dl != -1:
           return 1 + dl
        elif dr != -1:
           return 1 + dr
        else: # both are -1
           return -1

Для тестирования: 

root = Tree()
root.data = "1"
root.left = Tree()
root.left.data = "2"
root.right = Tree()
root.right.data = "3"

root.left.left = Tree()
root.right.left = Tree()
root.left.right = Tree()
root.right.right = Tree()
root.left.left.data = "4"
root.left.right.data = "5"
root.right.left.data = "6"
root.right.right.data = "7"

distance(root, "1")
distance(root, "2")
distance(root, "3")
distance(root, "4")

Результаты: 

>>> distance(root, "1")
0
>>> distance(root, "2")
1
>>> distance(root, "3")
1
>>> distance(root, "4")
2
>>> distance(root, "7")
2
>>> distance(root, "8")
-1
...