/*
 * Sehr einfache Implementierung eines binären Suchbaums
 * mit folgenden Einschränkungen
 * 	- nur int-Schlüssel, keine Daten
 *   	- nur Einfügen und Suchen
 *   	- keinerlei Balancierung
 *   	- alle Algorithmen rekursiv
 *  
 */

#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

class BinaryTree;

class Node {

	friend class BinaryTree;
       	
	private:
		int key;
		Node* left;
		Node* right;
		
		Node(int k) {
			key=k;
			left=right=NULL;
		}
		bool search(int k);
		void insert(int k);
		void print(int level);
};

class BinaryTree {

	public:
		BinaryTree() {
			root = NULL;
		}
		bool search(int key); 
		void insert(int key);
		void print();
	private:
		Node* root;
};



bool Node::search(int k) {
	if (k==key) return true;
	if (k<key && left != NULL) return left->search(k);
	if (k>key && right != NULL) return right->search(k);
	return false;
}

void Node::insert(int k) {
	if (k==key) return;
	if (k<key)
		if (left != NULL) left->insert(k);
		else left = new Node(k);
	if (k>key)
		if (right != NULL) right->insert(k);
		else right = new Node(k);
}

void Node::print(int level) {
	if (right != NULL) right->print(level+1);
	for (int i=0; i < level; i++) cout << "  ";
	cout << key << endl;
	if (left != NULL) left->print(level+1);
}

bool BinaryTree::search(int key) {
	if (root== NULL) return false; 
	return root->search(key);
}

void BinaryTree::insert(int key) {
	if (root==NULL) root = new Node(key);
	else root->insert(key);
}

void BinaryTree::print() {
	cout << "Binaerbaum " << hex << this << dec << " : " << endl;
	if (root == NULL) cout << "(leer)" << endl;
	else root->print(0);
}

int main() {

	// Balancierter Baum
	int eingabe[14] = {50,25,75,12,37,62,87,6,18,31,43,56,81,100};
	BinaryTree bb;
	for (int i=0; i < 14; i++)
		bb.insert(eingabe[i]);
	cout << "Balancierter ";
	bb.print();
	
	// Entarteter Baum
	BinaryTree eb;
	for (int i=0; i < 14; i++)
		eb.insert(i);
	cout << "Entarteter ";
	eb.print();
	
	// Zufällige Einfügereihenfolge
	BinaryTree zb;
	srand(time(NULL));
	for (int i=0; i < 14; i++) 
		zb.insert(rand()%100);
	cout << "Zufälliger ";
	zb.print();
	return 0;
}