Ruby: вычислить сумму всех значений узлов двоичного дерева. - PullRequest
Новая
       14

Ruby: вычислить сумму всех значений узлов двоичного дерева.

0 голосов
/ 06 марта 2019

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

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.

1 Ответ

0 голосов
/ 06 марта 2019

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

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, и если вы попытаетесь получить 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
...