Python(收益):从叶到树的根的所有路径 [英] Python (yield): all paths from leaves to root in a tree

查看:180
本文介绍了Python(收益):从叶到树的根的所有路径的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我想生成从每片叶子到树的根的所有路径.我想使用生成器来做到这一点,以节省内存(树可能很大).这是我的代码:

I want to generate all paths from every leaf to root in a tree. I'd like to do that with generators, to save memory (tree can be big). Here's my code:

def paths(self, acc=[]):
    if self.is_leaf():
        yield [self.node]+acc

    for child in self.children:
        child.paths([self.node]+acc)

但是它不起作用.为什么?从根调用,它从上到下遍历树,并在"acc"中收集节点.每个叶子都应返回"acc" ...

But it doesn't work. Why? Invoked at root, it traverses the tree from top to bottom, collecting nodes in "acc". "acc" should be returned in every leaf...

is_leaf()为true.

is_leaf() is true if self.children is empty.

推荐答案

此代码仅产生作为(立即)根子级的叶子.另一个函数被访问,它们屈服于上层函数,但是上层函数对它们不执行任何操作.您需要的是将它们从较低的功能转换为较高的功能:

This code only yields leaves that are (immediate) children of the root. The other ones get visited, they yield to the upper function, but the upper function does nothing with them. What you need is to yield them from the lower function to the upper one:

def paths(self, acc=[]):
    if self.is_leaf():
        yield [self.node]+acc

    for child in self.children:
        for leaf_path in child.paths([self.node]+acc): # these two
            yield leaf_path                            # lines do that

这应该可以解决问题.

这篇关于Python(收益):从叶到树的根的所有路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