65 lines
1.9 KiB
Plaintext
65 lines
1.9 KiB
Plaintext
!import "../lib/base.tri" Lib
|
|
!import "../lib/list.tri" !Local
|
|
|
|
main = exampleTwo
|
|
-- Level Order Traversal of a labelled binary tree
|
|
-- Objective: Print each "level" of the tree on a separate line
|
|
--
|
|
-- We model labelled binary trees as nested lists where values act as labels. We
|
|
-- require explicit notation of empty nodes. Empty nodes can be represented
|
|
-- with an empty list, `[]`, which evaluates 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
|
|
|
|
label = \node : head node
|
|
|
|
left = (\node : if (emptyList? node)
|
|
[]
|
|
(if (emptyList? (tail node))
|
|
[]
|
|
(head (tail node))))
|
|
|
|
right = (\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 label queue) (self (filter
|
|
(\node : not? (emptyList? node))
|
|
(append (map left queue) (map right queue))))))
|
|
|
|
levelOrderTraversal_ = \a : processLevel (t a t)
|
|
|
|
toLineString = y (\self levels : if (emptyList? levels)
|
|
""
|
|
(append
|
|
(append (map (\x : append x " ") (head levels)) "")
|
|
(if (emptyList? (tail levels)) "" (append (t (t 10 t) t) (self (tail levels))))))
|
|
|
|
levelOrderToString = \s : toLineString (levelOrderTraversal_ s)
|
|
|
|
flatten = foldl (\acc x : append acc x) ""
|
|
|
|
levelOrderTraversal = \s : append (t 10 t) (flatten (levelOrderToString s))
|
|
|
|
exampleOne = levelOrderTraversal [("1")
|
|
[("2") [("4") t t] t]
|
|
[("3") [("5") t t] [("6") t t]]]
|
|
|
|
exampleTwo = levelOrderTraversal [("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]]]
|