Brauche Hilfe beim Binärbaum

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 ... ^^

RunSeb

also wenn du so gut bist wäre es supi wenn du mir deinen Code von oben mal bisschen mit aussagekräftigen Kommentaren füllst!

außerdem bringt er eine Fehlermeldung in Zeile 39: size_t ist kein Element von std

*D*Evil

Was hast du für einen Compiler? std::size_t ist auf jeden Fall korrekt

template <typename T> // Wir wollen das nicht für einen Datentyp spezifizieren 
class binary_tree
{
public:
	struct node
	{
		node*	left;
		node*	right;
		node*	parent; // intern benötigt(bzw. zu vereinfachung)
		T		data;
		node(node* parent, T const& data) : left(NULL), right(NULL), parent(NULL), data(data) {}
	public:
		void	erase()
		{
			if (parent != NULL) // wenn es nicht die Wurzel ist
			{
				// Wir müssen dem Übergeordneten Knoten mitteilen, dass wir gleich nicht mehr existieren!
				if (parent->left == this) // Bin ich der linke oder der rechte Ast?!
					parent->left = NULL;
				else
					parent->right = NULL;
			}
			node* tmp_left = left;
			node* tmp_right = right;
			delete this; // uns selbst löschen

			// Wenn man einen Ast abschneidet gehen auch seine Blätter und "Unter"-Äste verloren ...
			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; // Wenn keine Untergeordneten Äste da sind, können sie auch nicht das node sein ...
			if (left == ptr || right == ptr) return true; // wenn eines der beiden es ist, dann das zurückgeben
			return (left != NULL && left->in(ptr)) || (right != NULL && right->in(ptr)); // sonnst kinder suchen lassen ...
		}
	};
private:
	node * m_root, *m_curent; // curent ist nur, damit wir wissen wo push_back weiter machen soll ...
	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) // wenn noch nichts drin ist, haben wir eine Wurzel!
		{
			m_root = new node(NULL, data);
			m_curent = m_root;
		}
		else if (left == true) // Linker oder rechtes Blatt?
		{
			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;
	}

	// Ist die Wurzel es selbst? Sonnst die Kinder weiter machen lassen(siehe oben!)
	bool in(const node* node) const	{	return (m_root != node ? m_root->in(node) : true);	}

	void erase(node* begin = NULL)
	{
		if (begin == NULL) // wenn begin == NULL ist, den ganzen Baum weg.
		{
			if (m_root != NULL)
				m_root->erase();
			m_root = NULL;
		}
		else if (in(begin) == true) // ist der Knoten überhaupt teil unseres Baumes? Wenn ja, dann löschen!
			begin->erase();
		else
			throw std::out_of_range("node not in tree"); // Sonnst Warnung rauswerfen
	}

	void insert(node* begin, T const& data, bool left)
	{
		if (left == true && begin->left != NULL || left == false && begin->right != NULL) 
			// wenn der Knoten schon ein solches Element hat, gibt es ne ausnahme ;)
			throw std::invalid_argument("node already set");

		node* tmp = (left == true ? begin->left : begin->right); // linker - rechter Ast?
		tmp = new node(begin, data); // neuen Knoten anlegen
		++m_size;
		// Hier kann man, wenn man will, m_curent auf den neu eingefügten Knoten setzen. (evtl. Parameter?)
	}
};

... ist eigentlich relativ selbsterklärend ... hab jetzt überall mal nen bissel was dran geschrieben ... wenn du noch Fragen hast, dann sag bitte die genaue Stelle im Code ...

RunSeb

Vielen Dank!!!

Wie gesagt, mein Compiler meckert auf Zeile 42, dass size_t kein Element von std ist! Was soll ich da für einen Typ nutzen?

Bashar

RunSeb schrieb:

Wie gesagt, mein Compiler meckert auf Zeile 42, dass size_t kein Element von std ist! Was soll ich da für einen Typ nutzen?

#include <cstddef>
oder einer der vielen anderen Header, die size_t definieren.

Mal so in den Raum geworfen: Macht es überhaupt Sinn, einen nicht balanzierten Baum zu verwenden? Meiner Meinung nach verkommen die sowieso zu einer einfachen verketteten Liste - und dann kann man auch direkt eine solche verwenden.

CStoll

Nicht jeder Baum wird als Suchbaum verwendet (bei Suchbäumen sind die balancierten Varianten tatsächlich vorteilhaft) Und nach dem, was ich bisher mitbekommen habe, läuft runSeb's Ansatz eher auf einen Syntaxbaum hinaus.

RunSeb

CStoll schrieb:

Nicht jeder Baum wird als Suchbaum verwendet (bei Suchbäumen sind die balancierten Varianten tatsächlich vorteilhaft) Und nach dem, was ich bisher mitbekommen habe, läuft runSeb's Ansatz eher auf einen Syntaxbaum hinaus.

richtig

Bashar schrieb:

#include <cstddef>
oder einer der vielen anderen Header, die size_t definieren.

Auf die Idee bin ich selbst schon gekommen, aber er bringt mir den selben Fehler, hängt das vielleicht mit dem Template Klasse binary_tree zusammen?

camper

(D)Evil schrieb:

void	erase()
		{
			if (parent != NULL) // wenn es nicht die Wurzel ist
			{
				// Wir müssen dem Übergeordneten Knoten mitteilen, dass wir gleich nicht mehr existieren!
				if (parent->left == this) // Bin ich der linke oder der rechte Ast?!
					parent->left = NULL;
				else
					parent->right = NULL;
			}
			node* tmp_left = left;
			node* tmp_right = right;
			delete this; // uns selbst löschen

			// Wenn man einen Ast abschneidet gehen auch seine Blätter und "Unter"-Äste verloren ...
			if (tmp_left != NULL) 
				tmp_left->erase();
			if (tmp_right != NULL)
				tmp_right->erase();
		}

Grundsätzlich ist es fast immer am besten, in umgekehrter Reihenfolge der Erzeugung zu zerstören: erst die Blätter, dann den Knoten selbst. Dann schleichen sich ganz automatisch nicht solche Fehler wie hier ein (in tmp_left->erase() wird versucht, auf den Vaterknoten zuzugreifen, der wurde aber schon gelöscht). Sinnvoll ist hier sowieso, das Ganze im Destruktor durchzuführen.

*D*Evil

Ehm wird doch im Destruktor aufgerufen(meine ich ... hab den Code nichtmehr da ...)

CStoll

Aber im Destuktor hat ein "delete this" nichts zu suchen (und selbst außerhalb ist es äußerst suspekt).

RunSeb

(D)Evil schrieb:

Ehm wird doch im Destruktor aufgerufen(meine ich ... hab den Code nichtmehr da ...)

Äähm ich will dich ja nicht nerven aber wenn du Zeit hättest kannst mich mal auf ICQ anschreiben!? Ich hab da noch ein paar Fragen da geht Chat einfach schneller! Nr. steht in meinem Profil!
THX