/* tree.c: create binary tree */
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include "tree.h"

struct tnode {
   char ch;
   struct tnode *left;
   struct tnode *right;
};
static struct tnode *newnode(char );
static void treeprint2(struct tnode *);
struct tnode *root = NULL;

/* insert: add a node, non-recursive */
void insert(char c) {
   struct tnode *p;
   if (root == NULL) { /* empty tree */
      root = newnode(c);
      return;
   }
   p = root;
   for (;;) {
      if ((p -> ch) == c) return;/*dups */
      else if ((p -> ch) > c) { /* left */
         if ((p -> left) == NULL) {
            p -> left = newnode(c);
            return;
         }
         else p = p -> left;
      }
      else if ((p -> ch) < c) {/* right */
         if ((p -> right) == NULL) {
            p -> right = newnode(c);
            return;
         }
         else p = p -> right;
      }
   }
}

/* newnode: fix up a new node */
static struct tnode *newnode(char c) {
   struct tnode *p = (struct tnode *)
        malloc(sizeof(struct tnode));
   p -> ch = c;
   p -> left = p -> right = NULL;
   return p;
}

/* treeprint: recursive inorder print */
void treeprint(void) {
   treeprint2(root);
}

/* treeprint2: recursive inorder print */
static void treeprint2(struct tnode *p) {
   if (p != NULL) {
      treeprint2(p -> left);
      printf("%c", p -> ch);
      treeprint2(p -> right);
   }
}
-----------------------------------------
/* tree.h: header file for tree.c */
void insert(char );
void treeprint(void);
-----------------------------------------
/* treetest.c: test tree.c */
#include <stdio.h>
#include "tree.h"

int main() {
   char c;
   while ((c = getchar()) != '\n') {
      insert(c);
   }
   treeprint();
   printf("\n");
}
% cc -o tree tree.c treetest.c
% tree
thequickbrownfoxjumpsoverthelazydog
abcdefghijklmnopqrstuvwxyz

• Rewrite the program above so that it will make use of C strings instead of single characters.
• We want to handle the same word list file as before, so in the end we need to treat uppercase letters as if they were lowercase, as was done for Recitation 11.
• As in the previous program, you should read a file of words, insert into the binary search tree, and do an inorder traversal to print the words in sorted order.
• You are supposed to be adapting the program above so that it will handle strings, not writing or finding a new C program to do this.
• First work with the months file to test your program. (This is not "random" order, but certainly not alphabetic.)
• Next work with the full word list file in random order: ranwords_unix. Here you must not print the result of an inorder traversal, but instead you should print it to a file, and print the first 20 and the last 20 entries of this file.

• This function is similar to and simpler than the insert function.
• The function should allow you to look up a word after the binary search tree has been built. lookup should return 0 in case the word is found, and it should return -1 if the word is not found.
• Look up the words foxtail, atrophy, and hypertrophy, showing whether they are in the Unix wordlist of Part A or not.

• Add extra pointers prev and next, each of type struct tnode *, to the definition of the structure tnode. prev points to the immediately preceding node in alphabetic order. For the first node in alphabetic order, the prev field should be null. Similarly, next points to the immediately following node in alphabetic order. For the last node in alphabetic order, the next field should be null.
• In addition to the rootpointer, there should also be a global pointer first pointing to the first node (whose prev field is null), and another global pointer last pointing to the last node (whose next field is null). (See the first diagram below for an illustration with three nodes.)
• Add to the lookup function of Part B, so that in case it finds a word, it will print the five words preceding the word, the word itself, and the five words following the word being looked up. (See the second diagram below for a picture of adding a node, and see the illustrative output below.)
• Test this first with the file months.
• Finally test with the full word list file in random order: ranwords_unix

struct tnode {
   char *w;
   struct tnode *left;
   struct tnode *right;
   struct tnode *prev;
   struct tnode *next;
};

void printfromfirst(void) {
   struct tnode *p = first;
   while (p != NULL) {
      printf("%s\n", p -> w);
      p = p -> next;
   }
}

void printfromlast(void) {
   struct tnode *p = last;
   while (p != NULL) {
      printf("%s\n", p -> w);
      p = p -> prev;
   }
}

% cc -o treetest tree.c treetest.c
% treetest
Enter word to look up ---> Jul
Apr
Aug
Dec
Feb
Jan
Jul <----
Jun
Mar
May
Nov
Oct

% cc -o treetest tree.c treetest.c
% treetest
Enter word to look up ---> foxtail
fox
foxglove
Foxhall
foxhole
foxhound
foxtail <----
foxy
foyer
FPC
fraction
fractionate