Created
May 19, 2017 01:42
-
-
Save ityonemo/6f8e3eba41fe5b51a4f58856956c5da4 to your computer and use it in GitHub Desktop.
prints trees, yay
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
## 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