/* puuesimerkki */

#include <TRA.h>

void preorder_print_haara(TREE T, TREE_NODE n)
{
  TREE_PRINT_NODE(T, n);								/* tms hyödyllistä */
  putchar(' ');
  n = TREE_LEFTMOST_CHILD(T, n);
  while (n != TREE_NIL) {
	  preorder_print_haara(T, n);
	  n = TREE_RIGHT_SIBLING(T, n);
  }
}

void preorder_print(TREE T)
{
  if (TREE_ROOT(T) != TREE_NIL)
	  preorder_print_haara(T, TREE_ROOT(T));
}



/* sama ilman rekursiota, käytetään hyväksi pinoa */
/* tällä kertaa koko puu kerralla */
void preorder_print2(TREE T)
{
  STACK S;
  TREE_NODE n, m;
  VOIDPTR_STACK_CREATE(S);
  n = TREE_ROOT(T);
  if (n != TREE_NIL) 
	  VOIDPTR_STACK_PUSH(S, n);

  while ( ! STACK_EMPTY(S))  {

	  n = VOIDPTR_STACK_TOP(S);
	  VOIDPTR_STACK_POP(S);
	  TREE_PRINT_NODE(T, n);		/* tms hyödyllistä */
	  putchar(' ');

	  m = TREE_RIGHT_SIBLING(T, n);
	  if (m != TREE_NIL) 
		  VOIDPTR_STACK_PUSH(S, m);

	  m = TREE_LEFTMOST_CHILD(T, n);
	  if (m != TREE_NIL) 
		  VOIDPTR_STACK_PUSH(S, m);

  }

  STACK_FREE(S);
} /* preorder_print2 */


int main()
{

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


  preorder_print(puu); putchar('\n');

  preorder_print2(puu); putchar('\n');

  TREE_FREE(puu);

  exit(0);
}