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