// Binaerer Baum Binary Tree 21.04.2009, 13:14h
// Der Baum funktioniert nun endlich :-)
//
// Die verwendete Queue entspricht exakt der Musterloesung aus Uebung 3,
// wobei allerdings der Rückgabetyp von remove() von void auf Object geaendert wurde
// und die Funktion isEmpty() noch neu hinzugefuegt wurde.

#include <iostream>

using std::cout;
using std::endl;

template<typename Object>

class Queue

{

protected:

	struct Node {

		Object element; // element

		Node* next; // next pointer

	};

	typedef Node* NodePtr; // pointer type to node

private:

	NodePtr front; // pointer to the front of queue

public:

	Queue();

	~Queue();

	void insert(Object const &);

	Object remove();

	bool isEmpty();

	void print(); // print queue elements

};

template<typename Object>

Queue<Object>::Queue()

{

	front = NULL;

}

template<typename Object>

Queue<Object>::~Queue()

{

	while (front != NULL)

		remove();

}

template<typename Object>

void Queue<Object>::insert(Object const &item)

{

	NodePtr newNode = new Node();

	newNode->element = item;

	newNode->next = front;

	front = newNode;

}

template<typename Object>

Object Queue<Object>::remove()

{
	Object result = NULL;

	if (front == NULL)

		return result;

	//go to the back, last item

	NodePtr p = front;

	NodePtr pn = NULL;

	while (p->next != NULL) {

		pn = p;

		p = p->next;

	}

	//delete the last item

	if (pn != NULL) {

		result = p->element;

		pn->next = NULL;

		delete p;

	}

	else {

		/* Note that if 'pn' equals to NULL, it means that

		 *  while loop is not executed, in other words, there

		 *  exists just one item in the queue, just "front".

		 */

		result = front->element;

		delete front;

		front = NULL;

	}

	return result;

}

template<typename Object>

bool Queue<Object>::isEmpty() {
	return front == NULL;
}

template<typename Object>

void Queue<Object>::print()

{

	NodePtr p = front;

	while (p != NULL) {

		cout << p->element << " ";

		p = p->next;

	}

	cout << endl;

}

class BinaryTree {
protected:
	struct Node {
		int element;
		Node* nextLeft;
		Node* nextRight;
		Node() {
			element = -1;
			nextLeft = NULL;
			nextRight = NULL;
		}
	};
private:
	Node* root;
public:
	BinaryTree(int value);
	void add(int value);
	void addToTree(Node* actualNode, int value, Node* upperNode, bool left);
	void printAddressOfTree();
	void levelorderAll();
	void levelorder(Node* node);
	void preorderAll();
	void preorder(Node* node);
	void inorderAll();
	void inorder(Node* node);
	void postorderAll();
	void postorder(Node* node);
};

BinaryTree::BinaryTree(int value) {
	root = new Node();
	root->element = value;
}

void BinaryTree::add(int value) {
	bool left = true;
	addToTree(root, value, NULL, left);
}

void BinaryTree::addToTree(Node *actualNode, int value, Node *upperNode,
		bool left) {
	if (actualNode == NULL) {
		actualNode = new Node();
		actualNode->element = value;
		if (upperNode != NULL) {
			if (left) {
				upperNode->nextLeft = actualNode;
			} else if (!left) {
				upperNode->nextRight = actualNode;
			}
		}
	} else if (value < actualNode->element) {
		bool left = true;
		addToTree(actualNode->nextLeft, value, actualNode, left);
	} else if (value > actualNode->element) {
		bool left = false;
		addToTree(actualNode->nextRight, value, actualNode, left);
	}
}

void BinaryTree::printAddressOfTree() {
	cout << " " << root->element << endl;
	Node *x = root->nextLeft;
	Node *y = root->nextRight;
	cout << "/" << " " << "\\" << endl;
	cout << x->element << " " << y->element << endl;
}

void BinaryTree::levelorderAll() {
	levelorder(root);
}

void BinaryTree::levelorder(Node* node) {
	Queue<Node*> q;
	q.insert(root);
	while (!q.isEmpty()) {
		node = q.remove();
		cout << node->element << " ";
		if (node->nextLeft != NULL) {
			q.insert(node->nextLeft);
		}
		if (node->nextRight != NULL) {
			q.insert(node->nextRight);
		}
	}
}

void BinaryTree::preorderAll() {
	preorder(root);
}

void BinaryTree::preorder(Node* node) {
	cout << node->element << " ";
	if (node->nextLeft != NULL) {
		preorder(node->nextLeft);
	}
	if (node->nextRight != NULL) {
		preorder(node->nextRight);
	}
}

void BinaryTree::inorderAll() {
	inorder(root);
}

void BinaryTree::inorder(Node* node) {
	if (node->nextLeft != NULL) {
		inorder(node->nextLeft);
	}
	cout << node->element << " ";
	if (node->nextRight != NULL) {
		inorder(node->nextRight);
	}
}
void BinaryTree::postorderAll() {
	postorder(root);
}

void BinaryTree::postorder(Node* node) {
	if (node->nextLeft != NULL) {
		postorder(node->nextLeft);
	}
	if (node->nextRight != NULL) {
		postorder(node->nextRight);
	}
	cout << node->element << " ";
}

void binaryTreeTest() {
	BinaryTree c(6);
	c.add(3);
	c.add(1);
	c.add(5);
	c.add(8);
	c.add(2);
	c.add(7);
	c.add(4);
	c.add(9);
	c.add(0);
	//
	// Der Baum sieht nun aus:
	//            6
	//      3           8
	//  1       5    7     9
	// 0 2     4
	//
	c.printAddressOfTree();

	// Die Funktion printAddressOfTree() scheint noch nicht richtig zu funktionieren
	// bzw. nur die beiden obersten Ebenen werden ausgegeben. Vermutlich muesste die Funktion rekursiv sein.
	// Ich habe deshalb die Funktion "levelorderAll()" implementiert (siehe unten), welche die Knoten in levelorder ausgibt,
	// was auch als "printen" bezeichnet werden koennte. Als Hilfe fuer die Funktion "levelorderAll()" benutzte ich die folgende Webseite:
	// http://en.wikipedia.org/wiki/Tree_traversal , Abschnitt "Queue-based level order traversal"

	cout << "preorder: ";
	c.preorderAll();
	cout << endl;

	cout << "inorder: ";
	c.inorderAll();
	cout << endl;

	cout << "postorder: ";
	c.postorderAll();
	cout << endl;

	cout << "levelorder: ";
	c.levelorderAll();
	cout << endl;
}

int main() {
	binaryTreeTest();
	return 0;
}