/* tree_tulosta_tasoittain.c SJ */

#include <TRA.h>

void tulosta_tasoittain(TREE T)
{
  TREE_NODE n;
  QUEUE Q;

  /* PQ_ == VOIDPTR_QUEUE_ */

  PQ_CREATE(Q);
  if (TREE_ROOT(T) != TREE_NULL) 
	  PQ_ENQUEUE(Q, TREE_ROOT(T));

  while ( ! QUEUE_EMPTY(Q))  {
	  n = PQ_FRONT(Q);
	  PQ_DEQUEUE(Q);
	  TREE_PRINT_NODE(T, n); putchar(' ');
	  n = TREE_LEFTMOST_CHILD(T, n);
	  while (n != TREE_NULL)  {
		  PQ_ENQUEUE(Q, n);
		  n = TREE_RIGHT_SIBLING(T, n);
	  } /* while */
  } /* while */

  QUEUE_FREE(Q);
} /* tulosta_tasoittain */


int main()
{

  TREE puu;
  TREE_NODE n, m, l;
  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));


  printf("Tasoittain: ");
  tulosta_tasoittain(puu);
  printf("\n");


  TREE_FREE(puu);

  exit(0);
}