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

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

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

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

将产生：

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

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

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

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 branchEXITING CHILD: Node(C)EXITING CHILD: Node(B)ENTERING CHILD: Node(D)ON NODE: Node(D)['A','D']  # yIElded branchEXITING 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

我知道我对列表做错了,因为它在空时尝试d出,但是我不明白它是怎么做到的.它应该为每个追加调用调用一次pop.

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

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

在此先感谢您的帮助！

最佳答案这是您的代码的修改后的变体.

code.py：

#!/usr/bin/env python3import sysclass 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-产生二叉树的所有从根到叶的分支 所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。