37 lines
1.1 KiB
Text
37 lines
1.1 KiB
Text
program tree_traversal;
|
|
tree := [1, [2, [4, [7]], [5]], [3, [6, [8], [9]]]];
|
|
|
|
print("preorder ", preorder(tree));
|
|
print("inorder ", inorder(tree));
|
|
print("postorder ", postorder(tree));
|
|
print("level-order ", levelorder(tree));
|
|
|
|
proc preorder(tree);
|
|
if tree = om then return []; end if;
|
|
[item, left, right] := tree;
|
|
return [item] + preorder(left) + preorder(right);
|
|
end proc;
|
|
|
|
proc inorder(tree);
|
|
if tree = om then return []; end if;
|
|
[item, left, right] := tree;
|
|
return inorder(left) + [item] + inorder(right);
|
|
end proc;
|
|
|
|
proc postorder(tree);
|
|
if tree = om then return []; end if;
|
|
[item, left, right] := tree;
|
|
return postorder(left) + postorder(right) + [item];
|
|
end proc;
|
|
|
|
proc levelorder(tree);
|
|
items := [];
|
|
loop init queue := [tree]; while queue /= [] do
|
|
[item, left, right] fromb queue;
|
|
items with:= item;
|
|
if left /= om then queue with:= left; end if;
|
|
if right /= om then queue with:= right; end if;
|
|
end loop;
|
|
return items;
|
|
end proc;
|
|
end program;
|