Brauche Hilfe beim Binärbaum

RunSeb

Hallo,

hab mir die ganze Theorie reingezogen und auch einigermaßen verstanden.

Jetzt wollt ich das in mein Programm einbauen. Die Grundstruktur hab ich schon:

struct Knoten
{
	Knoten* l;		// linker Kindknoten
	Knoten* r;		// rechter Kindknoten
	string inhalt;		

};

Der Baum soll kein AVL oder sonstiger Sortierbaum werden. Es wird einfach nur ein unbalancierter Baum der als Knoteninhalte Strings hat.
Die Inhalte der Knoten also die Strings liegen vor also ich weis wie der Baum am Ende auf dem Papier aussehen soll und was im welchen Knoten steht.
Bloß versteh ich das nicht so ganz mit den Pointern wie ich jetzt den Baum "wachsen" lasse, wie ich die Wurzel erstelle und wie das dann im Speicher aussieht, etc.? Kann mir das mal jemand näher bringen, also wie ich jetzt die Wurzel erstelle und dann den Baum durch Einfügen der strings wachsen lasse!?

Vielen Dank für euer Bemühen!

CStoll

Zunächst mußt du dir klar machen, wo und wie die einzelnen Knoten zu einem Baum zusammengebaut werden sollen. Dann erzeugst du für jeden Eintrag einen Knoten, trägst in 'inhalt' den entsprechenden String ein und hängst die einzelnen Knoten über die l- und r-Pointer entsprechend deinen Vorstellungen zusammen.

Du merkst Dir Dein Wurzelelement (root).
Die l und r Elemente sollten initialisiert werden, entweder mit nem Objekt oder
mit NULL.

Knoten* root = new Knoten();
root->inhalt = "root";
root->l = NULL;
root->r = NULL;

Neuen Knoten ganz links einfügen

Knoten* tmp = root;
while(tmp)
{
    tmp = tmp->l;
}

// ganz links angekommen
tmp = new Knoten();
tmp->l = NULL;
tmp->r = NULL;
tmp->inhalt = "ganz links";

RunSeb

Jo, das erklärt schon einiges, danke!

Trotzdem werfen sich mir da gleich neue FRagen auf:
Verstehe ich das richtig das jeder Knoten dann zusätzlich zu seinem Inhalt und den Zeigern noch zusätlich einen Namen hat wie "root" und "tmp"?
Kann ich dem ganzen Baum dann einen Namen geben, weil ich mehrere Bäume erstellen will bzw. am Ende einen ganzen Wald habe und bestimmte Bäume dann wiederfinden muss.
Ob und wie muss ich mich um Speicherverwaltung kümmern?

CStoll

1. Er kann einen "Namen" haben, muß aber nicht unbedingt - die Bezeichnung "tmp" ist z.B. nur eine Hilfsvariable, um sich durch den Baum durchhangeln zu können.

2. Ja, du kannst auch mehrere Bäume haben (und die sogar miteinander verschmelzen etc., wenn du willst).

3. Klar brauchst du Speicherverwaltung - wenn du einen Knoten aus dem Baum löschst, muß er (und eventuell alle Unterknoten) per delete entsorgt werden - und spätestens am Programmende fliegt der komplette Baum auf den Müll.
(da bietet es sich übrigens an, einen Destruktor für die Baumknoten zu schreiben, der das übernimmt)

RunSeb

Das mit dem Einfügen klappt noch nicht!
Ich meine schließlich will ich ja nicht immer nur ganz links oder ganz rechts einfügen sondern auch in der Mitte des Baumes!?

Das wird so ne Art boolscher Termbaum wie z.B.:

aus so ner Art Postfixschreibweise die mir vorliegt: OR AND NOT var1 var2 AND var2 NOT var1

soll genau dieser Baum entstehen:
OR
/ \
AND AND
/ \ / \
NOT var1 var2 NOT
/ /
var2 var1

CStoll

Wie gesagt: - da mußt du schon wissen, wo die einzelnen Teile untergebracht werden sollen. Bei diesen Vorgaben würde ich die Eingabe von hinten abarbeiten und den Syntaxbaum stückweise über einen Stack zusammenstellen

