I found my "print binary tree" program, it is dated May 1993 using C language.
I simply modify it to solve this quiz.
The presentation format is not quite what we asked.
#----------------------------------------------------------------------------#
public
def to_s( )
return "[empty heap]" if @heap.size <= 1
result = ''
root = 1
if has_right?(root)
print_node(result, ' ', true, right_index(root))
result << " |\n"
end
result << "-o #{@heap[root]}\n"
if has_left?(root)
result << " |\n"
print_node(result, ' ', false, left_index(root))
end
result
end
private
def left_index( index ) ; index * 2 ; end
def right_index( index ) ; index * 2 + 1 ; end
def has_left?( index ) ; left_index(index) < @heap.size ; end
def has_right?( index ) ; right_index(index) < @heap.size ; end
def print_node( result, line, right, index )
if has_right?(index)
print_node(result, line + (right ? ' ' : '| '), true, right_index(index))
result << "#{line}#{right ? ' ' : '|'} |\n"
end
result << "#{line}+-o #{@heap[index]}\n"
if has_left?(index)
result << "#{line}#{right ? '|' : ' '} |\n"
print_node(result, line + (right ? '| ' : ' '), false, left_index(index))
end
end
#----------------------------------------------------------------------------#
Some output:
+-o 22
|
+-o 15
| |
| +-o 17
| |
| +-o 19
|
-o 12
|
| +-o 51
| |
| +-o 23
| | |
| | +-o 26
| |
+-o 20
|
| +-o 40
| |
+-o 29
|
+-o 35
+-o heap
| |
| +-o this
|
+-o data
| |
| | +-o the
| | |
| +-o of
| |
| +-o words
|
-o another
|
| +-o on
| |
| +-o kind
| | |
| | +-o random
| |
+-o are
|
| +-o test
| |
+-o some
|
+-o to