Обход дерева в Python?

Question

У меня есть два дерева в Python. Мне нужно сравнить их в соответствии со следующими характеристиками. Предположим, у меня есть дерево для сущности E1 и дерево для сущности E2 . Мне нужно пройти через оба дерева, начиная с E1 и E2 и двигаясь вверх, пока я не доберусь до общего корня. ( Обратите внимание, что мне нужно начать обход с узла E1 на первом дереве и узла E2 на втором дереве. ) Затем мне нужно сравнить количество длин обоих путей.

Может кто-нибудь дать мне представление о том, как это сделать в Python? Могут ли здесь быть полезны классические алгоритмы обхода дерева?

Answer 1

Это не «путешественник» (который посещает каждый узел в дереве); то, что вы описываете, просто следует за родителями.

Алгоритм будет выглядеть следующим образом. Одним из приемов является чередование вычислений, так что алгоритм гарантированно быстро завершится. Вы также должны рассмотреть такие случаи, как node1==node2. Это также алгоритм O(A+B=N), а не O(A*B=N^2), где мы учитываем расстояние между узлами и их самым младшим общим предком.

def findYoungestCommonAncestor(node1, node2):
    visited = set()
    if node1==node2:
        return node1
    while True:
        if node1 in visited:
            return node1
        if node2 in visited:
            return node2

        if not node1.parent and not node2.parent:
            return None
        if node1.parent:
            visited.add(node1)
            node1 = node1.parent
        if node2.parent:
            visited.add(node2)
            node2 = node2.parent

Узлы node1 и node2 могут быть частью леса (набора связанных деревьев), и это все равно должно работать.

Более элегантно было бы что-то вроде:

def ancestors(node):
    """
        an iterator of node, node.parent, node.parent.parent...
    """
    yield node
    while node.parent:
        yield node
        node = node.parent

def interleave(*iters):
    """
        interleave(range(3), range(10,16)) -> 0,10,1,11,2,12,13,14,15
    """
    ignore = object()
    for tuple in zip_longest(*iters, fillvalue=ignore):
        for x in tuple:
            if not x is ignore:
                yield x

def findYoungestCommonAncestor(node1, node2):
    # implementation: find first repeated value in interleaved ancestors
    visited = set()
    for node in interleave(ancestors(node1), ancestors(node2)):
        if node in visited:
            return node
        else:
            visited.add(node)

Answer 2

То, что они деревья, даже не имеет отношения к решению.Вы ищете, сколько потребуется времени, чтобы два односвязных (родительских) списка сошлись в одном и том же списке.Просто перейдите по ссылкам, но сохраняйте счетчик длины для каждого посещенного узла.Как только вы достигнете уже посещенного узла, суммируйте ранее найденный счетчик и новый.Это не сработает, если какой-либо из списков окажется круглым, но если они это сделают, это не совсем правильное дерево.Способ исправить это - отследить отдельные посещенные словари для каждой ветви;если вы достигнете узла, посещенного в его собственной ветви, вы можете прекратить обход этой ветви, поскольку нет смысла пересчитывать цикл.

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

Answer 3

def closest_common_ancestor(ds1, ds2):

        while ds1 != None:
                dd = ds2
                while dd != None:
                        if ds1 == dd:
                                return dd
                        dd = dd.parent
                ds1 = ds1.parent
        return None