Блог

У меня есть реализация двоичного дерева, как показано ниже. Я хотел бы добавить метод, который рекурсивно суммирует все значения узлов двоичного дерева:

 class BST

  class Node
    attr_reader :value, :left, :right

    def initialize(value)
      @value = value
      @left = nil
      @right = nil
    end

    def insert(value)
      if value <= @value
        @left.nil? ? @left = Node.new(value) : @left.insert(value)
      elsif value > @value
        @right.nil? ? @right = Node.new(value) : @right.insert(value)
      end
    end

  end

  def initialize
    @root = nil
  end

  def insert(value)
    @root.nil? ? @root = Node.new(value) : @root.insert(value)
  end

end
  

Я нашел ответ для других языков, но, к сожалению, не для Ruby.

Я думаю, что ваш код в комментариях был:

 def sum(node=@root)
  return if node.nil?
  total  = node.value
  sum(node.left)
  sum(node.right)
end
  

Идея почти в порядке. В nil узлах нет суммирования; и вы суммируете значение текущего узла, левого узла и правого узла. Вот ошибки:

• total = node.value это мы видим впервые total . Это инициализирует его nil . Когда вы пытаетесь добавить к нему node.value , вы получаете описанную вами ошибку. Чтобы избежать этого, оно total должно уже существовать, или вы можете просто присвоить node.value ему значение.

• Если функция завершается без выполнения return инструкции, она возвращает последнее вычисленное выражение; в данном случае sum(node.right) . Не было бы лучше, если бы sum возвращалось total ?

• И наоборот, sum(node.left) предположительно, выполнит некоторое суммирование… но его возвращаемое значение отбрасывается. Возможно, имеет смысл добавить это в total . Говоря об итогах, возможно, нам следует сделать то же самое для sum(node.right) .

• Наконец, return if node.nil? говорится, что вы отказываетесь суммировать узлы, которые на самом деле не являются узлами. Это здорово … за исключением того, что это return возвращает nil , и если вы попытаетесь с чем-то суммировать a nil , это не сработает. Здесь есть два решения: отказаться от суммирования узла перед его вводом или сказать, что нулевой узел имеет значение 0, которое не влияет на сумму.

Собрав все это вместе, вот мои две версии:

 # refuse to enter a nil node:
def sum(node=@root)
  total = node.value
  total  = sum(node.left) unless node.left.nil?
  total  = sum(node.right) unless node.right.nil?
  total
end

# treat nil nodes as if they were zeroes:
def sum(node=@root)
  return 0 if node.nil?
  node.value   sum(node.left)   sum(node.right)
end