python - 产生二叉树的所有根到叶分支

Question

抱歉，如果这是一个常见问题，但我还没有找到适合我的特定问题的答案。我正在尝试实现 walk将二叉树从其根节点遍历到其每个叶节点的方法，每当我到达叶节点时产生根到叶的路径。例如，遍历由以下内容表示的二叉树:

     __a__
    /     \
   b       d
  / \     / \
 -   c   -   -

会产生:

['a', 'b', 'c']
['a', 'd']

我的想法是BinaryTree.walk电话 Node.traverse在根节点上，它又调用 traverse每个子节点的递归方法。 BinaryTree.walk还创建了一个空列表，它与每个 traverse 一起传递调用，附加每个节点的数据，一旦到达叶节点就产生列表，并在访问每个节点后从列表中弹出每个元素。

但在某些时候，有些地方出了问题。这是我的代码:

class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def __repr__(self):
        return f"{self.__class__.__name__}({self.data})"

    @property
    def children(self):
        return self.left, self.right

    def traverse(self, branch):
        print('ON NODE:', self)
        branch.append(self.data)
        if self.left is None and self.right is None:
            yield branch
        else:
            for child in self.children:
                if child is not None:
                    print('ENTERING CHILD:', child)
                    child.traverse(branch=branch)
                    print('EXITING CHILD:', child)
                    branch.pop()


class BinaryTree:
    def __init__(self, root=Node()):
        if not isinstance(root, Node):
            raise ValueError(f"Tree root must be Node, not {type(root)}")
        self.root = root

    def __repr__(self):
        return f"{self.__class__.__name__}({self.root})"

    def walk(self):
        node = self.root
        branch = []
        yield from node.traverse(branch=branch)


if __name__ == '__main__':
    # create root node
    n0 = Node('A')
    # create binary tree with root node
    tree = BinaryTree(root=n0)
    # create others nodes
    n1 = Node(data='B')
    n2 = Node(data='C')
    n3 = Node(data='D')
    # connect nodes
    n0.left = n1
    n0.right = n3
    n1.right = n2

    # walk tree and yield branches
    for branch in tree.walk():
        print(branch)

预期输出:

ON NODE: Node(A)
ENTERING CHILD: Node(B)
ON NODE: Node(B)
ENTERING CHILD: Node(C)
ON NODE: Node(C)
['A', 'B', 'C']  # yielded branch
EXITING CHILD: Node(C)
EXITING CHILD: Node(B)
ENTERING CHILD: Node(D)
ON NODE: Node(D)
['A', 'D']  # yielded branch
EXITING CHILD: Node(D)

实际输出:

ON NODE: Node(A)
ENTERING CHILD: Node(B)
EXITING CHILD: Node(B)
ENTERING CHILD: Node(D)
EXITING CHILD: Node(D)
IndexError: pop from empty list

我知道我对列表做错了，因为它试图在它为空时弹出，但我不明白它是如何做到这一点的。它应该调用 pop每个append一次称呼。

我也不知道为什么要进入和退出节点，但是 ON NODE:消息未打印...就像我的代码只是跳过了 child.traverse(branch=branch)以某种方式行？

任何人都可以帮助我理解我哪里搞砸了吗？

预先感谢您的帮助!

Answer 1

这是您的代码的修改变体。

代码.py:

#!/usr/bin/env python3

import sys


class Node:
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def __repr__(self):
        return f"{self.__class__.__name__}({self.data})"

    @property
    def children(self):
        if self.left:
            yield self.left
        if self.right:
            yield self.right

    @property
    def is_leaf(self):
        return self.left is None and self.right is None

    def traverse_preord(self, accumulator=list()):
        print("  On node:", self)
        accumulator.append(self.data)
        if self.is_leaf:
            yield accumulator
        else:
            for child in self.children:
                print("  Entering child:", child)
                yield from child.traverse_preord(accumulator=accumulator)
                accumulator.pop()
                print("  Exiting child:", child)


def main():
    root = Node(data="A",
                left=Node(data="B",
                          right=Node(data="C")
                         ),
                right=Node(data="D",
                           #left=Node(data="E"),
                           #right=Node(data="F"),
                          )
               )
    for path in root.traverse_preord():
        print("Found path:", path)


if __name__ == "__main__":
    print("Python {:s} on {:s}\n".format(sys.version, sys.platform))
    main()

注意事项:

• 我稍微重构了代码(简化，更改了一些标识符名称、文本和其他无关紧要的更改)
• children 属性:
  • None 对于节点的 left 或 right 属性，意味着该节点没有子节点，因此没有必要将它包含在返回的结果中
  • 因为问题涉及yield，所以我把它变成了一个生成器(而不是返回一个元组或列表，...)。因此，我不得不添加 is_leaf，因为生成器的计算结果不会为 False(即使为空)

输出:

[cfati@CFATI-5510-0:e:\Work\Dev\StackOverflow\q055424449]> "e:\Work\Dev\VEnvs\py_064_03.07.03_test0\Scripts\python.exe" code.py
Python 3.7.3 (v3.7.3:ef4ec6ed12, Mar 25 2019, 22:22:05) [MSC v.1916 64 bit (AMD64)] on win32

  On node: Node(A)
  Entering child: Node(B)
  On node: Node(B)
  Entering child: Node(C)
  On node: Node(C)
Found path: ['A', 'B', 'C']
  Exiting child: Node(C)
  Exiting child: Node(B)
  Entering child: Node(D)
  On node: Node(D)
Found path: ['A', 'D']
  Exiting child: Node(D)

你的代码有什么问题？

这是 traverse 循环调用 (child.traverse(branch=branch))。 它创建了一个生成器，但由于它没有在任何地方使用(迭代)，该函数实际上并没有调用自己，导致尝试删除的元素多于添加的元素(仅< em>1:根节点)。
所以，原来你快到了。您所要做的就是在它前面添加一个 yield from :)。
更多详情请见[Python]: PEP 380 -- Syntax for Delegating to a Subgenerator .