/* program puuesimerkki2; */

#include <TRA.h>

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

  VOIDPTR_DEQUE_CREATE(D);
  loytyi = 0;
  if (TREE_ROOT(T) != TREE_NIL)
	  VOIDPTR_DEQUE_ENQUEUE(D, top, TREE_ROOT(T));
  while  (! VOIDPTR_DEQUE_EMPTY(D) &&  ! loytyi)  {
	  n = VOIDPTR_DEQUE_FRONT(D);
	  if (TREE_SAME(T, TREE_RETRIEVE(T, n), x))
		  loytyi = 1;
	  else if (TREE_LEFTMOST_CHILD(T, n) != TREE_NIL) 
		  VOIDPTR_DEQUE_ENQUEUE(D, top, TREE_LEFTMOST_CHILD(T, n));
	  else {
		  while (( ! VOIDPTR_DEQUE_EMPTY(D)) && (TREE_RIGHT_SIBLING(T, VOIDPTR_DEQUE_FRONT(D)) == TREE_NIL))
			  VOIDPTR_DEQUE_DEQUEUE(D, top);
		  if  (! VOIDPTR_DEQUE_EMPTY(D))  {
			  n = VOIDPTR_DEQUE_FRONT(D);
			  VOIDPTR_DEQUE_DEQUEUE(D, top);
			  VOIDPTR_DEQUE_ENQUEUE(D, top, TREE_RIGHT_SIBLING(T, n));
		  }
	  }
  }

  if (loytyi)  {
	  printf("Polku solmuun ");
	  TREE_PRINT_NODE(T, VOIDPTR_DEQUE_FRONT(D));
	  printf(" :");
  }
  while (! VOIDPTR_DEQUE_EMPTY(D)) {
	  printf(" ");
	  TREE_PRINT_NODE(T, VOIDPTR_DEQUE_REAR(D));
	  VOIDPTR_DEQUE_DEQUEUE(D, bottom);
  }
  putchar('\n');
}


int main()
{

  TREE puu;
  TREE_NODE n, m, l, k;
  ELEMENT x;
  int i;

	/*
             1
           //\\
          /|  |\
         / |  | \
        2  3  4  5
       /\  |  |
      6  7 8  9
              |
              10
	*/

  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 = 3 ; i <= 5 ; i++) {
	  l = INT_TREE_CREATE_NODE(i);
	  INT_TREE_ASSIGN_RIGHT_SIBLING(puu, m, l);
	  m = l;
  }

  m = TREE_LEFTMOST_CHILD(puu, TREE_ROOT(puu));
  INT_TREE_ASSIGN_LEFTMOST_CHILD(puu, m, INT_TREE_CREATE_NODE(6));
  INT_TREE_ASSIGN_RIGHT_SIBLING(puu, TREE_LEFTMOST_CHILD(puu, m), INT_TREE_CREATE_NODE(7));

  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(9));

  m = TREE_LEFTMOST_CHILD(puu, m);

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


  for (i = 1 ; i <= 10 ; i++)
	  print_path(puu, INT_ELEMENT(i));

  TREE_FREE(puu);

  exit(0);
}