vip% cat treeprint.c
/* treeprint.c: read chars, store in binary */
/* tree and print using inorder traversal */
/* Written by NR Wagner, 7 Mar 1997 */
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

struct tnode {
   char ch;
   struct tnode *left;
   struct tnode *right;
};
void          addtree(struct tnode *, char );
struct tnode *newnode(char );
void          treeprint(struct tnode *);
struct tnode *talloc(void);

main()
{
   struct tnode *root;
   char c;
   root = NULL;
   while ((c = getchar()) != '\n') {
      if (root == NULL) root = newnode(c);
      else addtree(root, c);
   }
   treeprint(root);
   printf("\n");
   return 0;
}

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

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

/* treeprint: recursive inorder print of tree p */
void treeprint(struct tnode *p)
{
   if (p != NULL) {
      treeprint(p -> left);
      printf("%c", p -> ch);
      treeprint(p -> right);
   }
}

/* talloc: make a tnode */
struct tnode *talloc(void)
{
   return (struct tnode *)
        malloc(sizeof(struct tnode));
}
vip% treeprint
jesocimlpqzw
ceijlmopqswz
vip% treeprint
zyxwvutsrqponmlkjihgfedcba
abcdefghijklmnopqrstuvwxyz
vip% treeprint
abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxyz
vip% treeprint
qpwoeirutyalskdjfhgzmxncbvhdfjdkaslsiw
abcdefghijklmnopqrstuvwxyz
vip% treeprint3 <treeprint3.c  (with EOF for '\n')
        
 !"#%()*,-./0179:;<=>EFLMNORUW\abcdefghiklmnoprstuvwxyz{}
vip% treeprint
the quick brown fox jumps over the lazy dog
 abcdefghijklmnopqrstuvwxyz