Brauche Hilfe beim Binärbaum

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

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?