/*  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    
*/

#include "TRA.h"
#include <stdio.h>

int binpuuhaku(BTREE T, ELEMENT x) {
	BTREE_NODE n;
	int loytyi = 0;
	n = BTREE_ROOT(T);
	while ( !loytyi && (n!=BTREE_NIL) )
		if (BTREE_SAME(T, BTREE_RETRIEVE(T, n), x))
			loytyi = 1;
		else 
			if (BTREE_LESS(T, x, BTREE_RETRIEVE(T, n)))
				n = BTREE_LEFTCHILD(T, n);
			else
				n = BTREE_RIGHTCHILD(T, n);
	return loytyi;
}

void main() {
	BTREE T;
	BTREE_NODE n;
	INT_BTREE_CREATE(T);
	BTREE_ASSIGN_ROOT(T, INT_BTREE_CREATE_NODE(4)); /* 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))) printf("Löytyy\n");
	else printf("Ei löydy\n");
}