80 lines
2 KiB
Text
80 lines
2 KiB
Text
:- object(tree_traversal).
|
|
|
|
:- public(orders/1).
|
|
orders(Tree) :-
|
|
write('Pre-order: '), pre_order(Tree), nl,
|
|
write('In-order: '), in_order(Tree), nl,
|
|
write('Post-order: '), post_order(Tree), nl,
|
|
write('Level-order: '), level_order(Tree).
|
|
|
|
:- public(orders/0).
|
|
orders :-
|
|
tree(Tree),
|
|
orders(Tree).
|
|
|
|
tree(
|
|
t(1,
|
|
t(2,
|
|
t(4,
|
|
t(7, t, t),
|
|
t
|
|
),
|
|
t(5, t, t)
|
|
),
|
|
t(3,
|
|
t(6,
|
|
t(8, t, t),
|
|
t(9, t, t)
|
|
),
|
|
t
|
|
)
|
|
)
|
|
).
|
|
|
|
pre_order(t).
|
|
pre_order(t(Value, Left, Right)) :-
|
|
write(Value), write(' '),
|
|
pre_order(Left),
|
|
pre_order(Right).
|
|
|
|
in_order(t).
|
|
in_order(t(Value, Left, Right)) :-
|
|
in_order(Left),
|
|
write(Value), write(' '),
|
|
in_order(Right).
|
|
|
|
post_order(t).
|
|
post_order(t(Value, Left, Right)) :-
|
|
post_order(Left),
|
|
post_order(Right),
|
|
write(Value), write(' ').
|
|
|
|
level_order(t).
|
|
level_order(t(Value, Left, Right)) :-
|
|
% write tree root value
|
|
write(Value), write(' '),
|
|
% write rest of the tree
|
|
level_order([Left, Right], Tail-Tail).
|
|
|
|
level_order([], Trees-[]) :-
|
|
( Trees \= [] ->
|
|
% print next level
|
|
level_order(Trees, Tail-Tail)
|
|
; % no more levels
|
|
true
|
|
).
|
|
level_order([Tree| Trees], Rest0) :-
|
|
( Tree = t(Value, Left, Right) ->
|
|
write(Value), write(' '),
|
|
% collect the subtrees to print the next level
|
|
append(Rest0, [Left, Right| Tail]-Tail, Rest1),
|
|
% continue printing the current level
|
|
level_order(Trees, Rest1)
|
|
; % continue printing the current level
|
|
level_order(Trees, Rest0)
|
|
).
|
|
|
|
% use difference-lists for constant time append
|
|
append(List1-Tail1, Tail1-Tail2, List1-Tail2).
|
|
|
|
:- end_object.
|