wir wollen uns als nächstes anschauen wie man bäume in java darstellen kann in den beispielen findet ihr dafür eine klasse binary tree diese klasse ist so gedacht dass er zum einen einen knoten darstellt zum anderen ist jeder knoten wieder die wurzel für einen teil baum also knoten und teil baum ist für mich in dem fall das gleiche die klasse selber stellt nicht nur die verkettung im baum da sondern für jeden knoten können wir auch noch nutzdaten speichern sowie bei der liste auch um diese daten sind vom typ tnt zum beispiel in texas dann können wir
in unserem knoten im internet speichern und dann die beiden kinder das linke und das rechte kind für den binär baum die kinder können wieder irgendwelche werte haben und so weiter und so fort damit ist klar dass wir pro knoten die folgenden attribute brauchen einmal ein attribut data das speichert unsere nutzlast das was wir mit dem knoten speichern wollen also 123 hier beispiel dann zwei referenzen eine auch das linke und eine auf das rechte kind also für den knoten 1 hier hätte die referenz läuft diesen knoten und die referenz bereit diesen knoten bezeichnet was wir zusätzlich
noch machen ist wir speichern auch noch eine referenz parent auf den eltern knoten also über den knoten nummer zwei wäre dass die referenz nach 1 für den knoten nummer drei wäre dass die referenz nach 1 und der knoten 1 ist hier die wird die wurzel der hat keinen eltern knoten dementsprechend würde hier in 0 referenz stehen all diese attribute verstecken wir in der implementierung die soll niemand direkt auslesen und vor allem nicht direkt manipulieren die sind privat ich habe es als package privat deklariert wie schon gesagt ich deute das immer an dass die attribute nahmen
den unterstrich am ende bekommen es ist eher lustlos konvention als in java konventionen ich das in den beispielen recht konsistent so durch gut wir wollten nicht direkt auf die attribute zu greifen sondern das soll über methoden geschehen und das sind einmal den begriff kennt man auch noch aus dem wintersemester select ohren also methoden die mir was über den aktuellen zustand aussagen ohne den zustand selbst zu verändern das sind hier geht parent geschäft und betreibt die mir jeweils die entsprechenden referenzen zurück liefern die implementierung ist was ganz einfach gibt einfach diese referenz diese referenz ohne diese
referenz zurück ganz ähnlich fürbeth data at data liefert mir den daten wird die nicht an dem knoten speicher ist ein fehler auf der folie data ist vom typ t hier kriege ich natürlich einen guten zurück sondern ich krieg tatsächlich etwas vom typ t zurück so was wollen wir noch wissen wir wollen für einen knoten zb entscheiden können ob der knoten die wurzel oder ein plattes das ist auch wieder recht einfach die methode ist gut schaut ob die parent referenz gleich null ist also wenn da eine null referenz ist wenn paare nicht auf den anderen knoten
zeigt dann ist dieser knoten zu knoten die methode ist lief schaut ob sowohl das rechte kind als auch das linke kind nicht vorhanden sind also ob sowohl in left als auch in lightning 0 referenz steht mit diesen methoden können wir zum beispiel schon in knoten aufwärts richtung wurzel tradieren wenn wir uns vorstellen ja hier die wurzeln und hier kinder heute restlichen baumann und wir starten hier in diesen knoten dann würde die methode getrud jetzt fordern diesen knoten ausgehend immer wieder nach oben richtung parent laufen also zum eltern knoten zum pad und noten zum eltern knoten
und zwar so lange bis es hier nicht mehr weitergeht also bis wir als eltern knoten im java oder statt dem eltern guten referenzen und genau das passiert hier in co die methode getrud 3 basiert vom aktuellen knoten gedroht ist eine methode vom baum also von einem knoten das heißt der aktuelle boden das bild tatsächlich ich selber die des referenz von hier aus lauf ich nach oben so lange wie der aktuelle knoten nicht die wurzel ist also wir schreiben hier die neue referenz tatsächlich nicht nochmal aus sondern wir haben es schon in der methode ist einmal
implementiert dann benutzen wir die auch solange wir nicht am wurzel knoten sind laufen wir eins weiter nach oben also machen not zum eltern knoten wenn nun schließlich die wurzel ist richtig schleife ab und her geben diesen knoten zurück ein bisschen spannender wird es jetzt wenn man den baum tatsächlich manipulieren wollen also wir haben methoden mit deren hilfe wir für einen knoten das linke beziehungsweise das rechte kind setzen können dethleffs etrade sind im wesentlichen gleich nur spiegelverkehrt wir schauen uns hier beispielhaft set läuft an das ganze soll so funktionieren dass wir als eingabe das neue linke
kind haben das ist ein knoten und gleichzeitig eben auch ganzer baum an den knoten kann ein ganzer baum dranhängen und die methode set left soll den alten knoten oder den altenteil baum der ausgehängt wird zurückgehen schauen wir uns kurz zum beispiel an wir wollen in diesem baum für den wurzel knoten dessen linkes kind also diesen knoten und damit diesen kompletten teil baum hier ersetzen als eingabe für detlef nehmen wir unseren neuen baum das soll dieser rote hier sein und was jetzt passiert ist dass wir hier kurz als erstes den altenteil baumärkten all den wollen wir
auf jeden fall am ende zurück geben das heißt wir halten uns erstmal eine referenz auf den altenteil geholt danach setzen wir an unseren knoten das ist der wurzel knoten die referenz für das linke kommt also läuft auf unseren neuen teil baum also diese referenz hier umgebogen auf diese und schon haben wir den alten teil baum ausgehängt jetzt könnten schon fast fertig sein die verkettung hier funktioniert genau wie für die verketteten listen auch wir haben uns in diese implementierung dafür entschieden sowohl nach unten zu den kindern hin zu verketten das müssen wir auf jeden fall machen
beim baum aber auch wieder zurück nach oben zum eltern knoten zu verketten das entspricht also einer doppelt verketteten liste und insofern haben wir jetzt noch arbeit weil wir dafür sorgen müssen dass die referenzen auch die eltern knoten stimmen was bedeutet dass einmal wir haben hier den roten keil baum neu eingefügt das war unser argument trieb und diese rote teil bau der soll jetzt als eltern knoten unseren aktuellen knoten bekommen und das trat man an dieser stelle auch ein das passiert hier jetzt haben aber einen sonderfall und zwar ich möchte zu lassen dass der knoten den
ich hier reingehen tatsächlich auch eine null referenz ist das heißt wenn ich sagt das linke kind sollen lehrer baum sein dafür soll die neue referenz stehen bedeutet dass ich möchte das linke kind löschen mit der konvention ist das gar kein problem weil ich schreib mir nun würden die neue referenz reinschreiben allerdings wenn ich ihnen nun referenz reingeht dann ist natürlich für die neue referenz kein knoten hinterlegt das heißt da ist auch kein parent definiert das heißt in dem fall wenn ich einen knoten raus frisch gibt es da keine rückwärts referenz zum hintern knoten zu setzen
jetzt hat auch der alte knoten noch eine referenz auf seinen eltern knoten die muss man auch noch waschen den alten knoten wollen aushänge in den hang vielleicht woanders wieder ein aber wir wollen dafür sorgen dass diese referenz auch wieder verschwindet und die löschmann indem wir sie hier 0 sätzen ausnahme ist auch wieder dass der alte knoten oder der alte teil baum der nicht ausgehängt habt tatsächlich existieren musste wenn ich den linken knoten setzt einem knoten ja noch keinen linken knoten hatte dann stand vorher in left 0 referenz und damit wäre auch holt das konzil gemerkt
haben gleich null dann gibt es natürlich auch wieder nichts nach rückwärts zum eltern knoten zu verketten also die rückwärts verkettungen die wir hier machen geschehen jeweils nur dann wenn das entsprechende ziel auch existiert hat das waren erstmals schon die schwierigsten methoden vom ganzen baum weil es ein paar sonderfall ich hätte jetzt fehlen uns noch die konstrukt uhr und dazu nehmen uns zwei konstrukteuren vor einmal einen konstrukteur der den einzelnen knoten ohne kinder konstruiert der nimmt auch wieder den daten wert und den schreibt denn die knoten rhein zum beispiel 1 und dem zweiten konstrukt uhr der
nimmt auch einen daten wert aber gleichzeitig nimmt er als argument noch einen linken und einen rechten knoten beziehungsweise teil baum als kind so dass ich mit diesem konstrukt nicht nur einen knoten sondern einen ganzen baum konstruieren auf die art und weise kann ich mir recht passiv boy mit bauen ich habe den linken teil baum ich habe den rechten teil warum es die gleiche skizze bloß die reihenfolge ist noch mal anders jetzt baue ich mir einen neuen knoten der diesen linken teil baum und den rechten teil und baum als linkes und rechtes kind hat und das
ganze kann ich natürlich eine stufe höher wieder machen und so weiter und so fort wie funktioniert das wir setzen einmal den daten wird eine schöne anwendung von dem das schlüsselwort das in dem fall dazu dient den anderen konstrukt ort den wir hier oben definiert haben aufzurufen hier passiert zwar nicht viel aber im zweifel finde ich das immer ganz schön hier zu sagen wir machen nichts anderes als das was der konstrukt ort macht wenn hier was ändern würden müssten wir hier nichts mehr ändern danach setzen wir den linken und den rechten teil baum also linkes und
rechtes kind und setzten für das linke und das rechte kind dann auch den eltern den knoten auf und selbst also wir machen wieder einmal diese referenzen nach unten und was hier passiert sind es die rückwärts referenzen nach oben auch hier ist es wieder sinnvoll dass links und rechts ein lehrer baum ist also dass ich hier verläuft und reiht in 0 referenz mit geht in dem fall würde hier einfach in der linke teil baum nicht existiert würde ich einfach den 0 referenz stehen also ist hier gar nichts mehr aber dann könnte ich natürlich auch keine rückwärts
referenz setzen wir brauchen als ich hier wieder die fall unterscheidung das ist unser rundum sorglos paket für den binär baum und mit hilfe von diesem baum als basis wenn wir jede menge andere bäume vor allem binäre suchräume implementieren diese implementierung speichert explizit den verweis auf den eltern knoten also nochmal wie gerade eben wir haben eine verkettung nach unten aber eben auch wieder nach oben zum eltern knoten entspricht mehr doppelt verketteten liste wir machen das weil es uns an einigen stellen das leben leichter macht wenn man nicht nur nach unten im baum wandern können sondern auch
jederzeit wieder nach oben kommen allerdings ist diese verkettung tatsächlich nicht immer nötig und viele algorithmen die wir uns anschauen brauchen die tatsächlich nicht beziehungsweise mit ein kleines bisschen mehr arbeit am algorithmus am code können wir uns das spaß und können uns damit auch könnten wir uns den speicher sparen um den preis dass wir ja den aufwendigeren quoten wir haben hier dafür entschieden dass wir beim einfachen code bleiben wo wir jederzeit von den knoten auch wieder zum eltern knoten kommen und deswegen verwenden wir diese doppelte verkettung es ist einfach bequem ein preis die man natürlich auch
zahlen müssen auch die implementierung hat ihre nachteile sie braucht nicht nur mehr speicher sondern wir haben gesehen dass die konstrukteuren und methoden wie es läuft und stride bisschen komplexer sind als sie vielleicht sein müssten weil wir immer die rückwärts referenz zum eltern knoten auch noch berücksichtigen müssen und weil wir dort auch immer noch mal sonderfälle berücksichtigen müssen so wie wir es definiert haben ist das meistens sehr praktisch wenn man satt left right einmal definiert haben dann kann man das wunderbar verwenden und müssen uns keine gedanken machen manchmal ist die extra arbeit die setlist und vertreibt
sich machen aber auch störend dann müssen wir eventuell mal kurzzeitig den eltern knoten vorher aushängen dass ein bisschen unschön aber es funktioniert auf jeden fall er findet alternativen mit einfacher verkettung also wo diese verkettung der weg nach oben fehlt zum beispiel in buchform untersagte und kay uwe sattler also auch hier schaut euch verschiedene implementierungen an alle haben ihre vor und nachteile es gibt nicht unbedingt die beste es gibt immer den preis den wir zahlen müssen und damit sie müssen beim nächsten thema und das macht man im nächsten video wir fangen an mit der ersten anwendung
von bäumen zur darstellung von terni