Önszervező bináris keresőfa vágása C++-ban.

Önszervező bináris keresőfa vágása C++-ban.
2013-03-15T13:44:38+01:00
2013-03-20T20:20:07+01:00
2022-11-28T14:10:37+01:00
Skorzeny8814
Sziasztok!

Szeretnék csinálni egy önszervező bináris keresőfát C++ nyelven. Már mindenem megvolt hozzá, de az utolsó lépésnél elakadtam, mert nem tudok vágás metódust írni hozzá. Tudom a szabályát, hogy ha x a vágási pont, akkor két fa jön létre, ahol az egyikben bármely y < x és a másikban bármely z > x. A két fa gyökerének apja pedig az x lesz. De nem tudom ezt lekódolni, hiába próbáltam többféleképpen is. Gondoltam rá, hogy csak átláncolgatom az elemeket, de ebbe annyira belekavarodtam, hogy már abban sem voltam biztos, hogy jól tudom a szabályt. Aztán megpróbáltam úgy, hogy kiszedem az összes elemet és építek belőlük két fát, úgy hogy beszurkálom őket egymás után (az említett feltételekkel) és a gyökereik apjának megjelölöm a vágási pontot. Ekkor jöttem rá, hogy beszúrás metódusom nem tud üres fába (NULL pointer értékbe) beszúrni egy gyökér elemet, ráadásul a konstruktorom nem törli a gyerekeit az adott elemnek, csak magát az elemet. Ekkor még erőlködtem 2-3 órát és most itt vagyok. Semmire sem jutottam vele. Tudnátok segíteni? Megadom a két fájl forráskódját:

Fa.cpp:
#include "Fa.hpp" #include <iostream> #include <cstddef> using namespace std; Fa::Fa(){ this->kulcs = -1; this->bal = NULL; this->jobb = NULL; this->apa = NULL; } Fa::Fa(int kulcs, Fa* bal, Fa* jobb, Fa* apa){ this->kulcs = kulcs; this->bal = bal; this->jobb = jobb; this->apa = apa; } Fa::~Fa(){} Fa::Fa(Fa& other){ this->kulcs = other.kulcs; this->bal = other.bal; this->jobb = other.jobb; this->apa = other.apa; } Fa* Fa::keres(int kulcs){ if (this->kulcs == kulcs){ return this; } else if (this->kulcs > kulcs){ return this->bal->keres(kulcs); } else { return this->jobb->keres(kulcs); } } Fa* Fa::min(){ if (this->bal == NULL){ return this; } else { return this->bal->min(); } } Fa* Fa::max(){ if (this->jobb == NULL){ return this; } else { return this->jobb->max(); } } Fa* Fa::kovetkezo(){ if (this->jobb != NULL){ return this->jobb->min(); } else { Fa* q = this->apa; Fa* p = this; while (q != NULL && p == q->jobb){ p = q; q = p->apa; } return q; } } Fa* Fa::elozo(){ if (this->bal != NULL){ return this->bal->max(); } else { Fa* p = this->apa; Fa* q = this; while (q != NULL && p == q->bal){ p = q; q = p->apa; } return q; } } void Fa::vag(Fa* vagasi_pont){ } void Fa::beszur(Fa* beszurando){ Fa* y = NULL; Fa* x = this; while (x != NULL){ y = x; if (beszurando->kulcs < y->kulcs){ x = x->bal; } else { x = x->jobb; } } beszurando->apa = y; if (y == NULL){ this->~Fa(); } else { if (beszurando->kulcs < y->kulcs){ y->bal = beszurando; } else { y->jobb = beszurando; } } } void Fa::torol(Fa* torlendo){ Fa *x, *y; if (torlendo->bal == NULL || torlendo->jobb == NULL){ y = torlendo; } else { y= torlendo->kovetkezo(); } if (y->bal != NULL){ x = y->bal; } else { x = y->jobb; } if (x != NULL){ x->apa = y->apa; } if (y->apa = NULL){ this->~Fa(); } else if (y == y->apa->bal) { y->apa->bal = x; } else { y->apa->jobb = x; } if (y != torlendo){ torlendo->kulcs = y->kulcs; } } void Fa::kiir(){ cout << "kulcs: " << this->kulcs; if (this->bal != NULL){ cout << " bal: " << this->bal->kulcs; } else { cout << " bal: NULL"; } if (this->jobb != NULL){ cout << " jobb: " << this->jobb->kulcs; } else { cout << " jobb: NULL"; } if (this->apa != NULL){ cout << " apa: " << this->apa->kulcs << endl; } else { cout << " apa: NULL" << endl; } if (this->bal != NULL){ this->bal->kiir(); } if (this->jobb != NULL){ this->jobb->kiir(); } } void Fa::kiir_egyet(){ cout << "kulcs: " << this->kulcs; if (this->bal != NULL){ cout << " bal: " << this->bal->kulcs; } else { cout << " bal: NULL"; } if (this->jobb != NULL){ cout << " jobb: " << this->jobb->kulcs; } else { cout << " jobb: NULL"; } if (this->apa != NULL){ cout << " apa: " << this->apa->kulcs << endl; } else { cout << " apa: NULL" << endl; } }

