94 lines
2.8 KiB
Text
94 lines
2.8 KiB
Text
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
|