(*  Tietorakenteet ja algoritmit 1999			*)
(*  Esimerkki 3-9 : Polun tulostaminen 			*)
(*  9.9.1999 MM							*)
(*  - Ratkaisussa jätetään vielä tuhoamatta puu.	*)
(*  - main():issa luodaan seuraavanlainen puu:		*)
(*     4      *)
(*   / | \    *)
(*  5  6  8   *)
(*     |      *)
(*     7      *)

program Esim3_9;

import TRA;

procedure path(T:TREE;x:ELEMENT);
var	D:DEQUE;
	n:TREE_NODE;
	loytyi:boolean;
begin
	VOIDPTR_DEQUE_CREATE(D);
	loytyi := false;
	if (TREE_ROOT(T) <> NIL) then
		VOIDPTR_DEQUE_ENQUEUE(D,dtop,TREE_ROOT(T));
	while ((not VOIDPTR_DEQUE_EMPTY(D)) and (not loytyi)) do
		begin
 		 n := VOIDPTR_DEQUE_FRONT(D);
		 if (TREE_SAME(T, TREE_RETRIEVE(T, n), x)) then loytyi:=true
		 else if (TREE_LEFTMOST_CHILD(T, n) <> NIL) then 
		  VOIDPTR_DEQUE_ENQUEUE(D, dtop,TREE_LEFTMOST_CHILD(T,n))
		 else 
			begin
			 while ((not VOIDPTR_DEQUE_EMPTY(D)) and
(TREE_RIGHT_SIBLING(T,(VOIDPTR_DEQUE_FRONT(D)))=NIL)) do
			 VOIDPTR_DEQUE_DEQUEUE(D, dtop);
			 if (not VOIDPTR_DEQUE_EMPTY(D)) then
			  begin
			   n := VOIDPTR_DEQUE_FRONT(D);
			   VOIDPTR_DEQUE_DEQUEUE(D, dtop);
			  VOIDPTR_DEQUE_ENQUEUE(D,dtop,TREE_RIGHT_SIBLING(T, n));
			  end;
			end;
		end;
	while (not VOIDPTR_DEQUE_EMPTY(D)) do
		begin
		 TREE_PRINT_NODE(T, VOIDPTR_DEQUE_REAR(D));
		 writeln(' ');
		 VOIDPTR_DEQUE_DEQUEUE(D, dbottom);
		end;
	writeln;
end;

var	T:TREE;
	apu,n:TREE_NODE;
begin
	INT_TREE_CREATE(T);
	apu:=INT_TREE_CREATE_NODE(4);
	TREE_ASSIGN_ROOT(T, apu);
	TREE_ASSIGN_LEFTMOST_CHILD(T, TREE_ROOT(T), INT_TREE_CREATE_NODE(5));
	n := TREE_LEFTMOST_CHILD(T, TREE_ROOT(T));
	TREE_ASSIGN_RIGHT_SIBLING(T, n, INT_TREE_CREATE_NODE(6));
	n := TREE_RIGHT_SIBLING(T, n);
	TREE_ASSIGN_LEFTMOST_CHILD(T, n, INT_TREE_CREATE_NODE(7));
	TREE_ASSIGN_RIGHT_SIBLING(T, n, INT_TREE_CREATE_NODE(8));
	n:=TREE_LEFTMOST_CHILD(T, n);
	(* n osoittaa nyt solmuun 7 *)
	path(T, TREE_RETRIEVE(T, n));
end.