(*  Tietorakenteet ja algoritmit 1999				*)
(*    Esimerkki 3-9 : Haku järjestetystä binääripuusta	*)
(*    9.9.1999 MM								*)
(*  - Ratkaisussa jätetään vielä tuhoamatta puu.		*)
(*  - main():issa luodaan seuraavanlainen puu:			*)
(*     4      								*)
(*    /   \    								*)
(*   2     8  								*)
(*  / \   / \     							*)
(* 1   3 6   9    							*)
program Esimerkki3_9;

import TRA;

function binpuuhaku(T:BTREE; x:ELEMENT):boolean; 
var n:BTREE_NODE;
	loytyi:boolean;	
begin
	loytyi := false;
	n := BTREE_ROOT(T);
	while ((not loytyi) and (n<>NIL)) do
		if (BTREE_SAME(T, BTREE_RETRIEVE(T, n), x)) then
			loytyi := true
		else 
			if (BTREE_LESS(T, x, BTREE_RETRIEVE(T, n))) then
				n := BTREE_LEFTCHILD(T, n)
			else
				n := BTREE_RIGHTCHILD(T, n);
	binpuuhaku:=loytyi;
end;

var T:BTREE;
    apu,n:BTREE_NODE;
begin	
	INT_BTREE_CREATE(T);
	apu:=INT_BTREE_CREATE_NODE(4);
	BTREE_ASSIGN_ROOT(T,apu); (* Juuri *)
	n := BTREE_ROOT(T);
	BTREE_ASSIGN_CHILD(T, n, left,  INT_BTREE_CREATE_NODE(2));
	BTREE_ASSIGN_CHILD(T, n, right, INT_BTREE_CREATE_NODE(8));

	n := BTREE_LEFTCHILD(T, BTREE_ROOT(T));
	BTREE_ASSIGN_CHILD(T, n, left, INT_BTREE_CREATE_NODE(1));
	BTREE_ASSIGN_CHILD(T, n, right, INT_BTREE_CREATE_NODE(3));

	n := BTREE_RIGHTCHILD(T, BTREE_ROOT(T));
	BTREE_ASSIGN_CHILD(T, n, left, INT_BTREE_CREATE_NODE(6));
	BTREE_ASSIGN_CHILD(T, n, right, INT_BTREE_CREATE_NODE(9));

	n := INT_BTREE_CREATE_NODE(9);
	(* n osoittaa nyt "irtonaiseen" solmuun jonka nimiö on 9 *)

	if (binpuuhaku(T, TREE_RETRIEVE(T, n))) then writeln('Löytyy')
	else writeln('Ei löydy');
end.