items.each {|x| tree.insert(x)}
tree.inorder {|x| print x, ' '}
print '
'
tree.preorder {|x| print x, ' '}
print '
'
tree.postorder {|x| print x, ' '}
print '
'
# Печатается:
# 5 10 14 20 28 30 41 50 66 70 75 80 88 90 96
# 50 20 10 5 14 30 28 41 80 70 66 75 90 88 96
# 5 14 10 28 41 30 20 66 75 70 88 96 90 80 50
9.3.3. Использование двоичного дерева как справочной таблицы
Пусть дерево уже отсортировано. Тогда оно может служить прекрасной справочной таблицей; например, для поиска в сбалансированном дереве, содержащем миллион узлов, понадобится не более 20 сравнений (глубина дерева равна логарифму числа узлов по основанию 2). Чтобы поиск был осмысленным, предположим, что в каждом узле хранится не какое-то одно значение, а ключ и ассоциированные с ним данные.
Почти всегда лучше использовать в качестве справочной таблицы хэш или даже таблицу во внешней базе данных. Но все равно приведем код:
class Tree
# Предполагается, что определения взяты из предыдущего примера...
def search(x)
if self.data == x
return self
elsif x < self.data
return left ? left.search(x) : nil
else
return right ? right.search(x) : nil
end
end
end
keys = [50, 20, 80, 10, 30, 70, 90, 5, 14,
28, 41, 66, 75, 88, 96]
tree = Tree.new
keys.each {|x| tree.insert(x)}
s1 = tree.search(75) # Возвращает ссылку на узел, содержащий 75...
s2 = tree.search(100) # Возвращает nil (не найдено).
9.3.4. Преобразование дерева в строку или массив
С помощью тех же приемов, которые применяются для обхода дерева, мы можем преобразовать его в строку или в массив. Ниже мы выполняем обход во внутреннем порядке, хотя подошел бы и любой другой способ:
class Tree
# Предполагается, что определения взяты из предыдущего примера...
def to_s
'[' +
if left then left.to_s + ',' else '' end +
data.inspect +
if right then ',' + right.to_s else '' end + ']'
end
def to_a
temp = []
temp += left.to_a if left
temp << data
temp += right.to_a if right
temp
end
end
items = %w[bongo grimace monoid jewel plover nexus synergy]
tree = Tree.new
items.each {|x| tree.insert x}
str = tree.to_a * ','
# str is now 'bongo,grimace,jewel,monoid,nexus,plover,synergy'
arr = tree.to_a
# arr равно:
# ['bongo',['grimace',[['jewel'],'monoid',[['nexus'],'plover',
# ['synergy']]]]]
Отметим, что глубина вложенности получающегося массива равна глубине дерева с корнем в том узле, с которого мы начали обход. Чтобы получить плоский массив, можете воспользоваться методом flatten.
9.4. Графы
