Tree traversal: Difference between revisions
Content deleted Content added
Added solution for Action! |
Not a robot (talk | contribs) Add CLU |
||
Line 2,962:
((resolve f) tree pr-node)
(println)))</lang>
=={{header|CLU}}==
<lang clu>bintree = cluster [T: type] is leaf, node,
pre_order, post_order, in_order, level_order
branch = struct[left, right: bintree[T], val: T]
rep = oneof[br: branch, leaf: null]
leaf = proc () returns (cvt)
return(rep$make_leaf(nil))
end leaf
node = proc (val: T, l,r: cvt) returns (cvt)
return(rep$make_br(branch${left:up(l), right:up(r), val:val}))
end node
pre_order = iter (n: cvt) yields (T)
tagcase n
tag br (b: branch):
yield(b.val)
for v: T in pre_order(b.left) do yield(v) end
for v: T in pre_order(b.right) do yield(v) end
tag leaf:
end
end pre_order
in_order = iter (n: cvt) yields (T)
tagcase n
tag br (b: branch):
for v: T in in_order(b.left) do yield(v) end
yield(b.val)
for v: T in in_order(b.right) do yield(v) end
tag leaf:
end
end in_order
post_order = iter (n: cvt) yields (T)
tagcase n
tag br (b: branch):
for v: T in post_order(b.left) do yield(v) end
for v: T in post_order(b.right) do yield(v) end
yield(b.val)
tag leaf:
end
end post_order
level_order = iter (n: cvt) yields (T)
bfs: array[rep] := array[rep]$[n]
while ~array[rep]$empty(bfs) do
cur: rep := array[rep]$reml(bfs)
tagcase cur
tag br (b: branch):
yield(b.val)
array[rep]$addh(bfs,down(b.left))
array[rep]$addh(bfs,down(b.right))
tag leaf:
end
end
end level_order
end bintree
start_up = proc ()
bt = bintree[int]
po: stream := stream$primary_output()
tree: bt := bt$node(1,
bt$node(2,
bt$node(4,
bt$node(7, bt$leaf(), bt$leaf()),
bt$leaf()),
bt$node(5, bt$leaf(), bt$leaf())),
bt$node(3,
bt$node(6,
bt$node(8, bt$leaf(), bt$leaf()),
bt$node(9, bt$leaf(), bt$leaf())),
bt$leaf()))
stream$puts(po, "preorder: ")
for i: int in bt$pre_order(tree) do
stream$puts(po, " " || int$unparse(i))
end
stream$puts(po, "\ninorder: ")
for i: int in bt$in_order(tree) do
stream$puts(po, " " || int$unparse(i))
end
stream$puts(po, "\npostorder: ")
for i: int in bt$post_order(tree) do
stream$puts(po, " " || int$unparse(i))
end
stream$puts(po, "\nlevel-order:")
for i: int in bt$level_order(tree) do
stream$puts(po, " " || int$unparse(i))
end
end start_up</lang>
{{out}}
<pre>preorder: 1 2 4 7 5 3 6 8 9
inorder: 7 4 2 5 1 8 6 9 3
postorder: 7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9</pre>
=={{header|CoffeeScript}}==
|