Ruby - рекурсивный каждый для n-арного дерева - PullRequest
3 голосов
/ 02 мая 2011

Исправлено: см. РЕДАКТИРОВАТЬ, РЕДАКТИРОВАТЬ

Привет, ребята,

У меня проблемы с написанием собственного рекурсивного кода для n-арного дерева. @element - это значение узла, а @children - это массив всех подключенных нижних узлов. Это мой метод:

def each
  yield(@element)

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

Проблема в том, что он повторяет нижние элементы. Например, если я использую это, чтобы напечатать узел со значением o и одним дочерним элементом c, он напечатает 'occ' вместо 'oc'. Я действительно не знаю, что происходит, поэтому все мои попытки исправления оказались неэффективными. Есть идеи?

РЕДАКТИРОВАТЬ: Я думаю, что это может быть потому, что он каким-то образом вызывает каждый на значение узла в дополнение к его получению, поэтому, когда это строка из одного символа, он выдаст этот символ, а затем выдаст его снова с помощью вызова .each.

РЕДАКТИРОВАТЬ РЕДАКТИРОВАТЬ: Спасибо за чтение, все, но я все испортил. Проблема была не в этом методе, а в другом в том же классе, to_s. to_s напечатал бы правильно, но изменил бы значение родительского узла, если бы это была строка. Всякий раз, когда я проверял, я всегда сначала использовал tos и даже не осознавал этого. Извини за это. (Не могу позволить мне ответить на свой вопрос, так как я новичок).

1 Ответ

3 голосов
/ 02 мая 2011

Судя по вашему ответу, мне кажется, что вам нужно что-то вроде этого:

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.

...