binary tree - delete node

Hi,

we kann ich für einen binary search tree die methode implementieren um einen knoten aus dem tree zu löschen...kann mir jemand bei dem fall helfen, falls der zu löschende knoten 2 kinder hat?

bool remove(int val)
	{
		class node *n = NULL;
		n = search(root, val);

                // no node in tree not found
		if(n == NULL)
		{
			return false;
		}
		else
		{
			// only 1 node
			if(!n->left && !n->right)
			{
				n->father = NULL;
			}
			// only 1 child node
			else if(n->left && !n->right)
			{
				n->father = n->left;
				n->left->father = n->father->father;
				delete n;
			}
			// only 1 child node
			else if(!n->left && n->right)
			{
				n->father = n->right;
				n->right->father= n->father->father;
				delete n;
			}
			// 2 child nodes
			else
			{
                            // ?
			}

			return true;
		}
	}

SeppJ

bintree schrieb:

kann mir jemand bei dem fall helfen, falls der zu löschende knoten 2 kinder hat?

Ja. Derjenige nennt sich Wikipedia und hat einen langen, detaillierten Artikel darüber geschrieben.

so wie ich es verstanden habe, muss ich im linken teilbaum des zu löschenden eltern knotens das max. finden und dann mit dem austauschen? und dann das blatt löschen?

SeppJ

bintree schrieb:

so wie ich es verstanden habe, muss ich im linken teilbaum des zu löschenden eltern knotens das max. finden und dann mit dem austauschen? und dann das blatt löschen?

Welches Blatt genau?

Nochmal auf deutsch:
Du willst das Element N löschen. Wenn N zwei Kinder hat, gehst du so vor:
Du suchst das vorherige oder das nächste Element in der Baumordnung. Welches, ist egal, es ist sogar besser, wenn du nicht immer das gleiche nimmst. Nennen wir dieses Element R. Du weist N den Wert des Knotens R zu. Dann löscht du R. Konstruktionsbedingt kann R höchstens auf einer Seite (nämlich der N abgewandten) einen Kindbaum haben, so dass du bei dieser Löschung auf jedem Fall beim einfachen Fall bist.

Element N ist der zu löschende knoten

1.) falls das element N einen linken sohn hat:
suche im linken unterbaum nach dem groessten element
vertausche groesstes element mit element N.
lösche ursprünglich groesstes element

2.) falls das element N einen rechten sohn hat:
eigentlich gibt es immer einen linken knoten?