Variable: Balttknoten erzeugen und auf Stack legen
NOT: obersten Knoten nehmen, als linken Sohn einen neuen Knotens einfügen und letzteren auf den Stack legen
AND/OR: oberste zwei Knoten nehmen, als Kinder eines neuen Knotens einfügen und letzteren auf den Stack legen

(am Ende liegt dann hoffentlich genau ein Knoten auf dem Stack, den du als Wurzel nehmen kannst)

*D*Evil

Ehm ist bei einem "Binär"baum nicht normalerweise der Wert 1 oder 0? Ansonsten solltest du als Type nen Template nehmen ...

CStoll

(D)Evil schrieb:

Ehm ist bei einem "Binär"baum nicht normalerweise der Wert 1 oder 0?

Nein, das "binär" in Binärbaum bezieht sich nicht auf die Werte der Knoten, sondern auf die Anzahl der jeweiligen Kind-Elemente.

.filmor

(D)Evil schrieb:

Ehm ist bei einem "Binär"baum nicht normalerweise der Wert 1 oder 0?

Binär heißt hier nur, dass jeder Knoten höchstens zwei Kindknoten haben kann.

(D)Evil schrieb:

Ehm ist bei einem "Binär"baum nicht normalerweise der Wert 1 oder 0?

LOOOOOOOOOOOOOOOOOOOOOOOOOL

*D*Evil

Hmm hab mir auch mal ne kleine Implementierung ausgedacht ... ist aber nicht ausgereift:

template <typename T>
class binary_tree
{
public:
	struct node
	{
		node*	left;
		node*	right;
		node*	parent;
		T		data;
		node(node* parent, T const& data) : left(NULL), right(NULL), parent(NULL), data(data) {}
	public:
		void	erase()
		{
			if (parent != NULL)
			{
				if (parent->left == this)
					parent->left = NULL;
				else
					parent->right = NULL;
			}
			node* tmp_left = left;
			node* tmp_right = right;
			delete this;
			if (tmp_left != NULL)
				tmp_left->erase();
			if (tmp_right != NULL)
				tmp_right->erase();
		}
		bool in(const node* ptr) const
		{
			if (left == NULL && right == NULL) return false;
			if (left == ptr || right == ptr) return true;
			return (left != NULL && left->in(ptr)) || (right != NULL && right->in(ptr));
		}
	};
private:
	node * m_root, *m_curent;
	std::size_t m_size;

public:
	binary_tree() : m_root(NULL), m_size(0), m_curent(NULL) {}
	~binary_tree()
	{
		erase(m_root);
	}

public:
	bool empty() const { return m_size == 0; }
	node* push_back(T const& data, bool left)
	{
		if (empty() == true)
		{
			m_root = new node(NULL, data);
			m_curent = m_root;
		}
		else if (left == true)
		{
			m_curent->left = new node(m_curent, data);
			m_curent = m_curent->left;
		}
		else
		{
			m_curent->right = new node(m_curent, data);
			m_curent = m_curent->right;
		}	
		++m_size;
		return m_curent;
	}

	bool in(const node* node) const	{	return (m_root != node ? m_root->in(node) : true);	}

	void erase(node* begin = NULL)
	{
		if (begin == NULL)
		{
			if (m_root != NULL)
				m_root->erase();
			m_root = NULL;
		}
		else if (in(begin) == true)
			begin->erase();
		else
			throw std::out_of_range("node not in tree");
	}

	void insert(node* begin, T const& data, bool left)
	{
		if (left == true && begin->left != NULL || left == false && begin->right != NULL)
			throw std::invalid_argument("node already set");

		node* tmp = (left == true ? begin->left : begin->right);
		tmp = new node(begin, data);
		++m_size;
	}
};

int main()
{
	binary_tree<bool> tree;
	binary_tree<bool>::node* tmp = tree.push_back(false, true);
	tree.push_back(true, false);
	tree.insert(tmp, false, true);
	//	  false
	//		*
	//false	   true
	//	*		*
}

Badestrand

(D)Evil, hast du eigentlich viel Zeit?

Nein. Eigentlich nicht ... Nur brauch ich evt. nicht so lange für so nen kurzen Codesnippet 4-6min denke ich mal hab ich höchstens daf+r gebraucht.

RunSeb

