From: David Tran <email55555@...>
Date: 2005-07-28T01:33:48+09:00
Subject: Re: [QUIZ] Drawing Trees (#40)

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