Meins

// 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 nodeprivate:	NodePtr front; // pointer to the front of queuepublic:	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;}