/* ========================================================================== */
/*                                                                            */
/*   tree.c                                                                   */
/*   (c) April 7, 2017 K. J. Rock                                             */
/*                                                                            */
/*   Build a binary tree from random data                                     */
/*     show inherent sorting of tree                                          */
/*                                                                            */
/* ========================================================================== */

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

struct data    // create a structure to hold the data necessary to the problem
	{
	int age;        // min 20  max 70
	int salary;     // min $30,000 max $95,000
	int seniority;  // years of service  0 - 45
	};

struct node    // create a node structure for the tree
	{
	struct data *data;   		// data pointer.
	struct node *left, *right; // tree structure pointers
	};

// allocate the space for the data and then fill each field
// this is a newNode() helper function.
struct data * newData(void)
	{
	struct data *myData;

	myData = (struct data *) malloc (sizeof(struct data));
	myData->age = rand() % 50 + 20;
	myData->salary = rand() % 65000 + 50000;
	myData->seniority = rand() % 45;
	return(myData);
	}

struct node * newNode(void)
	{
	struct node *myNode;

   myNode = (struct node *) malloc (sizeof(struct node));  // create new node
	myNode->data = newData();     // add data to our new node
   myNode->left = NULL;
	myNode->right = NULL;
	return(myNode);
	}

void printInorder(struct node *node)
	{
	if (node == NULL)             // the tree is empty
	    return;

		// First recurse on left child
	printInorder(node->left);

		// Then print the data of node
   printf("age %3d \t", node->data->age);
	printf("salary $%5d \t", node->data->salary);
	printf("seniority %3d \t", node->data->seniority);
		// the data lives at the following memory address
	//printf("data is here %p \n", node->data);
	printf("\n");

		// Now recurse on right child
	printInorder(node->right);
	}

// insert myNode into tree
struct node * treeInsert(struct node *root, struct node *myNode)
	{
	if (root == NULL)  				// empty tree
		{
		printf("node\n");          // sanity check
		root = myNode;
		}
	else
		{
		int isLeft = 0;            // direction flag
		struct node *ptr = root;
		struct node *prev = NULL;

		// walk the tree until there is space for a new node
		while (ptr != NULL)
			{
			prev = ptr;
		// change for different sort order
         if (myNode->data->age < ptr->data->age)
         //if (myNode->data->salary < ptr->data->salary)
         //if (myNode->data->seniority < ptr->data->seniority)
				{
				printf("left\n");    // sanity check
				isLeft = 1;         	// set left flag
				ptr = ptr->left;
				}
			else
				{
            printf("right\n");   // sanity check
				isLeft = 0;  			// set right flag
				ptr = ptr->right;
				}
			}
		// fill space at leaf with new node
		if (isLeft)
			prev->left = myNode;    // set new node as left leaf
		else
			prev->right = myNode;   // set new node as right leaf
		}
	return root;
	}

int main(void)
	{
	static struct node *root;
   time_t t;            			// structure to hold computer's current time

   srand((unsigned) time(&t)); 	// randomize by seeding from time
   root = NULL;  						// start with an empty tree

   for (int i=0; i<43; i++)     // fill the tree
		{
      root = treeInsert(root, newNode());
		}

	printInorder(root);           // walk tree, print in order
	}

////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////

void delTree(struct node *root)
	{
	if (root != NULL)
		{
		delTree(root->left);
		delTree(root->right);
		free(root->data);
		free(root);
		}
	}