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

struct treeNode {
	struct treeNode* leftPtr; // pointer to left subtree
	char data; // node value
	struct treeNode* rightPtr; // pointer to right subtree
};

typedef struct treeNode TreeNode;
typedef TreeNode* TreeNodePtr;

void insertNode(TreeNodePtr* treePtr, char value);
void inOrder(TreeNodePtr treePtr);
void preOrder(TreeNodePtr treePtr);
void postOrder(TreeNodePtr treePtr);

int main()
{
	TreeNodePtr rootPtr[10] = { NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL }; // each tree holds a vocabulary , tree is empty initially
    char item; // varaible to hold charactor
	char sentence[100]; // hold sentence input by user
	int charCounter = 0; // counter for charator in each vocabulary
	char* vocabulary[10]; // each vocabulary contains 10 charactor at most
	int vocabularyCounter = 0; // counter for vocabulary in sentence
	int vocabularyNumber = 0; // number of vocabulary this sentence owns
	char* nextTokenPtr = NULL; // for function token_s , points to remaining sentence to be tokenized

	printf("Please enter a sentence : ");
	fgets(sentence, 100, stdin); // read sentence from user
	sentence[strlen(sentence) - 1] = '\0'; // cover newline charactor

	// tolenize the sentence
	vocabulary[vocabularyCounter] = strtok_s(sentence, " ", &nextTokenPtr); // first token

	while (vocabulary[vocabularyCounter] != NULL)
	{
		printf("%s\n", vocabulary[vocabularyCounter]);
		vocabulary[++vocabularyCounter] = strtok_s(NULL, " ", &nextTokenPtr); // obtain next token
	}
	vocabularyNumber = vocabularyCounter;

	// for each vocabulary , build the tree
	for (vocabularyCounter = 0; vocabularyCounter < vocabularyNumber; vocabularyCounter++)
	{
		charCounter = 0;

		// build the tree , using charactors in vocabulary
		while (vocabulary[vocabularyCounter][charCounter] != '\0')
		{
			item = vocabulary[vocabularyCounter][charCounter++];
			insertNode(&(rootPtr[vocabularyCounter]), item);
		}
	}

	// for each vocabulary , print the tree
	for (vocabularyCounter = 0; vocabularyCounter < vocabularyNumber; vocabularyCounter++)
	{
		// traverse hte tree preOrder
		printf("\n\nThe preOrder traversal is : ");
		preOrder(rootPtr[vocabularyCounter]);

		// traverse hte tree inOrder
		printf("\n\nThe inOrder traversal is : ");
		inOrder(rootPtr[vocabularyCounter]);

		// traverse hte tree preOrder
		printf("\n\nThe postOrder traversal is : ");
		postOrder(rootPtr[vocabularyCounter]);
		printf("\n");
	}
	return 0;
}

// insert node into tree
void insertNode(TreeNodePtr* treePtr, char value)
{
	if (*treePtr == NULL) // if tree is empty or the correct location has been found
	{
		*treePtr = malloc(sizeof(TreeNode));

		// if the memory is allocated , then assign data
		if (*treePtr != NULL)
		{
			(*treePtr)->data = value;
			(*treePtr)->leftPtr = NULL;
			(*treePtr)->rightPtr = NULL;
		}
		else
		{
			printf("%c not inserted. No memory avaliable.\n", value);
		}
	}
	else // tree is not empty
	{
		if (value < (*treePtr)->data) // data to insert is less than data in the current node
		{
			insertNode(&((*treePtr)->leftPtr), value);
		}
		else if (value > (*treePtr)->data) // data to insert is greater than data in the current node
		{
			insertNode(&((*treePtr)->rightPtr), value);
		}
		else // duplicate data value ignored
		{
			printf("dup %c ", value);
		}
	}
} // end function insertNode

// begin inorder traversal of tree
void inOrder(TreeNodePtr treePtr)
{
	// if tree is not empty , then traverse
	if (treePtr != NULL)
	{
		inOrder(treePtr->leftPtr);
		printf("%c  ", treePtr->data);
		inOrder(treePtr->rightPtr);
	}
}

// begin preorder traversal of tree
void preOrder(TreeNodePtr treePtr)
{
	// if tree is not empty , then traverse
	if (treePtr != NULL)
	{
		printf("%c  ", treePtr->data);
		preOrder(treePtr->leftPtr);
		preOrder(treePtr->rightPtr);
	}
}

// begin postorder traveral of tree
void postOrder(TreeNodePtr treePtr)
{
	// if tree is not empty , then traverse
	if (treePtr != NULL)
	{
		postOrder(treePtr->leftPtr);
		postOrder(treePtr->rightPtr);
		printf("%c  ", treePtr->data);
	}
}