====== Binärbäume ======

Baumstrukturen werden aus Knoten aufgebaut, die einen Zeiger auf einen linken und rechten Teilbaum enthalten:

{{:inf:inf8bi_201112:datenstrukturen:baeume1.png|Binärbäume}}

Ein Baumknoten kann durch den Datentyp ''CKnoten'' dargestellt werden:

<code cpp>
struct CKnoten {
  int data;       // die Nutzdaten sind in diesem Beispiel nur Zahlen
  CKnoten* left;
  CKnoten* right;
};
</code>

Der Zeiger auf den obersten Knoten des Baums wird oft als root bezeichnet:

<code cpp>
CKnoten *root=0;
</code>

===== Einhängen eines neuen Knotens =====

<code cpp>
void einhaengen(CKnoten *&tiefer, CKnoten *neu)
{
	if (tiefer==0)
	{ tiefer=neu;
	}
	else
	{
		if (neu->data<=tiefer->data)
		{
		einhaengen(tiefer->left,neu);
		}
		else
		{
		einhaengen(tiefer->right,neu);
		}
	}
}

void __fastcall TForm3::Button1Click(TObject *Sender)
{
CKnoten *neu = new CKnoten;
 if (Edit1->Text!="")
 {  neu->data=StrToInt(Edit1->Text);
	neu->left=0;
	neu->right=0;
	Edit1->Text="";
	einhaengen(root,neu);
 }
 Edit1->Focused();
}
</code>

===== Löschen eines Knotens =====
==== Variante 1  ====
Bei dieser Variante wird ein Baum mit geringer Tiefe immer "listenähnlicher". 

<code cpp>
void loeschen(CKnoten *&h)
{
if (h!=0) {
  if (StrToInt(Form1->Edit3->Text) <= h->data) loeschen(h->left);
  else if (StrToInt(Form1->Edit3->Text) > h->data) loeschen(h->right);
  if (StrToInt(Form1->Edit3->Text) == h->data) {
	 if (h->left==0 && h->right==0) {   //Blatt
	 delete(h);
	 h=0;
	 }
	 else if (h->left!=0&&h->right==0) {    //Halbblatt  links
	// CKnoten *h1=h;
	// h=h->left;
	 delete(h);   //delete(h1) if not works
	 h=h->left;   //to delete if not works
	 }
	 else if (h->left==0&&h->right!=0) {    //Halbblatt rechts
	// CKnoten *h1=h;
	// h=h->right;
	 delete(h);   //delete(h1) if not works
	 h=h->right;   //to delete if not works
   //	 return;
	 }
	 else if (h->left!=0&&h->right!=0) {   //2 Kinder
	 CKnoten *h1=h;     //Hilfsknoten
	 CKnoten *h2=h->left;
	 h=h->right;              //größerer Teil rückt nach oben
	 delete(h1);
	 h1=h;
	 while (h1->left!=0) h1=h1->left;  //weiterwandern, immer links bis 0
	 h1->left=h2;
	// return;
	 }
  }
  }

}

void __fastcall TForm1::Button5Click(TObject *Sender)
{
loeschen(root);
}
</code>

=== Variante 2 ===

<code cpp>
void Del(CKnoten* h, CKnoten* i, int nr)
{
		if (h!=0)
		{
			Del(h->left, h, nr);

			if (h->data == nr)
			{
				if (h->right == 0 && h->left == 0)
				{
					if (i->right == h)	i->right = 0;
					else if (i->left == h)	i->left = 0;
				}
				else if (h->right == 0)
				{
					if (i->right == h)	i->right = h->left;
					else if (i->left == h)	i->left = h->left;
				}
				else if (h->left == 0)
				{
					if (i->left == h)	i->left = h->right;
					else if (i->right == h)	i->right = h->right;
				}
				else
				{
					CKnoten* temp1 = h->left;
					CKnoten* temp2 = h->right;

					while (temp1->right != 0)
					{
						temp1 = temp1->right;
					}

					temp1->right = temp2;

					if (i->left == h)	i->left = h->left;
					else if (i->right == h)	i->right = h->left;

                }
			}

			Del(h->right, h, nr);
		}

}

