打印二叉树中所有可能的路径

Question

打印二叉树中所有可能的路径

3

我正在尝试打印二叉树中所有可能的路径。我能够打印出所有从根到叶子节点的路径，但无法想出如何添加从叶子节点到叶子节点的路径（我使用先序遍历进行从根到叶子节点的遍历）。

所以，基本上：

如果我的树是：

       6
     /    \
    4      0
   / \      \
  1   3      1

如果想让代码打印出所有的路径：

6,4,1
6,4,3
6,0,1
1,4,6,0,1
3,4,6,0,1 
1,4,3  
4,6,0  
4,6,0,1  
etc.

有人能帮我解决这个二叉树问题吗？我真的很感激你们的帮助，因为我是新来的，对Python/Java也不熟悉。

谢谢。

- user9436638

最后，4,6,0 是有效的吗？也就是说，你是要找到所有从根节点到叶子节点的路径以及所有叶子节点之间的路径，还是要找到任意两个节点之间的所有可能路径？ - Zachary Cross

没想到这个。实际上我需要所有的路径。所以，4、6、0也应该在路径列表中。 - user9436638

请将您在注释中添加的附加信息放入问题中。看起来您想要树中任意一对节点的路径，因此，由于您的示例树具有6个节点，您想要6*5//2 == 15条路径。这正确吗？此外，请展示您用于二叉树的数据结构--这将影响任何答案。 - Rory Daulton

问题规模有多大？对于如此小的树，您可以简单地使用暴力方法：有5条边，因此有2^5=32种组合来添加/删除一条边。现在对于每个边缘组合，检查两个约束条件：（a）边缘必须形成单个连接路径，（b）每个顶点最多连接2条边。 - Harry

这只是一个例子，但我希望能将其推广到更大的问题上。 - user9436638

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Olivier Melançon · Accepted Answer

树的一个显著特点是对于节点 (x, y) 的每种组合，存在一条独特的非重复路径从 x 到 y。特别地，可以通过找到 x 和 y 的第一个共同祖先 z 并取路径 x->z+z->y 来找到此路径。

因此，查找所有路径的算法可能如下所示：

for each pair of distinct nodes x, y in the tree:
    find all common ancestors of x and y
    let z be the lowest common acestor in the tree
    let p be the path from x to z
    append the path from z to y to p, excluding the duplicate z
    print p

这里提供了一种面向对象的方法，实现所需的方法以完成上述任务。

class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
        self.parent = None

        if left is not None:
            left.parent = self

        if right is not None:
            right.parent = self

    def __iter__(self):
        """Return a left-to-right iterator on the tree"""
        if self.left:
            yield from iter(self.left)
        yield self
        if self.right:
            yield from iter(self.right)

    def __repr__(self):
        return str(self.value)

    def get_ancestors(self):
        """Return a list of all ancestors including itself"""
        ancestors = {self}
        parent = self.parent
        while parent:
            ancestors.add(parent)
            parent = parent.parent

        return ancestors

    def get_path_to_ancestor(self, ancestor):
        """
        Return the path from self to ancestor as a list
        output format: [self, ..., ancestor]
        """
        path = []
        parent = self
        try:
            while True:
                path.append(parent)
                if parent is ancestor:
                    break
                else:
                    parent = parent.parent
        except AttributeError:
            return None

        return path

    def get_path_to(self, other):
        """
        Return the path from self to other as a list
        output format: [self, ..., first common acestor, ..., other]
        """
        common_ancestors = self.get_ancestors() & other.get_ancestors()
        first_common_ancestor = {
            a for a in common_ancestors
            if a.left not in common_ancestors and a.right not in common_ancestors
        }.pop()

        return self.get_path_to_ancestor(first_common_ancestor)\
               + list(reversed(other.get_path_to_ancestor(first_common_ancestor)))[1:]

以下是针对您提供的树作为示例的应用方法。

tree = Tree(
    6,
    Tree(4,
         Tree(1),
         Tree(3)),
    Tree(0,
         Tree(1)))

nodes = list(tree)

for i in range(len(nodes)):
    for j in range(i + 1, len(nodes)):
        print([t for t in nodes[i].get_path_to(nodes[j])])

以下是所有被打印的路径。

[1, 4]
[1, 4, 3]
[1, 4, 6]
[1, 4, 6, 0, 1]
[1, 4, 6, 0]
[4, 3]
[4, 6]
[4, 6, 0, 1]
[4, 6, 0]
[3, 4, 6]
[3, 4, 6, 0, 1]
[3, 4, 6, 0]
[6, 0, 1]
[6, 0]
[1, 0]