Sortierter Binärbaum
-
Hallo....
Ich soll einen sortierten Binärbaum Programmieren. Bin bis jetzt eigentlich immer gut mitgekommen hab im moment aber keine Ahnung wie ich da ran gehn soll?? Welche Elemente ich noch brauch, welche funktionen ich definieren muss? Und überhaupt
....Hier einfach mal die Aufgabenstellung,..
http://www.fh-kl.de/~amueller/vorlesungen/swt2/blatt09.pdf
(nur 1. Teil also dass für 3P)Wär echt nett wenn mir jemand helfen könnt.
Mit freundlichen Grüßen
Andre
-
du brauchst weder elemente noch funktionen dazuerfinden (mag uU aber praktisch sein).
Weisst du wie ein binaerer Baum funktioniert? Weisst du wie ein sortierter baum funktioniert?
es ist schwer zu helfen ohne konkrete fragen zu bekommen
-
Die Vorgaben sind ja als erstes mal dass es keinen leeren gibt also mindestens ein Element im Baum ist. Was ja soviel heisst dass ich meinem Konstruktor nen int mitgeb und den auf das elem zuweise.
Sehe ich das Richtig?Das zweite ist, ich muss ja in meinem Baum Werte einfügen. Wie der Baum funktioniert also kleinerer Wert, linker Teilbaum, grösserer Wert rechter Teilbaum etc. Doch wie Programmier ich das? Das ganze wird ja rekursiv ablaufen und irgendwie hab ich da ein Problem mir das vorzustellen wie ich das ablaufen lass?
-
1. Ja Richtig.
Im Konstruktor initialisets du die pointer left und right mit 0.
In insertElement machst du dann folgendes
Pseudocode:wenn key > elem dann nextElem = right sonst nextElem = left wenn nextElem == 0 dann neues Element erzeugen sonst nextElem.insertElement(key)Ich hoffe das hilft dir weiter.
-
Du *musst* min. eine "Funktion dazuerfinden", nämlich den dtor, ohne den wird das nix werden.
Insert kann z.B. einfach so aussehen:
void baumi::insert(int e) { if (e == m_element) return; else { baumi*& p = (e < m_element) ? m_left : m_right; if (p) p->insert(e); else p = new baumi(e); } }Da auch nirgends eine Schranke für die max. Laufzeit/Komplexität vorgegeben ist sind alle weiteren Funktionen recht einfach implementierbar. Ein "remove" kannst du z.B. implementieren indem du den gesamten Teilbaum "aushängst", und dann die Knoten darunter (children) einzeln wieder in den original Baum einfügst.
-
