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

  * Weiterführende Informationen: [[http://schuljahr.inf-schule.de/2014-15/algorithmen/suchbaeume]]

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>

===== Musterbeispiel =====

<code cpp>
//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "Baum1Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;

struct CKnoten{
   int data;   // Nutzdaten
   CKnoten *left;
   CKnoten *right;
};

CKnoten *root=0;


//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
	: TForm(Owner)
{
}
//---------------------------------------------------------------------------

void ausgabevonoben(CKnoten *h,int k)
{AnsiString einr="";
 if (h!=0)
 {ausgabevonoben(h->right,k+1);
  for (int i=0;i<k;i++) einr=einr+"     ";
  Form1->Memo1->Lines->Add(einr+IntToStr(h->data));
  ausgabevonoben(h->left,k+1);
 }
}

void __fastcall TForm1::Button2Click(TObject *Sender)
{ausgabevonoben(root,0);
}
//---------------------------------------------------------------------------

void einhaengen(CKnoten *&pos, CKnoten *h)
{ // Der neue Knoten wird an der richtigen Stelle in den Baum eingehängt
  if (pos==0) pos=h;
  else
	if (h->data<=pos->data)  einhaengen(pos->left,h);
	else                     einhaengen(pos->right,h);
}

void __fastcall TForm1::Button1Click(TObject *Sender)
{ // Ein neuer Knoten wird errichtet und mit Daten gefüllt
  CKnoten *h = new CKnoten;
  h->data=StrToInt(Edit1->Text);
  h->left=0; h->right=0;
  einhaengen(root,h);

  Memo1->Clear(); ausgabevonoben(root,0);
  Edit1->Text="";
  Edit1->SetFocus();
}
//---------------------------------------------------------------------------
CKnoten *suche(CKnoten *h, int k)
{bool gefunden = false ;
 while (h!=0 && !gefunden){
	   if(h->data==k) gefunden=true;
	   else if(k<h->data) h=h->left;
			else h=h->right;
			}


 if(gefunden)ShowMessage("Gefunden!");
 else        ShowMessage("Nicht gefunden!");
 return h;
}


void __fastcall TForm1::Button3Click(TObject *Sender)
{CKnoten *p;
 int k=StrToInt(Edit1->Text); // Zahl die in Baumgesucht wird
 p = suche(root,k);
 Memo1->Lines->Add(IntToStr(p->data));
}
//---------------------------------------------------------------------------

</code>

**Suchen rekursiv**

<code cpp>

CKnoten *suche(CKnoten *h,int k){

if(h!=0){
	if(k<h->data)suche(h->left, k);
	if(k>h->data)suche(h->right, k);
	if(k==h->data){ShowMessage("Gefunden!");return h;}
	}
else {ShowMessage("Nicht Gefunden!");return 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  ====

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

=== Aufgabe ===

Schreibe ein Programm mit folgenden Funktionen:

Erstelle eine Struktur für einen Binären Baum, wo das Datenfeld ein AnsiString ist. Der Binäre Baum soll Kundennamen enthalten. Erweitere die Struktur um ein zusätzliches Datenfeld ''geschlecht'' vom Typ ''char''.

Implementiere folgende Funktionen

  * a) Aufbau des Baumes (Eingabe des Namens und des Geschlechts w bzw. m)
  * b) Ausgabe des gesamten Baumes (Button "Ausgabe")
  * c) Geschlechterspezifische Ausgabe des Baumes. Der Benutzer kann sich aussuchen, ob alle Männer oder alle Frauen ausgegeben werden. (Button "Ausgabe nach Geschlecht")