(* tra04.h4.19.p SJ *)

program puutehtavia;

import TRA;

(* tehtävä 19 *)
(*  Kirjoita algoritmi joka etsii alkion annetusta esijärjestetystä
    yleisestä puusta. Algoritmi palauttaa joko löydetyn solmun tai
    TREE_NIL, jollei ko. alkiota löytynyt. Algoritmin periaate
    käsiteltiin luennolla, ja se löytyy myös esimerkkisivulta.
    Aikavaativuus? *)

(* kaksi vaihtoehtoista toteutustapaa *)

function preorder_search(T : TREE; x : ELEMENT) : TREE_NODE;
begin
end;


(* pääohjelma *)

var puu : TREE;
	n, m, l, k : TREE_NODE;
	x : ELEMENT;
	i : integer;

begin

	(*
	    1
      //\\
     /|  |\
    / |  | \
   2  6 10  14_____________
  /\  |  |  |  \  \  \  \  \
  3 5 8 11  15 16 17 18 19 20
         |
        12
	*)

	INT_TREE_CREATE(puu);

	n := INT_TREE_CREATE_NODE(1);
	INT_TREE_ASSIGN_ROOT(puu, n);
	m := INT_TREE_CREATE_NODE(2);
	INT_TREE_ASSIGN_LEFTMOST_CHILD(puu, n, m);
	for i := 1 to 3 do begin
		l := INT_TREE_CREATE_NODE(2+4*i);
		INT_TREE_ASSIGN_RIGHT_SIBLING(puu, m, l);
		m := l;
	end;

	m := TREE_LEFTMOST_CHILD(puu, TREE_ROOT(puu));
	INT_TREE_ASSIGN_LEFTMOST_CHILD(puu, m, INT_TREE_CREATE_NODE(3));
	INT_TREE_ASSIGN_RIGHT_SIBLING(puu, TREE_LEFTMOST_CHILD(puu, m), INT_TREE_CREATE_NODE(5));

	m := TREE_RIGHT_SIBLING(puu, m);
  	INT_TREE_ASSIGN_LEFTMOST_CHILD(puu, m, INT_TREE_CREATE_NODE(8));

	m := TREE_RIGHT_SIBLING(puu, m);
	INT_TREE_ASSIGN_LEFTMOST_CHILD(puu, m, INT_TREE_CREATE_NODE(11));

	m := TREE_LEFTMOST_CHILD(puu, m);

	INT_TREE_ASSIGN_LEFTMOST_CHILD(puu, m, INT_TREE_CREATE_NODE(12));

	(* *)
	m := INT_TREE_CREATE_NODE(15);
	INT_TREE_ASSIGN_LEFTMOST_CHILD(puu, l,  m);
	for i := 16 to 20 do begin
		l := INT_TREE_CREATE_NODE(i);
		INT_TREE_ASSIGN_RIGHT_SIBLING(puu, m, l);
		m := l;
	end;

	for i := 1 to 20 do
		writeln('Haku ', i, ' : ',
				TREE_NIL <> preorder_search(puu, INT_ELEMENT(i)));


	TREE_FREE(puu);
end.