Informatik 11 - Hierarchische Baumstrukturen Einführung
InformatikEasyGoing
https://www.youtube.com/watch?v=aKA1efHAoBE

Transkript (automatisch erstellt)

0:00 in diesem video geht es jetzt um hierarchische baumstrukturen das heißt bäume bei denen jetzt nicht wie bei binär bäumen die anzahl der nachfolger
0:09 pro daten beruhten auf zwei begrenzt ist sondern die daten beliebig viele nachfolger haben können und solche baumstrukturen wirst wir hier sehen wo
0:20 also jeder daten von höchstens drei nachfolger haben darf die eignen sich eben dazu um ihre strukturen zb in einem unternehmen darzustellen und könnte sich
0:29 also vorstellen ganz oben in der wurzel da steht jetzt der geschäftsführer und ihm sind jetzt mal zunächst die abteilungsleiter in der zweiten ebene
0:38 also kein zwang a3 unterstellt denen dann wiederum pro abteilung einzelne mitarbeiter unterstellt sind und diese mitarbeiter bilden dann zum teil
0:49 vielleicht noch azubis aus die eben dann in dieser vierten ebene stehen und bei der implementierung solcher allgemeinen baumstrukturen legt man jetzt eben nicht
1:02 mehr für jeden nachfolger daten knoten ein extra referenz attribut an sondern man fast jetzt alle in einem feld zusammen
1:10 und in diesem feld speichert man dann eben von links nach rechts einfach die referenzen auf die nachfolger und dabei ordnet man diese nachfolger dann in baum
1:24 eben auch so an dass man dieses feld von links her mit den daten knoten die nachfolger sind auffüllt und dann eben ab einem gewissen punkt kommen dann
1:33 keine daten mehr als nachfolger und diese plätze im feld werden einfach mit referenzen auf abschluss objekte aufgefüllt und so kann es natürlich auch
1:43 sein dass irgendein daten knoten jetzt zb der mitarbeiter im k5 keiner azubis hat also zeigen alle 3 referenzen hierauf abschluss objekte
1:58 man könnte jetzt natürlich auch hier die listen verwenden und statt einem feld wieder eine liste von nachfolgern verwalten
2:06 das hätte sicherlich den vorteil dieses variablen ist weil ich hier nicht am anfang festlegen muss wie viele nachfolge gibt es maximal also ich muss
2:16 diese obergrenze nicht wählen und die verschwende auch keinen unnötigen speicherplatz weil partys haben dann zwangsläufig ja auch drei nachfolger die
2:27 dann in der regel auf jeden fall abschluss elemente sind weil die in der niedrigsten ebene in den unternehmen stehen sondern hier könnte ich dann
2:35 einfach wirklich speicherplatz sparen indem ich eine liste einsätze und nicht extra 3 referenzen die immer auf den abschluss objekt zeigen haben muss
2:46 trotzdem werden wir jetzt hier einfach als von der implementierung von quellcode ein bisschen übersichtlicher und leichter verständlich ist wenn man
2:54 mit einem feld arbeitet weil ich dann lediglich noch die zusätzlichen methode einer verketteten liste aufrufen muss beim aus dem conwert wir jetzt eben mit
3:03 feldern arbeiten schauen was uns mal an an einer repressiven methode und zwar wenn ich einfach nur die baum daten ausgeben möchte
3:12 wir sind also in der klasse daten die er von der abstrakten klasse baum element erbt und da gibt es eben das attribut inhalt von der klasse daten element wie
3:21 du es bereits kennst und dann ist jetzt eben hier ein feld ein kinderfest wo eben diese referenzen auf die nachfolger gespeichert werden
3:30 um jetzt die ganze implementierung von repressiven methoden ein bisschen geschickter zu gestalten und auszunutzen dass wir das feld von den nachfolgern er
3:42 mit den daten knoten von links her auffüllen und nicht einfach irgendwo an eine freie stelle speichern bzw hohen abschluss objekt bisher hängt gibt es
3:53 noch das attribut in anzahl kind knoten und in dem attribut speicher ich eben wie viele daten knoten gibt es denn als nachfolger also bei k1 würde zum
4:04 beispiel drinstehen 2 weil zwei der drei nachfolger sind daten bykov würde eben 0 drin stehen so was passiert jetzt bei der methode baum daten ausgeben da
4:18 passiert erstmal eigentlich oder durchlauf von grundsätzlichen sie schaute jetzt allerdings aus wenn ich ein ganzes feld von nachfolgern habe ich
4:28 möchte jeweils das ganze in eckigen klammern ausgeben damit auch dann diese ebenen klar werden deswegen hier einfach nur der erste
4:36 letzte befehl klammer auf und kramer zu so bei der pre order gebe ich ja zunächst mal den inhalt des aktuellen datum knotens aus das heißt ich ruf beim
4:46 darten element die methode daten ausgeben auf obwohl eben einfach system auf print der inhalt ausgegeben und dann gehe ich jetzt über diese zählen
4:56 schleife hier wird die vor schleife durch mein feld von nachfolgern durch und rufe da relativ einfach auf diese methode baum daten ausgeben auf und da
5:07 fällt jetzt eben auch wir müssen ja bei der null anfangen felder beginnen immer beim index 0 und hier laufe ich jetzt nicht einfach
5:14 bis zum ende meines feldes sondern ich laufe nur so weit wie diese referenzen auch auf daten quoten zeigen und damit sich jetzt eben den berg zum einzelkind
5:26 knoten aus den ich hier gespeichert haben das heißt becker 1 da war der wert 2 das heißt da laufe ich nur die referenzen an
5:35 den stellen 0 und 1 ab also genau die zwei nachfolger von diesen daten die auch wieder daten geworden sind und bei den ganzen abschluss objekten mache ich
5:44 mir erst gar nicht die mühe die methode rico sie aufzurufen weil dabei sicher da passiert eh nichts und so spar ich mir laufzeit technisch gesehen zumindest
5:54 durch den einsatz dieses attribut hier einiges und das war es auch schon so sind also allgemeine räume aufgebaut indem ich die nachfolge eben in einem
6:08 feld von objekten der klasse beim element speicher weil es sind wir raten kurven oder abschluss elemente und eben mir die implementierung noch ein
6:18 bisschen geschickter mache indem ich hier zwischenspeicher wie viele der nachfolger sind denn auch tatsächlich daten knoten im nächsten
6:28 video werde ich dann zeigen wie man bei so einem allgemeinen baum die anzahl der datenfluten berechnen kann und auch die baumhöhe damit bedanke ich
6:37 mich fürs zuhören und bis zum nächsten mal