In (binärem) Baum suchen

Ich wollte zum testen mal einen kleinen binären Baum schreiben, das soll kein Suchbaum sein, bei den die Werte sortiert eingefügt sind, sondern es soll einfach jeder Knoten durchgegangen werden und mit dem Vergleichswert verglichen werden (bzw. hier soll der Knoten mit der richtigen Kennziffer gesucht werden).
Die Art und Weise wie ich den Index berechne mag etwas seltsam erscheinen, aber auf dem Papier klappt es so (bis 11 Knoten bin ichs durchgegangen).

Das Problem ist die find-Methode, mir ist vom Prinzip her klar wie sie arbeiten sollte, nur die Implementierung will nicht so richtig.

Arbeiten soll sie so:
-aktuellen Knoten auf ID prüfen, wenn ja ist die Suche beendet da der Knoten gefunden wurde
-ansonsten soll mit dem linken Knoten als neue Wurzel weitergesucht werden,
wird der Knoten da nicht gefunden
-dann soll mit dem rechten Knoten als neue Wurzel weitergesucht werden
-wurde kein Knoten mit dieser ID gefunden, soll ein 0-zeiger zurückgegeben werden

So sieht das bisher aus:

template< typename T >
struct Node
{
	Node()
		: data( T() ), id( int() ), parent( 0 ), left( 0 ), right( 0 )
	{
	}

	T data;
	int id;
	Node* parent;
	Node* left;
	Node* right;
};

template< typename T >
class BTree
{
public:
	BTree()
		: head( Node< T >() ), nextNode( 0 )
	{
		head.id = 0;
	}

	~BTree()
	{
	}

	static Node< T >* find( Node< T >& head, int nodeId )
	{
		//wie muss ich die suche aufbauen, damit abgebrochen
		//wird wenn der Knoten gefunden wird, andernfalls
		//wie oben geschrieben fortgefahren wird
		if( head.id == nodeId )
			return &head
		else if()
	}

	int calcInsertIndex( int nextNode )
	{
		if( nextNode == 1 )
			return 0;
		static int offset = 2;
		static int times = 0;

		if( times == 2 )
		{
			++offset;
			++times;
		}

		return nextNode - offset;
	}

	void insert( const T& data )
	{
		Node< T >* p = find( head, nextNode );
		if( p == 0 )
		{
			p = createNode( calcInsertIndex( nextNode ) );
		}
		p->data = data;
		++nextNode;
	}

	Node< T >* createNode( int nodeId )
	{
		Node< T >* p = find( head, nodeId );
		if( !p )
			throw "createNode";
		if( !p->left )
		{
			p->left = new Node< T >();
			p->left->id = nextNode;
			return p->left;
		}
		if( !p->right )
		{
			p->right = new Node< T >();
			p->right->id = nextNode;
			return p->right;
		}

		throw "end of createNode";
	}

//private:
	Node< T > head;
	int nextNode;
};

int main()
{
	BTree< int > tree;
	for( int i = 0; i < 10; ++i )
		tree.insert( i );

}

Und ja ich weiß, dass ich derzeit den Speicher nicht lösche, ist mir im mom aber auch egal, dafür hab ich das OS.

Habe zwischenzeitlich das ganze mal so implementiert wie ich es nicht haben wollte:

static bool find( Node< T >& head, int nodeId, Node< T >*& p )
	{
		if( head.id == nodeId )
		{
			p = &head;
			return true;
		}
		else if( head.left )
		{
			if( find( *head.left, nodeId, p ) )
				return true;

			if( head.right )
			{
				if( find( *head.right, nodeId, p ) )
					return true;
			}
		}

		return false;
	}

Aber lieber wäre es mir wenn man keinen Parameter angeben müsste für den gefundenen Knoten, sondern er sollte als rückgabewert geliefert werden.

Ponto

Ich mach das mal nicht statisch.

Node<T> * find(int nodeId) {
  std::queue<Node *> que;
  que.push(&head);
  while (not que.empty()) {
    Node * cur = que.front();
    que.pop();
    if (cur->id == nodeId) return cur;
    if (cur->right) que.push(cur->right);
    if (cur->left ) que.push(cur->left );
  }
  return 0;
}