void __fastcall TForm1::btnBlattLoeschenClick(TObject *Sender)
{
	int nr=StrToInt(InputBox("Blatt löschen","Zahl des zu löschenden Blattes?",""));

	if (root->data == nr)
	{
		if (root->left != 0)
		{
			CKnoten* h=root->left;
			CKnoten* i=root->right;

			while (h->right!=0)
			{
				h = h->right;
			}

			h->right = i;
			root = root->left;
		}
		else if (root->right != 0 && root->left == 0)
		{
			root = root->right;
		}
		else if (root->right == 0 && root->left == 0)
		{
        	root = 0;
		}
	}

	Del(root, 0, nr);

}
</code>


==== Variante 3  ====
<code cpp>
 void loeschen(CKnoten *h, CKnoten *h2, int loesch)
{
	if (h!=0) {
		loeschen(h->left, h, loesch); //h2 ist immer 1 über h
		 if (h->data==loesch) {   //wenn gefunden

			   if (h==root) {      //Fall: zu löschendes ist root

				   if (h->left!=0 && h->right==0) {   //Fall: nur 1 Kind, left
					  root=h->left;
					 delete(h);
				   }
				   else if (h->left==0 && h->right!=0) {   //Fall: nur 1 Kind, right
					  root=h->right;
					 delete(h);
				   }

				   else if (h->left==0 && h->right==0) {
						root=0;
						delete(h);
				   }

				  else{        //Fall beide Kinder

				  root=h->right;

				   CKnoten *h3;
					   h3=h->right;
					while (h3->left!=0) {
						h3=h3->left;     //durchgehen bis zum letzten linken ast des rechten Astes
					   }
					h3->left=h->left;
					delete(h);
				   }
			   }

				else if (h->left!=0 && h->right==0)//Fall: 1 Kind - links
				  {
					if (h2->left==h) {  //wenn das kind des zu löschenden links ist
						h2->left=h->left;
					}else h2->right=h->left;

					delete (h);
				  }
				else if (h->left==0 && h->right!=0) {  //Fall: 1 Kind - rechts

				   if (h2->left==h) {  //wenn das kind des zu löschenden links ist
						h2->left=h->right;
					}else h2->right=h->right;

					delete (h);
				}

			   else if (h->left==0 && h->right==0) {   //Fall: letztes Glied      ACHTUNG-->wenn nur ein einziger eintrag-> abfangen
					if (h2->right==h) {   //der right/left zeiger des oberen muss gelöscht werden
						h2->right=0;
					}else h2->left=0;

					delete(h);
			   }

			   else    //Fall: 2 Kinder
			   {
					if (h2->left==h) {        //wenn das zu löschende ein linkes kind ist
					   h2->left=h->right;
					}
					else h2->right=h->right; //rechtes kind

					  CKnoten *h3;
					   h3=h->right;
					while (h3->left!=0) {
						h3=h3->left;     //durchgehen bis zum letzten linken ast des rechten Astes
					   }

					h3->left=h->left;

					delete(h);
			   }
		 }
		loeschen(h->right,h, loesch);
</code>

==== Variante 4  ====

<code cpp>
void loeschen(CKnoten *&h, CKnoten *prev)
{
 if (h!=0)
	{
	 loeschen(h->left, h);
	 loeschen(h->right, h);
	 if (h->data==StrToInt(Form1->Edit3->Text))
		{
		 CKnoten *h1=h->left;
		 CKnoten *h2=h->right;

		 if (h1==0 && h2==0)
			{
			 delete(h);
			 h=0;
			}

		 else if (h1!=0 && h2==0)
			{
			 delete(h);
			 h=h1;
			}

		 else if (h1==0 && h2!=0)
			{
			 delete(h);
			 h=h2;
			}
			
		 else
			{
			 if (prev!=0)
				{
				 if (prev->left==h)
					{
					 h1=h->right;
					 while(h1->left!=0)
						h1=h1->left;
					 h1->left=h->left;
					 prev->left=h->right;
					}
				 else
					{
					 h1=h->left;
					 while(h1->right!=0)
						h1=h1->right;
					 h1->right=h->right;
					 prev->right=h->left;
					}
				}
			}
		}
	}
}

void __fastcall TForm1::Button5Click(TObject *Sender)
{
 if (root->data==Edit3->Text && root->right!=0 && root->left)
	{
	 CKnoten *h=root->left, *h1=root->right;
	 while (h1->left!=0)
		h1=h1->left;
	 h1->left=h;
	 root=root->right;
	}
 loeschen(root, 0);
 Edit3->Clear();
}
</code>