35 lines
1.7 KiB
Plaintext
35 lines
1.7 KiB
Plaintext
-- Level Order Traversal of a labelled binary tree
|
|
-- Objective: Print each "level" of the tree on a separate line
|
|
--
|
|
-- NOTICE: This demo relies on tricu base library functions
|
|
--
|
|
-- We model labelled binary trees as sublists where values act as labels. We
|
|
-- require explicit notation of empty nodes. Empty nodes can be represented
|
|
-- with an empty list, `[]`, which is equivalent to a single node `t`.
|
|
--
|
|
-- Example tree inputs:
|
|
-- [("1") [("2") [("4") t t] t] [("3") [("5") t t] [("6") t t]]]]
|
|
-- Graph:
|
|
-- 1
|
|
-- / \
|
|
-- 2 3
|
|
-- / / \
|
|
-- 4 5 6
|
|
--
|
|
|
|
isLeaf = (\node : lOr (emptyList node) (emptyList (tail node)))
|
|
getLabel = (\node : head node)
|
|
getLeft = (\node : if (emptyList node) [] (if (emptyList (tail node)) [] (head (tail node))))
|
|
getRight = (\node : if (emptyList node) [] (if (emptyList (tail node)) [] (if (emptyList (tail (tail node))) [] (head (tail (tail node))))))
|
|
|
|
processLevel = y (\self queue : if (emptyList queue) [] (pair (map getLabel queue) (self (filter (\node : not (emptyList node)) (lconcat (map getLeft queue) (map getRight queue))))))
|
|
levelOrderTraversal = (\a : processLevel (t a t))
|
|
toLineString = y (\self levels : if (emptyList levels) "" (lconcat (lconcat (map (\x : lconcat x " ") (head levels)) "") (if (emptyList (tail levels)) "" (lconcat (t (t 10 t) t) (self (tail levels))))))
|
|
levelOrderToString = (\s : toLineString (levelOrderTraversal s))
|
|
|
|
flatten = foldl (\acc x : lconcat acc x) ""
|
|
flatLOT = (\s : lconcat (t 10 t) (flatten (levelOrderToString s)))
|
|
|
|
exampleOne = flatLOT [("1") [("2") [("4") t t] t] [("3") [("5") t t] [("6") t t]]]]
|
|
exampleTwo = flatLOT [("1") [("2") [("4") [("8") t t] [("9") t t]] [("6") [("10") t t] [("12") t t]]] [("3") [("5") [("11") t t] t] [("7") t t]]]
|