Руби, это двоичное дерево правильно? - PullRequest
Новая
       13

Руби, это двоичное дерево правильно?

0 голосов
/ 16 мая 2018

Итак, я прохожу OdinProject и начинаю с части «BinaryTree».Я написал двоичное дерево, но только на C ++, используя указатели.Поэтому без указателей меня немного смущает то, как узлы соединяются: 

class Node

  attr_accessor :value, :parent, :left, :right
  @@nodes = 0

  def self.nodes
    @@nodes
  end

  def initialize(value, parent=nil)
    @value = value
    @parent = parent
    @left = nil
    @right = nil
    @@nodes += 1
  end

end


class BinaryTree

  def initialize
    @root = nil
  end

  def build_tree(arr)
    arr.each {|el| add_child(el,@root)}
    @root
  end

  def add_child(value,node)
    if @root.nil?
      @root = Node.new(value)
    else
      if value < node.value
        node.left.nil? ? node.left = Node.new(value,node) : add_child(value,node.left)
      elsif value > node.value
        node.right.nil? ? node.right = Node.new(value,node) : add_child(value,node.right)
      end
    end
    return node
  end

end

Я выполнил некоторые основные функции печати, и мне кажется, что он работает правильно, но мне было интересно, выглядит ли это правильнодругим, которые понимают рубин лучше.(Sidenote: я понимаю, что это не обрабатывает дубликаты номеров).Я что-то упускаю из-за "строительной" части дерева.

Причина, по которой я обеспокоен, состоит в том, чтобы увидеть множество различных реализаций "сборки".Например, тот, который начинается в средней точке, или это только для «отсортированных» массивов?

1 Ответ

0 голосов
/ 17 мая 2018

добро пожаловать в мир рубинов!Остерегайтесь, вам это действительно может понравиться, и вы никогда не вернетесь к другому языку:)

Вот несколько комментариев, которые я могу вам дать:

Тестирование

Первое, когда вам интересноКод правильный, чтобы проверить его с разными входами.Вы можете сделать это вручную, в консоли или написать тесты, которые будут следовать за вами во время разработки.

Путем печати

Быстрый способ тестирования того, что вы делаете, - определитьto_s метод в вашем Node классе.Например, это позволит проверить, упорядочено ли ваше дерево: 

class Node
  …
  def to_s
     "#{left} #{value} #{right}".strip
  end
end

to_s - это метод ruby ​​по умолчанию, используемый при преобразовании объекта в строку.Например, вы можете сделать: 

#> puts BinaryTree.new.build_tree([5, 9, 1, 6])
1 5 6 9

Проверяя

Для вашего спокойствия вы можете описать некоторые тесты, которые позволят вам написать код, изменить его и проверить егоеще работает.Я бы предложил minitest, чтобы сделать это легко. 

require 'minitest/autorun'

describe BinaryTree do
  before do
    @constructor = BinaryTree.new
  end

  describe 'when given an array' do
    it 'sorts it' do
      @constructor.build_tree([1, 3, 2]).to_s.must_equal '1 2 3'
    end
  end

  describe 'when given an array with duplicates' do
    it 'builds the correct tree' do
      @constructor.build_tree([1, 3, 2, 3]).to_s.must_equal '1 2 3 3'
    end
  end
end

Затем вы можете запустить его с помощью ruby -Ilib:test binary_tree.rb, если binary_tree.rb - это файл, в который вы положили свой код.

Вы увидите тамКак вы упомянули, дублированный код не работает.Вы можете заставить его работать, удалив условие в блоке if…elsif.

Затем вы захотите поработать над кодом и запустить тест так часто, как вам нравится, чтобы вы были уверены, что ничего не сломали.

Каждый раз, когда у вас есть крайний случай, вы не уверены, что ваш код обрабатывает, просто поместите это в тест.

Подсчет узлов

Вероятно, ваш Node.nodes методне то, что вы хотите, если предполагается, что он подсчитывает количество узлов в вашем двоичном дереве.Это должно быть в случае Node, а не в самом классе: если у вас есть несколько деревьев, все узлы учитываются для каждого дерева.

Рубиновые вещи

Некоторые извещи, которые вы пишете, могут быть выражены по-разному в ruby:

Nil не требуется

attr_accessor parent - синтаксический сахар для 

def parent
  @parent
end

def parent=(other)
  @parent = other
end

В ruby, если ваша переменная экземпляра @parent не объявлено, по умолчанию имеет значение nil, и вызов node.parent также вернет nil.

Вам не нужны эти две строки в инициализаторе: 

@left = nil
@right = nil

Возврат не требуется

Когда ваша последняя инструкция в методе является возвращением, вам не нужно ключевое слово return.Это то, что я сделал с помощью метода to_s, описанного выше.

Именованные параметры

Я думаю, что чистые именованные параметры чистее, когда они неочевидны.Например, вызов Node.new(value, node) на самом деле не помогает понять, для чего эти 2 параметра.Я получаю, что узел должен иметь значение, но что это за второй параметр?

Вы можете определить: 

def initialize(value, parent: nil)
  # Same as before
end

и вызвать его с помощью Node.new(value, parent: node) или Node.new(value)

OO вещи

Методы перемещения, где они принадлежат

Ваш метод BinaryTree#add_child должен быть на узле.Вы добавляете дочерний элемент к узлу.Переместите его туда, чтобы вам не понадобился второй параметр: add_child(value, node.right) становится node.right.add_child(value)

class Node
  ...
  def add_child(other_value)
    if other_value < value
      left.nil? ? self.left = Node.new(other_value, parent: self) : left.add_child(other_value)
    else
      right.nil? ? self.right = Node.new(other_value, parent: self) : right.add_child(other_value)
    end
  end
end

class BinaryTree
  ...
  def add_child(value)
    if @root.nil?
      @root = Node.new(value)
    else
      @root.add_child(value)
    end
    @root
  end
end

Пока вы там, вы также можете избавиться от build_tree в классе BinaryTree,и переместите его в Node.

Надеюсь, это поможет вам в вашем путешествии по Ruby.

...