Зацикливается поиск минимума по бинарному дереву

Рейтинг: -1Ответов: 2Опубликовано: 16.06.2023

Есть класс, бинарное дерево, в нем метод поиска наименьшего:

    def get_min(self):
        print('Start finding minimum')
        return self._get_min(self.root)

    def _get_min(self, root):
        print(root.value)
        if root.child_l:
            return self._get_min(root.child_l)
        else:
            print('Found!')
            return root

При вызове метод бесконечно перезапускается, вот что вижу:

Start finding minimum
4.47213595499958
4.242640687119285
2.0
0.7999999999999998
Found!
4.47213595499958
4.242640687119285
2.0
0.7999999999999998
Found!
0.7999999999999998
4.242640687119285
2.0
0.7999999999999998

Я что то упускаю...

python рекурсия
Источник: Stack Overflow на русском

Ответы

▲ 1

Приведенные методы поиска вполне рабочие, ничего не зацикливается. Проблема у вас где-то в другом месте.

Я дополнил код до минимального рабочего, в самих методах только минимальные изменения (возвращаю значение, а не узел со значением, и убрал print-ы):

import random


class Node:
    def __init__(self, value, child_l=None, child_r=None):
        self.value = value
        self.child_l = child_l
        self.child_r = child_r
    
    def __repr__(self):
        return f"{type(self).__name__}({self.value!r}, {self.child_l!r}, {self.child_r!r})"


class BinaryTree:
    def __init__(self, root=None):
        assert root is None or isinstance(root, Node)
        self.root = root
    
    def _insert(self, node, value):
        if node is None:
            node = Node(value)
        elif value < node.value:
            node.child_l = self._insert(node.child_l, value)
        else:
            node.child_r = self._insert(node.child_r, value)
        
        return node
    
    def insert(self, value):
       self.root = self._insert(self.root, value)
    
    def _get_min(self, node):
        if node.child_l:
            return self._get_min(node.child_l)
        else:
            return node.value
    
    def get_min(self):
        return self._get_min(self.root)
        
    def __repr__(self):
        return f"{type(self).__name__}(root={self.root})"


tree = BinaryTree()

values = [random.randint(1, 1000) for _ in range(5)]
for value in values:
    tree.insert(value)

print("Values:", values)
print("Tree:", tree)
print("Min from tree:", tree.get_min())
print("Min from list:", min(values))

Пример вывода:

Values: [335, 246, 238, 59, 379]
Tree: BinaryTree(root=Node(335, Node(246, Node(238, Node(59, None, None), None), None), Node(379, None, None)))
Min from tree: 59
Min from list: 59
▲ -1

Мой косяк, конечно же тут

return self._get_min(root.child_l)

не должно быть return