Книга: Программирование на языке Ruby

9.3.1. Реализация двоичного дерева

9.3.1. Реализация двоичного дерева

Ruby позволяет реализовать двоичное дерево разными способами. Например, хранить значения узлов можно в массиве. Но мы применим более традиционный подход, характерный для кодирования на С, только указатели заменим ссылками на объекты.

Что нужно для описания двоичного дерева? Понятно, что в каждом узле должен быть атрибут для хранения данных. Кроме того, в каждом узле должны быть атрибуты для ссылки на левое и правое поддерево. Еще необходим способ вставить новый узел в дерево и получить хранящуюся в дереве информацию. Для этого нам потребуется два метода.

В первом дереве, которое мы рассмотрим, эти методы будут реализованы неортодоксальным способом. Позже мы расширим класс Tree.

В некотором смысле дерево определяется алгоритмом вставки и способом обхода. В нашем первом примере (листинг 9.1) метод insert будет осуществлять поиск в дереве «в ширину», то есть сверху вниз и слева направо. При этом глубина дерева растет относительно медленно, и оно всегда оказывается сбалансированием. Методу вставки соответствует итератор traverse, который обходит дерево в том же порядке.

class Tree
 attr_accessor :left
 attr_accessor :right
 attr_accessor :data
 def initialize(x=nil)
  @left = nil
  @right = nil
  @data = x
 end
 def insert(x)
  list = []
  if @data == nil
   @data = x
  elsif @left == nil
   @left = Tree.new(x)
  elsif @right == nil
   @right = Tree.new(x)
  else
   list << @left
   list << @right
   loop do
    node = list.shift
    if node.left == nil
     node.insert(x)
     break
    else
     list << node.left
    end
    if node.right == nil
     node.insert(x)
     break
    else
     list << node.right
    end
   end
  end
 end
 def traverse()
  list = []
  yield @data
  list << @left if @left != nil
  list << @right if @right != nil
  loop do
   break if list.empty?
   node = list.shift
   yield node.data
   list << node.left if node.left != nil
   list << node.right if node.right != nil
  end
 end
end
items = [1, 2, 3, 4, 5, 6, 7]
tree = Tree.new
items.each {|x| tree.insert(x)}
tree.traverse {|x| print "#{x} "}
print "n"
# Печатается "1 2 3 4 5 6 7 "

Такое дерево не слишком интересно. Но оно годится в качестве введения и фундамента, на котором можно возводить здание.

Оглавление книги