Binärbäume

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

Ein Baumknoten kann durch den Datentyp CKnoten dargestellt werden:

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

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

CKnoten *root=0;

//---------------------------------------------------------------------------
 
#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));
}
//---------------------------------------------------------------------------

Suchen rekursiv

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

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();
}

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);
}

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);
 
}

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

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();
}