質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.60%

  • Ruby

    7335questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

  • アルゴリズム

    392questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ruby にて "no method error"が出ます

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 666

shocyu

score 10

ruby にて2分木を作るアルゴリズムを書いています(参考:紀平拓男、春日伸弥「アルゴリズムとデータ構造」SoftbankCreative)まず Binary_Tree_Node クラスを作成し、その中に insert_node, find_value, delete_tree, print_treeメソッドを作成しました。

後半のメイン処理の部分で、まず insert_node メソッドを呼び出す際に、”undefined method for Binary_Tree_Node class(no method error) のような形でエラーが出ます。以下のソースではクラスの中にクラスメソッドとして作成しているのですが、なぜエラーが出るのでしょうか?

教えていただけますと嬉しくぞんじます。よろしくお願いします。

(以下ソース)
#---------------------------------------------------------------------------------#
# Binary_Tree_Node クラス(2分木の1つのノード)
class Binary_Tree_Node

  #インスタンス変数は参照と更新可能
  attr_accessor :value
  attr_accessor :left
  attr_accessor :right

  #コンストラクタ
  def initialize(num = 0)
    @value = num
    @left = nil
    @right = nil
  end

  # insert_nodeメソッド=枝の挿入(num が親ノードより小さければ左、大きければ右)
  def insert_node(num, node)
    if (node.left == nil) && (node.right == nil)
      tree_root = Binary_Tree_Node.new
      return
    end

    if node.value > num
      if node.left != nil
        insert_node(num, node.left)
      else
        node.left = Binary_Tree_Node.new(num)
      end
    else
      if node.right != nil
        insert_node(num, node.right)
      else
        node.right = Binary_Tree_Node.new(num)
      end
    end

    return
  end
  # insert_nodeメソッド終わり

  # find_valueメソッド=探している値を持つ node を見つける
  def find_value(node, val)
    if node.value > val
      if node.left == nil
        return nil
      end

      return find_value(node.left, val)
    end

    if node.value < val
      if node.right == nil
        return nil
      end

      return find_value(node.right, val)
    end

    return node
  end
  # find_value メソッド終わり

  # delete_tree メソッド(ノードの削除)
  def delete_tree(val)
    node = Binary_Tree_Node.new
    parent_node = Binary_Tree_Node.new

    direction = 0

    # while 文で削除すべき対象を見つける
    while node != nil && node.value != val do
      if node.value > val
        parent_node = node
        node = node.left
        diretion = -1
      else
        parent_node = node
        node = node.right
        diretion = 1
      end
    end

    if node == nil
      #見つからなかった
      return false
    end

    # 左か右、どちらかが nil であった場合(両方 nil の場合も含む)
    if node.left == nil || node.right == nil
      if node.left == nil
        # 親のポインタを変更する
        if diretion == -1
          paretnt_node.left = node.right
        elsif diretion == 1
          parent_node.right = node.right
        elsif direction == 0
          tree_root = node.right
        end
      else
        # 親のポインタを変更する
        if direction == -1
          parent_node.left = node.left
        elsif direction == 1
          parent_node.right = node.left
        elsif direction == 0
          tree_root = node.left
        end
      end
    # 両者とも nil でなかった場合
    # node の左側の、最も大きな値(最も右側の値)を取得する
    else
      left_biggest = Binary_Tree_Node.new
      left_biggest = node.left
      parent_node = node
      direction = -1

      while left_biggest.right != nil
        parent_node = left_biggest
        left_biggest = left_biggest.right
        direction = 1
      end

      # left_biggest の値を node に代入し
      # left_biggest は左側の枝を入れる
      node.value = left_biggest.value

      if direction == -1
        parent_node.left = left_biggest.left
      else
        parent_node.right = left_biggest.left
      end
    end

    return true
  end
  # delete_tree メソッド終わり

  # print_tree メソッド(木の状態を出力する)
  def print_tree(depth, node)
    if node == nil
      return
    end

    print_tree(depth + 1, node.left)

    for i in 0..depth do
      print "   "
    end

    print node.value.to_s
    print "\n"
    print_tree(depth + 1, node.right)
  end
  # print_tree メソッド終わり

end
# Binary_Tree_Node クラス終わり
#---------------------------------------------------------------------------------#

#メイン処理(情報を入力し、木を作成(Binary_Tree_Node クラスメソッドを用いて))
i, action, N = 0, 0, 0
random_value = 0
tree_root = Binary_Tree_Node.new

puts "Start making tree"

for i in 0..10 do
  random_value = Random.rand(100)

  Binary_Tree_Node.insert_node(random_value, tree_root)
end

puts "Number of Trial"
N = gets.to_i
 
