Binär Baum

[DuffCola]

Hi, ich bins mal wieder.
Ich bin gerade dabei mir einen dynamischen binären baum zu programmieren, aber ihrgendwie habe ich jetzt schon seit 2 strunden einen Denkfehler.
Warum, bleiben "smaller" und "bigger" der variable root immer auf null, trotz dessen, dass ich 10 integer hinzugefügt habe ?

#include <iostream>
using namespace std;

class Node
{
public:
	Node *smaller;
	Node *bigger;
	int value;

	Node(int value);
	~Node(void);
	void PrintAll(void);
};
Node::Node(int value)
{
	this->value = value;
	smaller = 0;
	bigger = 0;
}
Node::~Node(void)
{
	if(smaller != 0)
	{
		delete smaller;
	}
	if(bigger != 0)
	{
		delete bigger;
	}
}
void Node::PrintAll(void)
{
	cout<<"Value: "<<value<<endl;

	if(smaller != 0)
	{
		smaller->PrintAll();

	}
	if(bigger != 0)
	{
		bigger->PrintAll();
	}
}

class ContainerInteger
{
public:
	Node *root;

	ContainerInteger();
	~ContainerInteger();
	bool Add(int value);
	bool Del(int value);
	bool SearchFor();
	void PrintAll();
};
ContainerInteger::ContainerInteger()
{
	root = 0;
}
ContainerInteger::~ContainerInteger()
{
	if(root != 0)
	{
		delete root;
	}
}
bool ContainerInteger::Add(int value)
{
	if(root == 0)
	{
		root = new Node(value);
		return true;
	}
	else
	{
		Node *help_node = root;
		while(help_node != 0)
		{
			if(value < help_node->value)
			{
				help_node = help_node->smaller;
			}
			else
			if(value > help_node->value)
			{
				help_node = help_node->bigger;
			}
			else
			if(value == help_node->value)
			{
				return false;
			}
		}
		help_node = new Node(value);
		return true;
	}
}
void ContainerInteger::PrintAll()
{
	cout<<root->smaller<< endl;
	cout<<root->bigger<< endl;
}

int main(void)
{
	ContainerInteger a;
	a.Add(20);
	a.Add(10);
	a.Add(14);
	a.Add(15);
	a.Add(16);
	a.Add(3);
	_getch();
	return 0;
}

Ich hoffe, das ist jetzt nicht zuviel code, aber ich denke, dass es besser ist wenn ich den ganzen reinschreibe, da man hier ja alles sehen muss um den Fehler zu finden.
Die Klasse ContainerInteger ist noch nicht vollständig(Löschen usw.. fehlt)

 

[ibafluss]

Am besten machst du auch das add() rekursiv, ist um einiges leichter, der Binärbaum ist ein Paradebeispiel für rekursives Programmieren

Das Problem ist, du positionierst dir help_node zwar richtig (am Ende zeigt er ja auf NULL wenn er aus der Schleife kommt), aber dann schreibst du help_node = new .... Hier lässt du help_node dann auf den neu reservierten Speicher zeigen. Du müsstest den Zeiger des Knotens, der auf NULL zeigt, auf den neu reservierten Speicher zeigen lassen.

Lg

 

[Cromon]

Hallo DuffCola

Zeiger solltest du nicht mit 0 initialisieren, dazu gibts nullptr, also:

root = nullptr;

Ausserdem macht deine Add-Methode etwas merkwürdiges, du gehst durch alle Nodes durch bis es nullptr ist, anschliessend setzt du die Variable auf einen neuen Node. Was du machen müsstest:
Im Fall value < helper_node->value:
Prüfen ob helper_node->smaller == nullptr, wenn ja, da einen neuen Node setzen, wenn nein weiter runter in den Baum gehen

Im zweiten Fall (>) prüfst du bigger.

Frage ist: Musst du einen Baum selber implementieren? Das wurde schon so oft implementiert und optimiert, da nimmst du lieber etwas davon (z.B. boost::graph, oder stl_tree.h für R/B-Bäume).

Viele Grüsse
Cromon

 

[DuffCola]

Ja ich arbeite mcih inomment einfach in C++ neu ein.
Kla ich könnte viel bessere DatenTypen aus anderen klassen nehemen, aber ich will ja ungefähr verstehen, wie sowas funktioniert und es wenigstens auf eine einfache weise können.
Warum ist "nullptr" eigentlich besser als eine einfache 0?

 

[sheel]

zB. weil 0 ja auch als Zahl gesehen werden kann und sich dann bei überladenen Funktionen

void funktion(int i)
{
}
void funktion(double *d)
{
}

die Frage stellt, was genommen wird, wenn der Parameter 0 ist.
Hier würde 0 auf die int-Variante gehen und nullptr zum Pointer.

Noch einiges zB. hier zum Nachlesen:
http://stackoverflow.com/questions/1282295/what-exactly-is-nullptr

 

[DuffCola]

Ok.
Jetzt funktioniert es perfekt.
Nun habe ich mich was mit der Lösch-Funktion beschäftigt, aber ich komme inicht drauf, wie man die am performantesten machen könnte, meine Ideen waren alle viel zu Rechenlastig.
Ich hoffe ihr habt eine Idee, wie so eine Lösch-Funktion im theoretischen aussehen könnte, und wie man den Binär Baum noch Performativer gestalten könnte..
Aber auf jeden Fall bis hier vielen Dank für eure Hilfe!
Hier nochmal der aktuelle Code:

class Node
{
public:
	Node *smaller;
	Node *bigger;
	int value;

	Node(int value);
	~Node(void);
	void PrintAll(void);
};
Node::Node(int value)
{
	this->value = value;
	smaller = nullptr;
	bigger = nullptr;
}
Node::~Node(void)
{
	if(smaller != nullptr)
	{
		delete smaller;
	}
	if(bigger != nullptr)
	{
		delete bigger;
	}
}
void Node::PrintAll(void)
{
	cout<<"Value: "<<value<<endl;

	if(smaller != nullptr)
	{
		smaller->PrintAll();

	}
	if(bigger != nullptr)
	{
		bigger->PrintAll();
	}
}

class ContainerInteger
{
public:
	Node *root;

	ContainerInteger();
	~ContainerInteger();
	bool Add(int value);
	bool Del(int value);
	bool SearchFor();
	void PrintAll();
};
ContainerInteger::ContainerInteger()
{
	root = nullptr;
}
ContainerInteger::~ContainerInteger()
{
	if(root != nullptr)
	{
		delete root;
	}
}
bool ContainerInteger::Add(int value)
{
	if(root == nullptr)
	{
		root = new Node(value);
		return true;
	}
	else
	{
		Node *help_node = root;

		while(true)
		{
			if(value < help_node->value)
			{
				if(help_node->smaller == nullptr)
				{
					help_node->smaller = new Node(value);
					return true;
				}
				else
				{
					help_node = help_node->smaller;
				}
			}
			else
			if(value > help_node->value)
			{
				if(help_node->bigger == nullptr)
				{
					help_node->bigger = new Node(value);
				}
				else
				{
					help_node = help_node->bigger;
				}
			}
			else
			if(value == help_node->value)
			{
				return false;
			}
		}
		return false;
	}
}
bool ContainerInteger::Del(int value)
{

}
void ContainerInteger::PrintAll()
{
	if(root == nullptr)
	{
		cout<<"This ContainerInteger is empty!"<< endl;
	}
	else
	{
		root->PrintAll();
	}
}

Und Binary Tree Plan:

Beim unteren sind die verbindungen etwas verutscht....