This example consists of two separate C programs:

• search_tree.c:
  • Reads input consisting of individual characters.
  • Creates a binary search tree with each new character a new node of the tree. (If a character is encountered a second time, it is found in the tree and ignored.)
  • Outputs the tree using a lisp-like representation as a stream of characters. A null tree is represented as '0'. Other trees have the form: '(' character leftsubstree rightsubtree ')'

• traverse_tree.c:
  • Reads in a binary tree represented in a lisp-like representation as a stream of characters (see above).
  • Uses an inorder traversal to print the nodes in inorder (that is, alphabetic order).

First the two programs are executed separately. Then the output of the first is piped into the second as input. This example shows how a program (search_tree.c above) can create a binary tree, "flatten" it and output it as a stream of characters. This output can then be piped into a second program which decodes the binary tree, that is, "unflattens" it. Finally an inorder traversal is carried out on this reconstructed binary tree.

Part of the point of this example is to illustrate how much better it would be if one could pipe a whold data structure from one process to another.

/* search_tree.c: read chars, store in binary */
/* tree and output the tree */
#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 );
struct tnode *talloc(void);
void          treeprint(struct tnode *p);

int main(void) {
   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;
}

/* talloc: make a tnode */
struct tnode *talloc(void) {
   return (struct tnode *)
        malloc(sizeof(struct tnode));
}

/* treeprint: print tree in lisp-like form */
void treeprint(struct tnode *p) {
   if (p == NULL) printf("0");
   else {
      printf("( %c ", p -> ch);
      treeprint(p -> left);
      printf(" ");
      treeprint(p -> right);
      printf(" )");
   }
}

/* traverse_tree.c: read in binary tree, inorder traversal
 * grammar:
 *   bintree --->  tree '#'
 *   tree ---> '0' | '(' letter tree tree ')'
 *   letter ---> 'a' | 'b' | 'c' | ...
 */
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
char next;
struct tnode {
   char ch;
   struct tnode *left;
   struct tnode *right;
};

struct tnode *tree(void);
void error(int);
void scan(void);
void inorder_traversal(struct tnode *);

int main(void) {
   struct tnode *root;
   scan();
   root = tree(); /* read in binary tree */
   if (next != '#') error(1);
   inorder_traversal(root); /* print in alpha order using traversal */
   printf("\n");
   return 0;
}

struct tnode *tree(void) {
   struct tnode *p ;
   struct tnode *q;
   struct tnode *r;
   if (next == '0') {
      scan();
      p = NULL;
      return p;
   }
   else {
      p = (struct tnode *) malloc(sizeof(struct tnode));
      if (next == '(')
         scan();
      else error(2);
      if (isalpha(next)) {
         p -> ch = next;
         scan();
      }
      else error(3);
      q = tree();
      r = tree();
      if (next == ')')
         scan();
      else error(4);
      p -> left = q;
      p -> right = r;
      return p;
   }
}

void scan(void) {
   while (isspace(next = getchar()))
      ;
}
void error(int n) {
   printf("\n*** ERROR: %i\n", n);
   exit(1);
}

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

% cc -o search_tree search_tree.c
% cc -o traverse_tree traverse_tree.c
% search_tree
mtwfsjaond
( m ( f ( a 0 ( d 0 0 ) ) ( j 0 0 ) ) ( t ( s ( o ( n 0 0 ) 0 ) 0 ) ( w 0 0 ) ) )#
% traverse_tree
( m ( f ( a 0 ( d 0 0 ) ) ( j 0 0 ) ) ( t ( s ( o ( n 0 0 ) 0 ) 0 ) ( w 0 0 ) ) )#
adfjmnostw
% search_tree | traverse_tree
mtwfsjaond
adfjmnostw

/* treeprint: print tree in lisp-like form */
void treeprint(struct tnode *p) {
   if (p == NULL) printf("0");
   else {
      printf("(%c", p -> ch);
      treeprint(p -> left);
      treeprint(p -> right);
      printf(")");
   }
}

Here are the new results of test runs:

% cc -o search_tree2 search_tree2.c
% cc -o traverse_tree2 traverse_tree2.c
% search_tree2
dt$ *0)xy(8
(d($( 00)(*()((00)0)(00(800))))(t0(x0(y00))))#
% traverse_tree2
(d($( 00)(*()((00)0)(00(800))))(t0(x0(y00))))#
 $()*08dtxy
% search_tree2 | traverse_tree2
dt$ *0)xy(8
 $()*08dtxy