124 lines
3 KiB
Text
124 lines
3 KiB
Text
MODE VALUE = INT;
|
|
PROC value repr = (VALUE value)STRING: whole(value, 0);
|
|
|
|
MODE NODES = STRUCT ( VALUE value, REF NODES left, right);
|
|
MODE NODE = REF NODES;
|
|
|
|
PROC tree = (VALUE value, NODE left, right)NODE:
|
|
HEAP NODES := (value, left, right);
|
|
|
|
PROC preorder = (NODE node, PROC (VALUE)VOID action)VOID:
|
|
IF node ISNT NODE(NIL) THEN
|
|
action(value OF node);
|
|
preorder(left OF node, action);
|
|
preorder(right OF node, action)
|
|
FI;
|
|
|
|
PROC inorder = (NODE node, PROC (VALUE)VOID action)VOID:
|
|
IF node ISNT NODE(NIL) THEN
|
|
inorder(left OF node, action);
|
|
action(value OF node);
|
|
inorder(right OF node, action)
|
|
FI;
|
|
|
|
PROC postorder = (NODE node, PROC (VALUE)VOID action)VOID:
|
|
IF node ISNT NODE(NIL) THEN
|
|
postorder(left OF node, action);
|
|
postorder(right OF node, action);
|
|
action(value OF node)
|
|
FI;
|
|
|
|
PROC destroy tree = (NODE node)VOID:
|
|
postorder(node, (VALUE skip)VOID:
|
|
# free(node) - PR garbage collect hint PR #
|
|
node := (SKIP, NIL, NIL)
|
|
);
|
|
|
|
# helper queue for level order #
|
|
MODE QNODES = STRUCT (REF QNODES next, NODE value);
|
|
MODE QNODE = REF QNODES;
|
|
|
|
|
|
MODE QUEUES = STRUCT (QNODE begin, end);
|
|
MODE QUEUE = REF QUEUES;
|
|
|
|
PROC enqueue = (QUEUE queue, NODE node)VOID:
|
|
(
|
|
HEAP QNODES qnode := (NIL, node);
|
|
IF end OF queue ISNT QNODE(NIL) THEN
|
|
next OF end OF queue
|
|
ELSE
|
|
begin OF queue
|
|
FI := end OF queue := qnode
|
|
);
|
|
|
|
PROC queue empty = (QUEUE queue)BOOL:
|
|
begin OF queue IS QNODE(NIL);
|
|
|
|
PROC dequeue = (QUEUE queue)NODE:
|
|
(
|
|
NODE out := value OF begin OF queue;
|
|
QNODE second := next OF begin OF queue;
|
|
# free(begin OF queue); PR garbage collect hint PR #
|
|
QNODE(begin OF queue) := (NIL, NIL);
|
|
begin OF queue := second;
|
|
IF queue empty(queue) THEN
|
|
end OF queue := begin OF queue
|
|
FI;
|
|
out
|
|
);
|
|
|
|
PROC level order = (NODE node, PROC (VALUE)VOID action)VOID:
|
|
(
|
|
HEAP QUEUES queue := (QNODE(NIL), QNODE(NIL));
|
|
enqueue(queue, node);
|
|
WHILE NOT queue empty(queue)
|
|
DO
|
|
NODE next := dequeue(queue);
|
|
IF next ISNT NODE(NIL) THEN
|
|
action(value OF next);
|
|
enqueue(queue, left OF next);
|
|
enqueue(queue, right OF next)
|
|
FI
|
|
OD
|
|
);
|
|
|
|
PROC print node = (VALUE value)VOID:
|
|
print((" ",value repr(value)));
|
|
|
|
main: (
|
|
NODE node := tree(1,
|
|
tree(2,
|
|
tree(4,
|
|
tree(7, NIL, NIL),
|
|
NIL),
|
|
tree(5, NIL, NIL)),
|
|
tree(3,
|
|
tree(6,
|
|
tree(8, NIL, NIL),
|
|
tree(9, NIL, NIL)),
|
|
NIL));
|
|
|
|
MODE TEST = STRUCT(
|
|
STRING name,
|
|
PROC(NODE,PROC(VALUE)VOID)VOID order
|
|
);
|
|
|
|
PROC test = (TEST test)VOID:(
|
|
STRING pad=" "*(12-UPB name OF test);
|
|
print((name OF test,pad,": "));
|
|
(order OF test)(node, print node);
|
|
print(new line)
|
|
);
|
|
|
|
[]TEST test list = (
|
|
("preorder",preorder),
|
|
("inorder",inorder),
|
|
("postorder",postorder),
|
|
("level order",level order)
|
|
);
|
|
|
|
FOR i TO UPB test list DO test(test list[i]) OD;
|
|
|
|
destroy tree(node)
|
|
)
|