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

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

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

将产生：

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

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

在某些时候,尽管出了点问题.这是我的代码：

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.

我也无法弄清楚为什么要输入和退出节点,但是没有显示ON NODE：消息…就像我的代码以某种方式跳过child.traverse(branch = branch)行一样？

谁能帮助我了解我在哪里搞砸了？

在此先感谢您的帮助！

最佳答案

这是您的代码的修改后的变体.

code.py：

#!/usr/bin/env python3
import sys
class Node:
    def __init__(self,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属性为None,表示该节点没有子节点,因此在返回的结果中没有将其包括在内的任何点
>由于问题涉及产量,因此我将其变成了生成器(而不是返回元组或列表,…).结果,我必须添加is_leaf,因为生成器的结果不会为False(即使为空)

输出：

06001

您的代码有什么问题？

这是遍历重复调用(child.traverse(branch = branch)).它创建了一个生成器,但是由于没有在任何地方使用(迭代)该生成器,因此该函数实际上并未调用自身,从而导致尝试删除的元素多于添加的元素(只有1：这是根节点).因此,事实证明您已经快到了.您所要做的就是在其前面添加一个产量:).有关[Python]: PEP 380 — Syntax for Delegating to a Subgenerator的更多详细信息.

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

猜你在找的Python相关文章