Шрифт:
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 "
Такое дерево не слишком интересно. Но оно годится в качестве введения и фундамента, на котором можно возводить здание.
9.3.2. Сортировка с помощью двоичного дерева
Двоичное дерево позволяет эффективно реализовать сортировку произвольных данных. (Правда, если данные уже отсортированы, оно вырождается в обычный связанный список.) Причина ясна: при каждом сравнении мы исключаем половину мест, в которые можно поместить новый узел.
Хотя в настоящее время такой способ сортировки применяется редко, знать о нем не повредит. Код в листинге 9.2 основан на предыдущем примере.
Листинг 9.2. Сортировка с помощью двоичного дерева
class Tree
# Предполагается, что определения взяты из предыдущего примера...
def insert(x)
if @data == nil
@data = x
elsif x <= @data
if @left == nil
@left = Tree.new x
else
@left.insert x
end
else
if @right == nil
@right = Tree.new x
else
@right.insert x
end
end
end
def inorder
@left.inorder {|y| yield y} if @left != nil
yield @data
@right.inorder {|y| yield y} if bright != nil
end
def preorder
yield @data
@left.preorder {|y| yield y} if @left != nil
@right.preorder {|y| yield y} if @right != nil
end
def postorder
@left.postorder {|y| yield y} if @left != nil
@right.postorder {|y| yield y} if @right != nil
yield @data
end
end
items = [50, 20, 80, 10, 30, 70, 90, 5, 14,