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

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

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

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

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

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

Листинг 9.1. Вставка и обход дерева в ширину

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

# Печатается "1 2 3 4 5 6 7 "

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