Main.cpp:
#include <iostream> #include <cstddef> #include <cstring> #include "Fa.hpp" using namespace std; int main (int argc, char** argv){ //fa letrehozasa Fa* fa = /*NULL; fa->beszur(*/new Fa(35, NULL, NULL, NULL); fa->beszur(new Fa(25, NULL, NULL, NULL)); fa->beszur(new Fa(10, NULL, NULL, NULL)); fa->beszur(new Fa(32, NULL, NULL, NULL)); fa->beszur(new Fa(7, NULL, NULL, NULL)); fa->beszur(new Fa(15, NULL, NULL, NULL)); fa->beszur(new Fa(28, NULL, NULL, NULL)); fa->beszur(new Fa(77, NULL, NULL, NULL)); fa->beszur(new Fa(73, NULL, NULL, NULL)); fa->beszur(new Fa(54, NULL, NULL, NULL)); fa->beszur(new Fa(75, NULL, NULL, NULL)); fa->beszur(new Fa(94, NULL, NULL, NULL)); fa->beszur(new Fa(88, NULL, NULL, NULL)); cout << endl; fa->kiir(); cout << "\n" << endl; //fa->vag(fa->keres(73)); //fa->kiir(); }
Mutasd a teljes hozzászólást!
Nos, megvan a megoldás. Így néz ki a vágás metódus:


void Fa::vag(Fa* v_pont){ vector<Fa*> kicsik; vector<Fa*> nagyok; Fa *aktualis = this, *kovetkezo; while (aktualis->kulcs != v_pont->kulcs){ if (aktualis->kulcs < v_pont->kulcs){ kicsik.push_back(aktualis); kovetkezo = aktualis->jobb; aktualis->jobb->apa = NULL; aktualis->jobb = NULL; } else if (aktualis->kulcs > v_pont->kulcs){ nagyok.push_back(aktualis); kovetkezo = aktualis->bal; aktualis->bal->apa = NULL; aktualis->bal = NULL; } aktualis = kovetkezo; } if (aktualis->bal != NULL){ kicsik.push_back(aktualis->bal); aktualis->bal->apa = NULL; aktualis->bal = NULL; } if (aktualis->jobb != NULL){ nagyok.push_back(aktualis->jobb); aktualis->jobb->apa = NULL; aktualis->jobb = NULL; } vector<Fa*>::const_iterator iter; int i = 0, j = 0; if(kicsik.size() > 0){ for(int i = 1; i < kicsik.size(); ++i){ kicsik.at(0)->beszur(kicsik.at(i)); } v_pont->bal = kicsik.at(0); v_pont->bal->apa = v_pont; } if (nagyok.size() > 0){ for(int j = 1; j < nagyok.size(); ++j){ nagyok.at(0)->beszur(nagyok.at(j)); } v_pont->jobb = nagyok.at(0); v_pont->jobb->apa = v_pont; } }
Mutasd a teljes hozzászólást!

Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd