[SOLUTION] [QUIZ] Drawing Trees (#40)

Hi,

I apologise for my solution. I optimised the output for compactness, and
legibility suffers a little. Also my code is hard to read and is heavy on
bit operations because I was playing with the numbers instead of solving the
problem.

The code I added is listed below the sample output, which is below. A
complete Ruby file (including this, the Heap and some tests if you run it
from the command line) is available from:
http://www.dave.burt.id.au/ruby/heap.rb

Cheers,
Dave

SAMPLE OUTPUT:
13-15-22-
| | `-
| `-17-
| `-19
`-20-23-51
| `-26
`-29-40
`-35

another-data- kind-
| | `- test
| `- of- some
| `- to
`- are- heap- on
| `-words
`-random- the
`- this

RUBY CODE:
#
# Use a right-hand-side depth-first traversal of the tree to draw the right
# arms above the left arms, with the root at the left and leaves on the
# right:
#
# 1-3
# `2
#
def to_s( )

# empty heap -> empty string
return "" if empty?

d = depth

# w is the width of a column
w = Array.new(d) do |i|
@heap[2**i, 2**i].inject(0) {|m, o| [m, o.to_s.size].max }
end

# ww is the total width of the string (and of each line in it)
ww = w.inject {|m, o| m + o + 1 } - 1

# done is a flag for the traversal algorithm - it marks indexes in
# @heap that have already been traversed.
done = Array.new(2**d)
done[0] = true

# s is the string that will be returned
s = ""

# The outer loop counts down the last @heap index for each row. last
# takes the index of each leaf node, from right to left.
(2**d - 1).downto(2**(d - 1)) do |last|
# a accumulates a list of @heap indexes for a row
a = [last]
a << (a.last >> 1) until done[a.last >> 1]
a.each {|x| done[x] = true }

# The inner loop iterates through the columns, from the root to the
# leaves.
(d - 1).downto(0) do |col|
# Append a fixed-width string: a node, a line or spaces
s << "%#{w[d - col - 1] + 1}s" %
if a.size > col # a node
@heap[a[col]].to_s + "-"
elsif last >> col - 1 & 1 == 1 # a line
"| "
elsif (last + 1) >> col - 1 & 1 == 1 # an "L" angle
"`-"
end
end

# Replace the trailing "-" after all the leaf nodes with a newline.
s[-1] = "\n"
end
s
end

def empty?( )
size == 0
end

def depth( )
if empty?
0
else
(Math.log(@heap.size - 1) / Math.log(2)).to_i + 1
end
end


.

Relevant Pages
Loading