/*
  Student Name:
  Student NETID:
  Email Address:
  Problems Solved:
*/

/*
PROGRAM  : binary.c
PURPOSE  : insert/display(preorder,postorder,inorder) in a binary tree
UNIX COMP: gcc -o binary binary.c
PC COMP  : TURBO C++ (tcc) or Borland
TEST     : binary binary.dat
INTERACT : binary
REDIRECT : binary <binary.dat
HELP     : h(elp; q(uit; r(oot x; i(nsert [l|r]+ x (ex: i llr x); P(reorder; p(ostorder; I(norder; C(ount; f(ind; F(ind_parent x; s(imilar\n"
NOTE     : `x' is a single character
EXERCISES: Ex1..4
*/

#include <stdio.h>
#include <stdlib.h>

typedef char element_type;
typedef struct tree_node *tree_ptr;

struct tree_node {
  element_type element;
  tree_ptr left;
  tree_ptr right;
};

typedef tree_ptr BINARY_TREE;

void title(char *s) {
  printf("\n%s\ndepth pointer   left  right element\n",s);
}

void show_node(BINARY_TREE T, int depth) {
int i;
  printf("%5d %7d %6d %6d ",depth,T,T->left,T->right);
  for (i=1; i<=depth; i++)
    printf("  ");
  printf("%c\n",T->element);
}

void preorder(BINARY_TREE T, int depth) { 
if (T != NULL) {
    show_node(T,depth);
    preorder(T->left,depth+1);
    preorder(T->right,depth+1);
  }
}

void postorder(BINARY_TREE T, int depth) {  
  if (T != NULL) {
    postorder(T->left,depth+1);
    postorder(T->right,depth+1);
    show_node(T,depth);
  }
}

void inorder(BINARY_TREE T, int depth) {  
  if (T != NULL) {
    inorder(T->left,depth+1);
    show_node(T,depth);
    inorder(T->right,depth+1);
  }
}


BINARY_TREE create_node(element_type x) {  
  BINARY_TREE T;
  T = (BINARY_TREE) malloc(sizeof(struct tree_node));
  if (T == NULL) 
    printf("Out of space!\n");
  else {
    T->element = x;
    T->left = NULL;
    T->right = NULL;
  }
  return T;
}
 
BINARY_TREE ptr_check(BINARY_TREE T) {
  if (T == NULL) {
    printf("Pointer is NULL. Carefully insert from the root.\n");
  } 
  return(T);
}


/* Ex1: Return a count of all nodes in the tree. */

int Count(BINARY_TREE T) {
  return 0;
}

/* Ex2: TRUE (1) or FALSE (0): Is element "x" in the tree? */

int find(char x, BINARY_TREE T) {
  return 0;
}

/* Ex3: Return a pointer to the PARENT node of the node which 
        contains element "x". If the element does not exist,
        then return NULL. Cannot use find() above because
        children do not have pointers to their parent.
*/

tree_ptr find_parent(char x, tree_ptr p) {
  return NULL;
}

/* Ex4: TRUE (1) or FALSE (0): Are trees T1 and T2 similar?
        Two binary trees are similar if they are both
        empty or both nonempty and have similar left
        and right subtrees. That is, they have the same
        structure/shape. 
*/

int similar(BINARY_TREE T1, BINARY_TREE T2) {
  return NULL;
}


void cmd_interpreter(FILE *fp) {
char cmd, xtra, dir, lastdir;
BINARY_TREE T = NULL;
BINARY_TREE P;
element_type x;
int l,h;

  printf("> ");
  while (fscanf(fp,"%c",&cmd) != EOF) {
    switch (cmd) {
      case 'q' : exit(0);
      case 'h' : printf("h(elp; q(uit; r(oot x; i(nsert [l|r]+ x (ex: i llr x); P(reorder; p(ostorder; I(norder; C(ount; f(ind x; F(ind_parent x; s(imilar\n");
                 break;
      case 'r' : fscanf(fp," %c",&x);
                 T = create_node(x);
                 break;
      case 'C' : printf("Count of the tree: %d\n",Count(T));
                 break;
      case 'f' : fscanf(fp," %c",&x);
                 if (find(x,T))
                   printf("Found %c in tree\n",x);
                 else
                   printf("Did not find %c in tree\n",x);
                 break;
      case 'F' : fscanf(fp," %c",&x);
                 P = find_parent(x,T);
                 if (P)
                   printf("Found parent of %c in tree: %c\n",x,P->element);
                 else
                   printf("Did not find parent of %c in tree\n",x);
                 break;
      case 's' : if (similar(T,T))
                   printf("Trees are similar\n");
                 else
                   printf("Trees are not similar\n");
                 break;
       case 'i' : if (T == NULL) 
                   printf("Must do r(oot first\n");
                 else {
                   P = T;
                   fscanf(fp," %c%c",&lastdir,&dir);
                   while ((dir == 'l') || (dir == 'r')) {
                     if (lastdir == 'l')
                       P = ptr_check(P->left);
                     else 
                       P = ptr_check(P->right);
                     lastdir = dir;
                     fscanf(fp,"%c",&dir);
                   } 
                   fscanf(fp,"%c",&x);
                   if (lastdir == 'l')
                     P->left = create_node(x);
                   else
                     P->right = create_node(x);
                 }
                 break;
      case 'P' : title("Preorder: print first, then visit left and right");
                 preorder(T,0);
                 break;
      case 'p' : title("postorder: visit left and right, then print");
                 postorder(T,0);
                 break;
      case 'I' : title("Inorder: visit left, print, then visit right");
                 inorder(T,0);
                 break;
     }
   fscanf(fp,"%c",&xtra);
   printf("> ");
   }
}


int main(int argc, char *argv[]) {
FILE *fp;
  if (argc == 1)
    fp = stdin;
  else {
    fp = fopen(argv[1],"r");
    if (fp == NULL) {
      printf("No File: %s\n",argv[1]);
      return 1;
    }
  }
  cmd_interpreter(fp);
  return 0;
}