4706


「アルゴリズムとデータ構造」紀平拓男／春日伸弥 著
（<http://www.sbcr.jp/products/4797324198.html?sku=4797324198>）第6章において
、２分木へのデータの追加のコードが紹介されています。  
それを今Ruby版に置き換えたつもりなのですが、 **二つ目のデータの追加のとき** に上手く動かなくて困っています。  
どこを修正すればよいか教えていただけないでしょうか？

[code]

    # -*- coding: cp932 -*-
    
    # Node Class
    class Node
      attr_reader :value, :left, :right
      def initialize(val)
        @value = val   # ノードが保持する値
        @left = nil    # 左側のノード
        @right = nil   # 右側のノード
      end 
    end
    
    # ノードを生成する
    def create_new_node(val)
      newNode = Node.new(val)
      return newNode
    end
    
    # ノードの追加
    def insert_tree(num, node = nil)
      # 1つも挿入されていない場合
      if node == nil
        @tree_root = create_new_node(num)
        return
      end 
      # num が現在の node の値よりも小さい場合
      if node.value > num
        if node.left != nil
          insert_tree(num, node.left)
        else
          node.left = create_new_node(num)
        end
      # num が現在の node の値以上の場合
      else
        if node.right != nil
          insert_tree(num, node.right)
        else
          node.right = create_new_node(num)
        end
      end
    end
    
    def print_tree(depth, node = nil)
      if node == nil
        return
      end
      print_tree(depth + 1, node.left)
      i = 0
      while i < depth
        printf "   "
        i += 1
      end
      printf("%d\n",node.value)
      print_tree(depth + 1, node.right)
    end
    
    def main
      action = nil
      while action != 0
        print_tree(0, @tree_root)
        printf("実行する操作のタイプを入力してください。\n 1 ：追加\t2 ：検索\t3 ：削除\t それ以外：終了>")
        action = gets.chomp.to_i
        case action
          when 1
            printf("1 ～100の範囲で，追加する数字を入力してください:")
            i = gets.chomp.to_i
            if (i < 1 || i > 100)
              continue
            end
            insert_tree(i, @tree_root)
          else
            break
        end
      end
    end
    
    main
    
[/code]


CC BY-SA 3.0
2015-01-16T15:52:17.880
4704
2015-01-18T03:28:08.287
2015-01-17T05:47:30.160
33
5363
question
ruby アルゴリズム binary-tree
２分木へのデータの追加について


`attr_reader` を `attr_accessor` に変更すれば動くのではないでしょうか．  
`attr_reader` はgetterを自動生成するだけなので， `insert_tree(num, node = nil)` 内の

[code]

    node.left = create_new_node(num)
    node.right = create_new_node(num)
    
[/code]

のところでエラーになってしまうと思います．

ちなみに，

  * `attr_accessor` setter, getterを両方定義
  * `attr_reader` getterのみ定義
  * `attr_writer` setterのみ定義

となっています．


CC BY-SA 3.0
2015-01-16T16:59:17.353
4706
2015-01-16T16:59:17.353
5447
4704
answer


別の修正案をしめします。  
[お気楽 Ruby プログラミング入門 二分木](http://www.geocities.jp/m_hiroi/light/abcruby13.html)  
のコードを参考にしています。

[code]

    # coding: utf-8
    
    # See http://www.geocities.jp/m_hiroi/light/abcruby13.html
    
    # Node Class
    class Node
      attr_accessor :value, :left, :right
    
      def initialize(val)
        @value = val   # ノードが保持する値
        @left = nil    # 左側のノード
        @right = nil   # 右側のノード
      end
    end
    
    # ノードの追加
    def insert_tree(num, node = nil)
      if node.nil?
        return Node.new(num)   # ノードを生成する
      elsif num < node.value
        node.left = insert_tree(num, node.left)
      elsif node.value < num
        node.right = insert_tree(num, node.right)
      end
      node
    end
    
    def find_tree(num, node = nil)
      while node
        if node.value == num
          return node
        elsif node.value < num
          node = node.left
        else
          node = node.right
        end
      end
      nil
    end
    
    # node 以下の最小値のノードを探す。
    def search_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
    
    def delete_tree(num, node)
      if node
        if num == node.value
          if node.left.nil?
            return node.right
          elsif node.right.nil?
            return node.left
          else
            min_node = search_min(node.right)
            node.value = min_node.value
            node.right = delete_min(node.right)
          end
        elsif num < node.value
          node.left = delete_tree(num, node.left)
        else
          node.right = delete_tree(num, node.right)
        end
      end
      node
    end
    
    def print_tree(node = nil, depth = 0)
      return if node.nil?
    
      print_tree(node.left, depth + 1)
      printf "#{' ' * 4 * depth}#{node.value}\n"
      print_tree(node.right, depth + 1)
    end
    
    def ask(msg)
      print msg
      gets.chomp.to_i
    end
    
    def main
      tree_root = nil
      loop do
        print_tree(tree_root)
        case ask "実行する操作のタイプを入力してください。\n 1:追加 2：検索  3:削除 4: 表示 9:終了>"
        when 1
          i = ask '追加する数字を入力してください:'
          tree_root = insert_tree(i, tree_root)
        when 2
          i = ask '検索する数字を入力してください:'
          puts find_tree(i, tree_root).nil? ? "みつかりません\n" : "みつかりました\n"
        when 3
          i = ask '削除する数字を入力してください:'
          tree_root = delete_tree(i, tree_root)
        when 4
        # print_tree(tree_root)
        when 9
          break
        end
      end
    end
    
    main
    
[/code]

  * 2015-01-18: 追記  
print_tree を以下のようにすると、もうすこし tree らしい表示になります。  
参考： How to print binary tree diagram?
<https://stackoverflow.com/questions/4965335>

コード：

[code]

    INDENT_1 = '    '
    INDENT_2 = ' |  '
    INDENT_3 = '- '
    def print_tree(node = nil)
      return if node.nil?
    
      def print_tree_sub(node, is_right, indent = '')
        print_tree_sub(node.right, true, "#{indent}#{is_right ? INDENT_1 : INDENT_2}") if node.right
        printf("#{indent}")
        printf(is_right ? ' /' : ' \\')
        printf(INDENT_3)
        printf("#{node.value}\n")
        print_tree_sub(node.left, false, "#{indent}#{is_right ? INDENT_2: INDENT_1}") if node.left
      end
    
      print_tree_sub(node.right, true) if node.right
      printf "#{node.value}\n"
      print_tree_sub(node.left, false) if node.left
    end
    
[/code]

出力例：

[code]

             /- 19
         /- 15
     /- 14
     |   \- 11
    10
     |       /- 4
     |   /- 3
     |   |   \- 2
     \- 1
         \- 0
    
[/code]


CC BY-SA 3.0
2015-01-17T04:05:48.240
4722
2015-01-18T03:28:08.287
2017-05-23T12:38:56.467
-1
2987
4704
answer