Skip to content

Instantly share code, notes, and snippets.

@ityonemo
Created May 19, 2017 01:42
Show Gist options
  • Save ityonemo/6f8e3eba41fe5b51a4f58856956c5da4 to your computer and use it in GitHub Desktop.
Save ityonemo/6f8e3eba41fe5b51a4f58856956c5da4 to your computer and use it in GitHub Desktop.
prints trees, yay
## binary_tree_print.jl
#binary tree defined as the following:
type Tree{T}
node::T
left::Union{Tree{T}, Void}
right::Union{Tree{T}, Void}
end
function depth{T}(tree::Tree{T})
if tree.left != nothing
(tree.right != nothing) && return max(depth(tree.left), depth(tree.right)) + 1
depth(tree.left) + 1
elseif tree.right != nothing
depth(tree.right) + 1
else
1
end
end
function bfp{T}(f::Function, tree::Tree{T})
#a generic breadth-first-parse, with positional information
Q = Vector{Tuple{Tree{T}, Int, Int}}()
level = 1;
node = 1;
unshift!(Q, (tree, level, node))
while (length(Q) > 0)
(current, level, node) = shift!(Q)
(current.left != nothing) && unshift!(Q, (current.left, level + 1, node * 2 - 1))
(current.right != nothing) && unshift!(Q, (current.right, level + 1, node * 2))
#execute f on dequeued node.
f(current, level, node)
end
end
#do this as a closure.
function tree_printer_factory(total_levels::Int)
#total_levels is used to calculate the necessary width, which is 2^levels + 1
current_level = 1
current_node = 0
function index_of(node)
(node == 0) && return 1
node * ((2^total_levels) ÷ (2^current_level)) + 1
end
function seek_node(node)
print(" "^(index_of(node) - index_of(current_node) - 1))
end
function tree_printer{T}(x::Tree{T}, level, node)
if (level > current_level)
println()
current_level += 1
current_node = 0
end
seek_node(node)
print(x.node)
current_node = node
end
end
function print_tree{T}(tree::Tree{T})
bfp(tree_printer_factory(depth(tree)), tree)
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment