Ruby - 递归遍历 n 叉树

Question

已修复：请参见EDIT EDIT

我在编写n叉树的递归each方法时遇到了问题。 @element 是节点的值，@children 是所有连接的下层节点的数组。这是我的方法：

def each
  yield(@element)

  @children.each { |x|
    x.each { |i| yield i}
  }
  self
end

问题在于它重复了下面的元素。例如，如果我使用这个来打印一个值为o且有一个子节点c的节点，它将打印'occ'而不是'oc'。我真的不知道发生了什么，所以我尝试的所有修复方法都无效。有任何想法吗？

编辑：我认为这可能是因为它在除了yield之外还在节点值上调用了each，所以当它是单个字符的字符串时，它将首先产生该字符，然后使用.each调用再次产生它。

编辑编辑：谢谢大家阅读，但我搞砸了。问题不在这个方法中，而是在同一个类中的另一个方法to_s中。to_s会正确打印，但如果它是字符串，它会更改父节点的值。每次测试时，我总是先使用to_s，甚至没有意识到它。对此感到抱歉。(作为新手，不能自己回答问题)。

- Nathan

---

这个类应该定义在哪里？你应该用一个类体来包围你的代码。 - sawa

你还应该描述一下如何在n叉树的实例上定义@element和@children。 - sawa

该类被省略了，因为我认为这是问题所在。但我现在也不确定了...@element和@children都传递给构造函数，@element作为任何对象，@children作为一个数组。 - Nathan

sawa，问班上的其他人是否也遇到了同样的问题。我发现了我的问题。在这个类中，一个名为to_s的独立方法改变了树的元素，但是打印出了正确的答案。我总是在使用each之前用那个方法进行测试，所以我确信each是有问题的。 - Nathan

Answer 1

根据您的回复，我认为您想要的是这样的东西：

class Tree
  def initialize element, children = []
    @element, @children = element, children
  end
  def each &pr
    pr.call(@element)
    @children.each{|x| x.each(&pr)}
    self
  end
end

a = Tree.new('self')
b = Tree.new('parent', [a])
c = Tree.new('grandparent', [b])

c.each{|x| puts x}
# => grandparent
# => parent
# => self

b.each{|x| puts x}
# => parent
# => self

需要注意的是，由于你似乎想要递归传递proc对象，因此最好将其作为参数获取，如&pr，而不是使用yield。

- sawa

---

看起来不错，但是不好的是，如果没有块来构建迭代器，你不能使用树对象的 each 方法。 - DeTeam