# N 回以下の処理を繰り返し(1:追加、2:検索、3:削除、4:終わり)
for i in 0..(N - 1) do
  Binary_Tree_Node.print_tree(0, tree_root)

  puts "Select Control"
  puts "1:add, 2:search, 3:delete, 4:end"
  action = gets.to_i

  case action
  when 1
    puts "Put number from 0 to 100"
    i = gets.to_i

    if i < 1 || i > 100
      redo
    end

    Binary_Tree_Node.insert_node(i, tree_root)
  when 2
    puts "Put the number to find"
    i = gets.to_i

    if Binary_Tree_Node.find_value(tree_root, i) != nil
      puts "The number" + i.to_s + "is found"
    else
      puts "The number" + i.to_s + "couldn't be found"
    end
  when 3
    puts "Put the number to delete"
    i = gets.to_i

    if Binary_Tree_Node.delete_tree(i)
      puts "The number" + i.to_s + "is deleted"
    else
      puts "The number" + i.to_s + "couldn't be found"
    end
  when 4
    return
  end
end
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

checkベストアンサー

+1

Binary_Tree_Node.insert_node(i, tree_root)
でエラーにならないようにしたいなら、
def self.insert_node(num, node )
のように insert_node は定義する必要があります。

このエラーを解消させただけではプログラムが動作しなかったので、それなりに動作するように変更をしてみました。
# coding: utf-8
#-----------------------------------------------#
# Binary_Tree_Node クラス(2分木の1つのノード)
class BinaryTreeNode
  # インスタンス変数は参照と更新可能
  attr_accessor :value, :left, :right

  # コンストラクタ
  def initialize(num = 0)
    @value = num
    @left  = nil
    @right = nil
  end

  # 節の挿入(num が親ノードより小さければ左、大きければ右, 同じなら何もしない)
  def insert_node!(num = 0)
    if @value == num
      # 何もしない
    else
      if num < @value
        if @left.nil?
          @left = BinaryTreeNode.new(num)
        else
          @left.insert_node!(num)
        end
      else
        if @right.nil?
          @right = BinaryTreeNode.new(num)
        else
          @right.insert_node!(num)
        end
      end
    end
  end

  # 探している値を持つ節を見つける
  def find_value(num)
    ans = nil
    if @value == num
      ans = self
    elsif num < @value
      ans = @left.find_value(num) if @left
    elsif @value < num
      ans = @right.find_value(num) if @right
    end
    ans
  end

  # node 以下の最小値の節を探す
  def serach_min(node)
    node = node.left while node.left
    node
  end

  # node 以下の最小値の節を削除する
  def delete_min!(node)
    return node.right unless node.left
    node.left = delete_min!(node.left)
    node
  end

  # node 以下の 値が num の節を削除
  def delete_tree!(node, num)
    if node
      if num == node.value
        if node.left.nil?
          return node.right
        elsif node.right.nil?
          return node.left
        else
          min_node   = serach_min(node.right)
          node.value = min_node.value
          node.right = delete_min!(node.right)
        end
      elsif num < node.value
        node.left = delete_tree!(node.left, num)
      else
        node.right = delete_tree!(node.right, num)
      end
    end
    node
  end

  # 木の状態を出力する
  def print_tree(depth = 0)
    @left.print_tree(depth + 1) if @left
    puts "#{'   ' * depth}#{@value}"
    @right.print_tree(depth + 1) if @right
  end
end

#-----------------------------------------------#
# メイン処理(情報を入力し、木を操作する)
tree_root = BinaryTreeNode.new

puts 'Start making tree.'
10.times do
  random_value = Random.rand(100)
  tree_root.insert_node!(random_value)
end

puts 'Number of Trial.'
action_count = gets.to_i
# 以下の処理を最大でn回だけ繰り返す。
action_count.times do
  puts 'Select Control. (a:add, s:search, d:delete, p:print, q:end)'
  case gets.strip.downcase
  when 'a'
    puts 'Put number.'
    num = gets.to_i
    tree_root.insert_node!(num)
  when 's'
    puts 'Put the number to find.'
    num = gets.to_i
    if tree_root.find_value(num)
      puts "The number #{num} is found."
    else
      puts "The number #{num} is not found."
    end
  when 'd'
    puts 'Put the number to delete.'
    num = gets.to_i
    if num == 0
      puts 'The tree_root can not delete.'
    elsif tree_root.find_value(num).nil?
      puts "The number #{num} couldn't be found."
    else
      tree_root.delete_tree!(tree_root, num)
      puts "The number #{num} is deleted."
    end
  when 'p'
    tree_root.print_tree
  when 'q'
    break # 終了
  end
end

2分木の操作例としては以下が参考になるかもしれません。
参考
- 2分木のデータ追加、サーチ、削除について http://ja.stackoverflow.com/questions/4721/
- Rubyで実装して楽しむ古典データ構造再入門(平衡木編) http://hama-du.hatenablog.com/entry/2014/12/07/182113

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/10/13 15:24

    katoyさん、本当にありがとうございます!修正いただいたコードを一通り理解してからお返事を差し上げようと思い、返信が遅くなりました。

    木構造がアルゴリズムの基本だということが深く理解できました。あとオブジェクト指向を用いる利点をさらに理解できました。

    ruby のコードはここまで美しく書けるんですね。また精進したいと思います。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.60%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • Ruby

    7335questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

  • アルゴリズム

    392questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。