150117

Ruby


「アルゴリズムとデータ構造」のRuby版。

２分木のデータ追加、サーチ、削除

（ただし、書籍のように最初にtreeを作成しません。）

# -*- coding: cp932 -*-

# Node Class

class Node

  attr_accessor :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)

  # 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 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

# ノードの削除

def delete_tree(val)

  node = @tree_root

  parent_node = nil

  direction = 0

  # while文で削除すべき対象を見つける

  while (node != nil && node.value != val)

    if node.value > val

      parent_node = node

      node = node.left

      direction = -1

    else

      parent_node = node

      node = node.right

      direction = 1

    end

  end

  if node == nil

    return false

 end

  if node.left == nil || node.right == nil

    if node.left == nil

      if direction == -1

        parent_node.left = node.right

      elsif direction == 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

  else

    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

    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

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)

      when 2

        printf("検索する数字を入力してください:")

        i = gets.chomp.to_i

        if find_value(@tree_root, i) != nil

          printf("%dを発見しました\n", i)

        else

          printf("%dは見つかりませんでした\n", i)

        end

      when 3

        printf("削除する数字を入力してください:")

        i = gets.chomp.to_i

        if delete_tree(i)

          printf("%dを削除しました\n", i)

        else

          printf("%dは見つかりませんでした\n", i)

        end

      else

        break

    end

  end

end

main