2015年1月17日土曜日

150117

Ruby


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

2分木のデータ追加、サーチ、削除
(ただし、書籍のように最初に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

0 件のコメント:

コメントを投稿