#include <iostream>
#include "tree2.h"
using namespace std;
#include "queue.h"
template<class T>
void preorder(node2<T>* tree)
{
	if (tree != NULL)
	{
		cout << tree->info << " ";
		preorder(tree->lnext);
		preorder(tree->rnext);
	}
}
template<class T>
void inorder(node2<T>* tree)
{
	if (tree != NULL)
	{
			inorder(tree->lnext);
		cout << tree->info << " ";
		inorder(tree->rnext);
	}
}
template<class T>
void postorder(node2<T>* tree)
{
	if (tree != NULL)
	{
		postorder(tree->lnext);
		postorder(tree->rnext);
		cout << tree->info << " ";
	}
}
template<class T>
void levelorder(node2<T>* tree)
{
	QUEUE<node2<T>*> q;
	if (tree != NULL)
		q.enqueue(tree);
	while (!q.isEmpty())
	{
		tree = q.dequeue();
		cout << tree->info << " ";
		if (tree->lnext != NULL)
			q.enqueue(tree->lnext);
		if (tree->rnext != NULL)
			q.enqueue(tree->rnext);
	}
}
template<class T>
void findPredecessor(node2<T>* tree, T element, node2<T>* & res)
{
static bool found = false;
if((tree != NULL) && (tree->info != element))
{
if(!found)
{
if(tree->lnext != NULL)
if(tree->lnext->info == element)
{
res = tree;
found = true;
}
else
findPredecessor(tree->lnext, element, res);
}
if(!found)
{
if(tree->rnext != NULL)
if(tree->rnext->info == element)
{
res = tree;
found = true;
}
else
findPredecessor(tree->rnext, element, res);
}
}
if(!found)
res = NULL;
}

void main()
{
	node2<int>* tree = NULL;
	int inf = 0;
	cout << "Enter the value for the root (-1 for empty tree): ";
	cin >> inf;
	if (inf != -1)
		tree = new node2<int>(inf);
	else
		tree = NULL;
	if (tree == NULL)
		cout << "The tree is empty." << endl;
	else
	{
		enterSubNodes(tree);

			cout << endl;
		printTheTree(tree);
	}
	cout << "Preorder: ";
	preorder(tree);
	cout << endl;
	cout << "Inorder: ";
	inorder(tree);
	cout << endl;
	cout << "Postorder: ";
	postorder(tree);
	cout << endl;
	cout << "Level order: ";
	levelorder(tree);
	cout << endl;
	node2<int> *nod = NULL;
	if(tree != NULL)
	{
		cout << "Enter the element whose predecessor has to be found: ";
		cin >> inf;
		findPredecessor(tree, inf, nod);
		if(nod == NULL)
		//cout << "The predecessor of the element " << inf << " was not found in the tree, or the element is the root of the tree." << endl;
		cout << "NULL";
		cout << "";
		else
		cout << "The predecessor of the element " << inf << " is the element " << nod->info << " located on address " << nod << endl;
}

	system("PAUSE");
}