产生二叉树的所有从根到叶的分支 [英] Yield all root-to-leaf branches of a Binary Tree

问题描述

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

Sorry if this is a common question but I haven't found an appropriate answer for my particular problem. I'm trying to implement a walk method that walks a binary tree from its root node to each of its leaf nodes, yielding the root-to-leaf path whenever I get to a leaf node. For example, walking the binary tree represented by:

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

会产生:

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

我的想法是， BinaryTree.walk 调用根节点上的 Node.traverse ，后者依次调用每个子节点的 traverse 方法递归节点. BinaryTree.walk 还会创建一个空列表，该列表随每个 traverse 调用一起传递，附加每个节点的数据，一旦到达叶节点，就产生该列表并弹出每个列表访问每个节点后将元素从列表中移出.

My idea is that BinaryTree.walk calls Node.traverse on the root node, which in turn calls the traversemethod of each child node recursively. BinaryTree.walk also creates an empty list which is passed around with each traverse call, appending the data of each node, yielding the list once a leaf node is reached and popping each element out of the list after visiting each node.

在某些时候，虽然出了点问题.这是我的代码:

At some point, something is going wrong though. This is my code:

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

我知道我对列表做错了，因为它在空时尝试弹出，但是我不明白它是如何实现的.对于每个 append 调用，它应该调用一次 pop .

I understand I'm doing something wrong with the list since it's trying to pop when it's empty, but I can't understand how it got to that. It should call pop once for each append call.

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

Also I can't figure out why the nodes are being entered and exited, but the ON NODE: message is not being printed... It's like my code just skips the child.traverse(branch=branch) line somehow?

有人可以帮助我了解我在哪里搞砸吗?

Can anyone help me understand where I'm messing this up?

提前感谢您的帮助！

推荐答案

这是您代码的修改版本.

Here's a modified variant of your code.

code.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()

注释:

• 我对代码进行了一些重构(简化，更改了一些标识符名称，文本和其他无关紧要的更改)
• 子项属性:
  节点的 left 或 right 属性的
  • 无
  • 由于该问题涉及 yield ，因此我将其变成了生成器(而不是返回元组或列表，...).结果，我不得不添加 is_leaf ，因为生成器不会将其评估为 False (即使为空)
  • I refactored the code a bit (simplified, changed some identifier names, texts and other insignificant changes)
  • children property:
    • None for a node's left or right attribute, means that the node has no child, so no point including it in the returned result
    • Since the question is involving yield, I turned it into a generator (instead of returning a tuple or list, ...). As a consequence, I had to add is_leaf, since a generator doesn't evaluate to False (even if empty)

    输出:

    [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)
    

    
    

    这是遍历重复调用( child.traverse(branch = branch)).它创建了一个生成器，但是由于未在任何地方使用(迭代)该函数，因此实际上并未对其本身进行调用，导致尝试删除比添加的元素更多的元素(仅 1 :这是根节点).
    所以，事实证明您已经快到了.您所要做的就是在其前面添加 的收益:).
有关> [Python]:PEP 380-委派给子生成器的语法的详细信息.

    It's the traverse recurring call (child.traverse(branch=branch)). It created a generator, but since that wasn't used (iterated on) anywhere, the function didn't actually called itself, resulting in the attempt of removing more elements than added (only 1: which is the root node).
    So, it turns out that you were almost there. All you have to do, is adding a yield from in front of it :).
    More details on [Python]: PEP 380 -- Syntax for Delegating to a Subgenerator.

    这篇关于产生二叉树的所有从根到叶的分支的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！