python - Python中以自定义方式进行树遍历？

Question

我在 python 中有两棵树。我需要根据以下规范以定制的方式对它们进行比较。假设我有实体 E1 的树和实体 E2 的树。我需要从 E1 和 E2 开始遍历两棵树，然后向上移动，直到到达共同的根。 (请注意，我必须从第一棵树上的节点 E1 和第二棵树上的节点 E2 开始遍历。)然后我需要比较它们两个路径的长度计数。 p>

有人可以告诉我如何在 Python 中执行此操作吗？经典的树遍历算法在这里有用吗？

Answer 1

这不是“遍历”(访问树中的每个节点)；你所描述的只是跟随 parent 。

该算法如下所示。技巧之一是交错计算，以便保证算法快速终止。您还必须考虑诸如 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)