时间戳

首页 > 解决方案 > Ruby，这个二叉树正确吗？

ruby - Ruby，这个二叉树正确吗？

问题描述

所以我通过 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

我已经完成了一些基本的打印功能，它似乎工作正常，但我想知道这对于其他更了解 ruby​​ 的人来说是否正确。（旁注：我意识到这不处理重复的数字）。我是否缺少树的“建筑”部分的东西。

我关心的原因是看到了很多不同的“构建”实现。例如，一个从中点开始，还是仅用于“排序”数组？

标签： rubybinary-search-tree

解决方案

欢迎来到红宝石世界！当心你可能真的很喜欢它并且永远不会回到另一种语言:)

以下是我可以给你的一些评论：

测试

当您想知道您的代码是否正确时，第一件事就是使用不同的输入对其进行测试。您可以在控制台中手动完成，也可以编写在开发过程中跟随您的测试。

通过打印

测试您所做工作的一种快速方法是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.rbifbinary_tree.rb是您放置代码的文件来运行它。

正如您所提到的，您将在那里看到重复的代码不起作用。您可以通过删除块中的条件来使其工作if…elsif。

然后，您可以根据需要处理代码并运行测试，这样您就可以确信自己没有破坏任何东西。

每次遇到边缘情况时，您都不确定您的代码是否可以处理，只需将其放入测试中即可。

计算节点

Node.nodes如果应该计算二叉树中的节点数，您的方法可能不是您想要的。它应该在 a 的实例中Node，而不是在类本身中：如果您有几棵树，则每棵树都会考虑所有节点。

红宝石的东西

你写的一些东西在 ruby​​ 中可以用不同的方式表达：

没有必要

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)并不能真正帮助理解这两个参数的用途。我知道一个节点应该有一个值，但是第二个参数是什么？

你可以定义：

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

并用Node.new(value, parent: node), 或Node.new(value)

面向对象的东西

将方法移到它们所属的地方

你的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 之旅有所帮助。

推荐阅读