Как пройти через дерево, чтобы найти наименьшее значение

Question

Учитывая график, начиная с указанного узла (например, оранжевого), как можно получить листовой узел с наименьшим значением (например, зеленым)?

Это не двоичный файл, поэтому один узел можетесть сотни детей.Детям не гарантируется, что они будут иметь более низкое значение, чем их родители.

Есть ли лучший способ, чем просто перебирать каждую отдельную ветвь?Если нет, то мы могли бы собрать все листья в набор, чтобы найти лист с наименьшей ценностью.

К сожалению, это будет очень дорого.

Answer 1

Обход дерева - это способ сделать такую ​​вещь, если в вашем дереве нет определенного свойства.
Этот псевдокод описывает возможный способ сделать это:

find_min(node):
    result = node.value
    for each child of node:
        child_min = find_min(child)
        if child_min < result:
            result = child_min
    return result

Но в конечном итоге выпридется идти через все ветви твоего дерева.Это потому, что, чтобы найти мин, вы должны пройти через все узлы вашего дерева и, таким образом, пройти его.В общем случае нет более быстрого метода, так как он выполняется в O(n), с n числом узлов в вашем дереве.
Это также самый простой метод, другие подходы были бы более сложными, и, следовательно, болееподвержен ошибкам.