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) のような形でエラーが出ます。以下のソースではクラスの中にクラスメソッドとして作成しているのですが、なぜエラーが出るのでしょうか?
教えていただけますと嬉しくぞんじます。よろしくお願いします。
(以下ソース)
ruby
1#---------------------------------------------------------------------------------# 2# Binary_Tree_Node クラス(2分木の1つのノード) 3class Binary_Tree_Node 4 5 #インスタンス変数は参照と更新可能 6 attr_accessor :value 7 attr_accessor :left 8 attr_accessor :right 9 10 #コンストラクタ 11 def initialize(num = 0) 12 @value = num 13 @left = nil 14 @right = nil 15 end 16 17 # insert_nodeメソッド=枝の挿入(num が親ノードより小さければ左、大きければ右) 18 def insert_node(num, node) 19 if (node.left == nil) && (node.right == nil) 20 tree_root = Binary_Tree_Node.new 21 return 22 end 23 24 if node.value > num 25 if node.left != nil 26 insert_node(num, node.left) 27 else 28 node.left = Binary_Tree_Node.new(num) 29 end 30 else 31 if node.right != nil 32 insert_node(num, node.right) 33 else 34 node.right = Binary_Tree_Node.new(num) 35 end 36 end 37 38 return 39 end 40 # insert_nodeメソッド終わり 41 42 # find_valueメソッド=探している値を持つ node を見つける 43 def find_value(node, val) 44 if node.value > val 45 if node.left == nil 46 return nil 47 end 48 49 return find_value(node.left, val) 50 end 51 52 if node.value < val 53 if node.right == nil 54 return nil 55 end 56 57 return find_value(node.right, val) 58 end 59 60 return node 61 end 62 # find_value メソッド終わり 63 64 # delete_tree メソッド(ノードの削除) 65 def delete_tree(val) 66 node = Binary_Tree_Node.new 67 parent_node = Binary_Tree_Node.new 68 69 direction = 0 70 71 # while 文で削除すべき対象を見つける 72 while node != nil && node.value != val do 73 if node.value > val 74 parent_node = node 75 node = node.left 76 diretion = -1 77 else 78 parent_node = node 79 node = node.right 80 diretion = 1 81 end 82 end 83 84 if node == nil 85 #見つからなかった 86 return false 87 end 88 89 # 左か右、どちらかが nil であった場合(両方 nil の場合も含む) 90 if node.left == nil || node.right == nil 91 if node.left == nil 92 # 親のポインタを変更する 93 if diretion == -1 94 paretnt_node.left = node.right 95 elsif diretion == 1 96 parent_node.right = node.right 97 elsif direction == 0 98 tree_root = node.right 99 end 100 else 101 # 親のポインタを変更する 102 if direction == -1 103 parent_node.left = node.left 104 elsif direction == 1 105 parent_node.right = node.left 106 elsif direction == 0 107 tree_root = node.left 108 end 109 end 110 # 両者とも nil でなかった場合 111 # node の左側の、最も大きな値(最も右側の値)を取得する 112 else 113 left_biggest = Binary_Tree_Node.new 114 left_biggest = node.left 115 parent_node = node 116 direction = -1 117 118 while left_biggest.right != nil 119 parent_node = left_biggest 120 left_biggest = left_biggest.right 121 direction = 1 122 end 123 124 # left_biggest の値を node に代入し 125 # left_biggest は左側の枝を入れる 126 node.value = left_biggest.value 127 128 if direction == -1 129 parent_node.left = left_biggest.left 130 else 131 parent_node.right = left_biggest.left 132 end 133 end 134 135 return true 136 end 137 # delete_tree メソッド終わり 138 139 # print_tree メソッド(木の状態を出力する) 140 def print_tree(depth, node) 141 if node == nil 142 return 143 end 144 145 print_tree(depth + 1, node.left) 146 147 for i in 0..depth do 148 print " " 149 end 150 151 print node.value.to_s 152 print "\n" 153 print_tree(depth + 1, node.right) 154 end 155 # print_tree メソッド終わり 156 157end 158# Binary_Tree_Node クラス終わり 159#---------------------------------------------------------------------------------# 160 161#メイン処理(情報を入力し、木を作成(Binary_Tree_Node クラスメソッドを用いて)) 162i, action, N = 0, 0, 0 163random_value = 0 164tree_root = Binary_Tree_Node.new 165 166puts "Start making tree" 167 168for i in 0..10 do 169 random_value = Random.rand(100) 170 171 Binary_Tree_Node.insert_node(random_value, tree_root) 172end 173 174puts "Number of Trial" 175N = gets.to_i 176 177# N 回以下の処理を繰り返し(1:追加、2:検索、3:削除、4:終わり) 178for i in 0..(N - 1) do 179 Binary_Tree_Node.print_tree(0, tree_root) 180 181 puts "Select Control" 182 puts "1:add, 2:search, 3:delete, 4:end" 183 action = gets.to_i 184 185 case action 186 when 1 187 puts "Put number from 0 to 100" 188 i = gets.to_i 189 190 if i < 1 || i > 100 191 redo 192 end 193 194 Binary_Tree_Node.insert_node(i, tree_root) 195 when 2 196 puts "Put the number to find" 197 i = gets.to_i 198 199 if Binary_Tree_Node.find_value(tree_root, i) != nil 200 puts "The number" + i.to_s + "is found" 201 else 202 puts "The number" + i.to_s + "couldn't be found" 203 end 204 when 3 205 puts "Put the number to delete" 206 i = gets.to_i 207 208 if Binary_Tree_Node.delete_tree(i) 209 puts "The number" + i.to_s + "is deleted" 210 else 211 puts "The number" + i.to_s + "couldn't be found" 212 end 213 when 4 214 return 215 end 216end
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2015/10/13 06:24