// ---------------------------------------------------------------------------
// Originally I used this to implement a tree of Colors using the X-Windows
// xlib library.  Here it is used as an example for 605.201, Introduction to
// C++ Programming, Summer 1997.
//
// 1/31/94  J. Paul McNamee
// ---------------------------------------------------------------------------

#include <iostream.h>
#include <stdio.h>
#include <string.h>

// ---------------------------------------------------------------------------
// A Binary Tree / Binary Tree Node structure.  The key is the
// string / label associated with each node.  If the left and right
// nodes are NULL, the present node is a leaf node in the tree.


struct btnode { 
    char  *key;               /* the name of the color */
    struct btnode *left;
    struct btnode *right;
};


btnode *btalloc();
btnode *Find(btnode *ancestor_node, char *str);
btnode *Insert(btnode *ancestor_node, char *str);
int Add_Color(char *str);

// ---------------------------------------------------------------------------
// Duplicate a string function (ANSI C version from K&R)

char *strdup(char *s) {
  char *p;
  p = new char [strlen(s) + 1];
  strcpy(p, s);
  return p;
}

// ---------------------------------------------------------------------------
// Create and return a new node in the tree.

btnode *btalloc() {
  btnode *node = new btnode;
  node->left = NULL;
  node->right = NULL;
  return node;
}

// ---------------------------------------------------------------------------
// Find finds the node that has a key of str

btnode *Find(btnode *ancestor_node, char *str) {
  if (ancestor_node == NULL) {  /* Color is not in tree */
    return NULL;
  }
  int cond;
  if ((cond = strcmp(str, ancestor_node->key)) == 0)
    return ancestor_node; /* Found It! */
  else if (cond < 0)
    return Find(ancestor_node->left, str);
  else
    return Find(ancestor_node->right, str);
}

// ---------------------------------------------------------------------------
// Walks the binary tree and prints out nodes

void Inorder_Traversal(btnode *p) {
  if (p != NULL) {
    Inorder_Traversal(p->left);
    cout << "  Key: " << p->key << endl;
    Inorder_Traversal(p->right);
  }
  return;
}

// ---------------------------------------------------------------------------
// Walks the binary tree and prints out nodes
void Preorder_Traversal(btnode *p) {
  if (p != NULL) {
    cout << "  Key: " << p->key << endl;
    Preorder_Traversal(p->left);
    Preorder_Traversal(p->right);
  }
  return;
}

// ---------------------------------------------------------------------------
// Walks the binary tree and prints out nodes
void Postorder_Traversal(btnode *p)
{
  if (p != NULL) {
    Postorder_Traversal(p->left);
    Postorder_Traversal(p->right);
    cout << "  Key: " << p->key << endl;
  }
  return;
}

// ---------------------------------------------------------------------------
// Add a color into the colortree.

btnode *Insert(btnode *ancestor_node, char *str) {
  if (ancestor_node == NULL) {          // Node not in tree yet, so add it!
    ancestor_node = btalloc();
    ancestor_node->key = strdup(str);   // Note pointer assignment!
  } else {
    int cond;
    if ((cond = strcmp(str, ancestor_node->key)) == 0) {
      cerr << "Duplicate color - not inserted in tree. " << str << endl;
    } else {
      if (cond < 0) {
        if (ancestor_node->left == NULL)
          ancestor_node->left = Insert(NULL, str);
        else
          return Insert(ancestor_node->left, str);
      } else {
        if (ancestor_node->right == NULL)
          ancestor_node->right = Insert(NULL, str);
        else
          return Insert(ancestor_node->right, str);
      }
    }
  }
  return ancestor_node;
}

// ---------------------------------------------------------------------------
// Let's test the code!

int main () {

  // First set up root node in tree to be "Green"
  btnode *root = Insert(NULL, "Green");

  // Now make some other insertions
  Insert(root, "Black");
  Insert(root, "Blue");
  Insert(root, "Red");
  Insert(root, "Purple");

  // Check In-Order Traversal
  cout << "Should see: Black, Blue, Green, Purple, Red" << endl;
  Inorder_Traversal(root);
  
  Insert(root, "Yellow");
  Insert(root, "Red");          // Should get a message for duplicate entry
  Insert(root, "Orange");

  // Another In-Order Traversal
  cout << "Should see: Black, Blue, Green, Orange, Purple, Red, Yellow" << endl;
  Inorder_Traversal(root);

  cout << "Now a pre-order traversal" << endl;
  Preorder_Traversal(root);

  btnode *red = Find(root, "Red");
  if (red != NULL) {
    cout << "The color is: " << red->key << endl;
  }

  // Should delete tree to avoid memory leak
  
  return 1;
}

// Output:

// Should see: Black, Blue, Green, Purple, Red
//  Key: Black
//  Key: Blue
//  Key: Green
//  Key: Purple
//  Key: Red
// Duplicate color - not inserted in tree. Red
// Should see: Black, Blue, Green, Orange, Purple, Red, Yellow
//   Key: Black
//   Key: Blue
//   Key: Green
//   Key: Orange
//   Key: Purple
//   Key: Red
//   Key: Yellow
// Now a pre-order traversal
//   Key: Green
//   Key: Black
//   Key: Blue
//   Key: Red
//   Key: Purple
//   Key: Orange
//   Key: Yellow
// The color is: Red