36 lines
1.4 KiB
Text
36 lines
1.4 KiB
Text
component BinaryTreeTraversals (Tree, Element);
|
|
type Tree;
|
|
type Node = Tree;
|
|
Tree (LeftTree = Tree, Element, RightTree = Tree) -> Tree;
|
|
Leaf (Element) -> Node;
|
|
Node (Tree) -> Node;
|
|
Item (Node) -> Element;
|
|
|
|
Preorder (Tree) -> multi (Node);
|
|
Inorder (Tree) -> multi (Node);
|
|
Postorder (Tree) -> multi (Node);
|
|
Level_order(Tree) -> multi (Node);
|
|
begin
|
|
Tree (Lefttree, Item, Righttree) = Tree: [ Lefttree; Item; Righttree ];
|
|
Leaf (anItem) = Tree (null(Tree), anItem, null(Tree) );
|
|
Node (aTree) = aTree;
|
|
Item (aNode) = aNode.Item;
|
|
|
|
Preorder (=null(Tree)) = no(Tree);
|
|
Preorder (T) = ( T, Preorder (T.Lefttree), Preorder (T.Righttree));
|
|
|
|
Inorder (=null(Tree)) = no(Tree);
|
|
Inorder (T) = ( Inorder (T.Lefttree), T, Inorder (T.Righttree));
|
|
|
|
Postorder (=null(Tree)) = no(Tree);
|
|
Postorder (T) = ( Postorder (T.Lefttree), Postorder (T.Righttree), T);
|
|
|
|
Level_order(T) = [ Queue = {T};
|
|
node = Tree:items(Queue);
|
|
[ result(node);
|
|
add(Queue, node.Lefttree) when valid(node.Lefttree);
|
|
add(Queue, node.Righttree) when valid(node.Righttree);
|
|
];
|
|
no(Tree);
|
|
];
|
|
end component BinaryTreeTraversals;
|