#include <iostream>

using std::cout;
using std::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 printAdressOfTree();
	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::printAdressOfTree(){
	cout << " " << root->element<< endl;
	Node *x = root->nextLeft;
	Node *y = root->nextRight;
	cout << "/" << " " << "\\" << endl;
	cout << x->element<< " " << y->element << endl;
}

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) {
		preorder(node->nextLeft);
	}
	cout << node->element << " ";
	if (node->nextRight != NULL) {
		preorder(node->nextRight);
	}
}
void BinaryTree::postorderAll() {
	postorder(root);
}

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

void binaryTreeTest() {
	BinaryTree c(6); // 1
	c.add(3); //  2 -> 1
	c.add(1); //  3 -> 1
	c.add(5); //  4 -> 2
	c.add(8); //  5 -> 2
	c.add(2); //  6 -> 3
	c.add(7); //  7 -> 3
	c.add(4); //  8 -> 4
	c.add(9); //  9 -> 4
	c.add(0); // 10 -> 5
//
// So sollte der Baum meiner Meinung nach nun eigentlich aussehen:
//          6
//    3          1
//  5     8   2      7
// 4 9   0
//
	c.printAdressOfTree(); // Es scheint nicht richtig zu funktionieren bzw. die Ausgabe stimmt (vermutlich?) nicht mit der Reihenfolge eines binaeren Baumes ueberein.
	cout << "preorder: "; c.preorderAll(); cout << endl; // Ausgabe stimmt (vermutlich?) nicht mit der preorder-Reihenfolge eines binaeren Baumes ueberein.
	cout << "inorder: "; c.inorderAll(); cout << endl; // Ausgabe stimmt (vermutlich?) nicht mit der inorder-Reihenfolge eines binaeren Baumes ueberein.
	cout << "postorder: "; c.postorderAll(); cout << endl; // Ausgabe stimmt (vermutlich?) nicht mit der postorder-Reihenfolge eines binaeren Baumes ueberein.
}

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