MMH, ok, der Code ist super. Blos brauche ich da wirklich nur den Aufbau von so einem Baum, also De-/Konstruktor sowie Knoten wieder löschen und/oder kopieren und was du da noch schönes alles eingebaut hast ist überflüssig. Trotzdem danke für die Mühe.
Leider versteh ich da als Hobbyprogrammierer auch nur die Hälfte.

Mich würde bei dem Code:

Förster schrieb:

Du merkst Dir Dein Wurzelelement (root).
Die l und r Elemente sollten initialisiert werden, entweder mit nem Objekt oder
mit NULL.
Knoten* root = new Knoten();
root->inhalt = "root";
root->l = NULL;
root->r = NULL;
Neuen Knoten ganz links einfügen
Knoten* tmp = root;
while(tmp)
{
    tmp = tmp->l;
}

// ganz links angekommen
tmp = new Knoten();
tmp->l = NULL;
tmp->r = NULL;
tmp->inhalt = "ganz links";

interessieren was du mit "Wurzelelement merken" meinst!? Das mit dem tmp verstehe ich auch noch nicht. Könnte mir das mal jemand ausführlich näher bringen. Wie kann ich mir die Stelle merken wo ich grad einen Knoten erstellt habe - ( ist das das tmp? ) - wie kann ich von dieser Stelle aus dann wieder rechts oder links einen Knoten einfügen?

Bei einem Baum musst Du immer Zugriff auf die Wurzel haben.
Also brauchst Du eine Variable die lange genug gültig ist und auf das Wurzelelement verweist (in diesem Beispiel die Variable root).
So kannst Du immer von oben nach unten (egal wohin genau) iterieren und am ende den Baum wieder löschen (Speicher freigeben).

tmp ist ein (temporärer) Zeiger auf ein Element (Knoten).
Du kannst ihn natürlich weiter verwenden oder woanders ablegen.

Bei dem Code ist tmp am Ende das neue Element, welches ganz links eingefügt wurde. Es ist aber nur ein Zeiger. Du kannst genauso einen weiteren Zeiger auf dieses Element verweisen lassen.
Falls Du tmp speicherst, dann kannst Du immer noch das Element ganz links erreichen (durch root).

RunSeb

Ok, schön, da hab ich jetzt verstanden was es mit root und tmp auf sich hat!
Jetzt hab ich aber folgendes Problem:
Mal angenommen ich füge ganz links einen Knoten ein. Wie kann ich dann von dem ganz linken Knoten aus wieder rechts und links einen Knoten einfügen ohne zur Wurzel zurückzukehren. Also irgendwie müsste ich dann an dem Knoten bleiben bzw. mir den Knoten merken und von dort aus weiter... oder hab ich es aufgrund einer Denkblockade immer noch nicht gepeilt.

Knoten* root = new Knoten();
root->inhalt = "root";
root->l = NULL;
root->r = NULL;

Baum sieht so aus (nur Wurzel, keine weiteren Knoten):

*
/   \

Knoten* tmp = root; // tmp zeigt auf root
while(tmp->l) // solange tmp ein l-Element besitzt
{
    tmp = tmp->l;  // gehe nach links
}

Wenn Du jetzt bei tmp->l ein neues Element einfügst, dann ist es so als würdest Du bei root->l einfügen, weil root und tmp auf das gleiche zeigen.

Baum sieht nun so aus:

*
   /   \
  *
/  \

Wenn Du nun an tmp->l immer einen neuen Knoten anhängst, dann wächst der Baum nach links.

RunSeb

OKAY, das ist gebongt! Und wenn ich dann meinen Baum nach rechts aufbauen möchte und links fertig bin, gehe ich wieder von root aus!! Mal sehn ob ich das jetzt hinbekomme!
Ich bin mal wieder schwer von Begriff. Danke für die umfangreiche Erklärung!

*D*Evil

Auch auf die Gefahr hin das jetzt welche mein Urteilungsvermögen niedriger einschätzen:

Leider versteh ich da als Hobbyprogrammierer auch nur die Hälfte.

Ich bin noch zu jung um Programmierer (als Beruf) zu sein ... von daher ist das kein Argument Ich bin jünger als sagen wir mal 80% der als halbwegs "guru"-mäßigen ... ^^