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

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

void path(TREE T, ELEMENT x) {
	DEQUE D;
	TREE_NODE n;
	int loytyi;

	VOIDPTR_DEQUE_CREATE(D);
	loytyi = 0;

	if (TREE_ROOT(T) != TREE_NIL)
		PD_ENQUEUE(D, top, TREE_ROOT(T));
	while ( !PD_EMPTY(D) && !loytyi ) {
		n = PD_FRONT(D);
		if (TREE_SAME(T, TREE_RETRIEVE(T, n), x)) loytyi = 1;
		else if (TREE_LEFTMOST_CHILD(T, n) != TREE_NIL) 
			PD_ENQUEUE(D, top, TREE_LEFTMOST_CHILD(T, n));
		else {
			while ( !PD_EMPTY(D)  &&
				(TREE_RIGHT_SIBLING(T, PD_FRONT(D))==TREE_NIL ))
			PD_DEQUEUE(D, top);
			if ( !PD_EMPTY(D)) {
				n = PD_FRONT(D);
				PD_DEQUEUE(D, top);
				PD_ENQUEUE(D, top, TREE_RIGHT_SIBLING(T, n));
			}
		}
	}
	while ( !PD_EMPTY(D)) {
		TREE_PRINT_NODE(T, PD_REAR(D));
		putchar(' ');
		PD_DEQUEUE(D, bottom);
	}
	putchar('\n');
}

void main() {
	TREE T;
	TREE_NODE n;
	INT_TREE_CREATE(T);
	TREE_ASSIGN_ROOT(T, IT_CREATE_NODE(4));
	TREE_ASSIGN_LEFTMOST_CHILD(T, TREE_ROOT(T), IT_CREATE_NODE(5));
	n = TREE_LEFTMOST_CHILD(T, TREE_ROOT(T));
	TREE_ASSIGN_RIGHT_SIBLING(T, n, IT_CREATE_NODE(6));
	n = TREE_RIGHT_SIBLING(T, n);
	TREE_ASSIGN_LEFTMOST_CHILD(T, n, IT_CREATE_NODE(7));
	TREE_ASSIGN_RIGHT_SIBLING(T, n, IT_CREATE_NODE(8));

	n = TREE_LEFTMOST_CHILD(T, n);
	/* n osoittaa nyt solmuun 7 */

	path(T, TREE_RETRIEVE(T, n));
}