Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Übung: Binärbäume in der Informatik (Dynamische Datenstrukturen)
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 89 Zeilen
- hallo in diesem video schauen wir uns eine aufgabe an zur dynamischen datenstruktur bäume
- das heißt wir verwenden hier dieses arbeitsplatz dieses übungsplatz in dem es um verkettete liste stapel speicher warteschlange neben um die bäume geht
- dieses platz haben sie entweder in der schule von mir bekommen darüber dass tausch verzeichnis oder sie können dieses platz auch auf meiner webseite
- herunterladen auf dem informatiker nämlich hierbei programmierungen dann hierbei dynamische datenstrukturen und
- da gibt es dieses arbeitsplatz als word-dokument um selbst etwas mit hand rein schreiben zu können oder auch die druck
- freundliche version als pdf ok dann werfen wir mal einen blick auf dieses arbeitsplatz die bäume kommen ganz am schluss das scrollen wir ganz
- schnell hin so und im wesentlichen müssen wir hier bei diesen übungsaufgaben ankreuzen und teilweise auch eine kleine
- begründung dazu schreiben also machen sie mal folgendes diese aufgaben mit denen sollten sie sich jetzt ein paar minuten beschäftigen als hilfestellung
- sollten sie natürlich das entsprechende arbeitsplatz zu den bäumen verwenden es ist mit sicherheit nicht verkehrt dann noch mal reinzuschauen und sich noch mal
- genauer anzuschauen was sind bin eher bäume wie kann man die unter zeilen dieses arbeitsblatt finden sie auf dem informatik heller ebenso ganz unten mit
- einem erklär video oder auf der seite informatik - bg punkt.de auch da finden sie hier die dynamischen datenstrukturen und hier die bäume das ist das gleiche
- diese seite hier betreibe ich zusammen mit meinem kollegen von der informatik zentrale und hier sammeln wir das ganze material für
- die oberstufe des beruflichen gymnasiums in baden württemberg so ok dann legen sie mal los nehmen sie sich mal ein paar minuten und bearbeiten sie diese
- aufgaben die wir dann gleich besprechen bis dann okay dann gehe ich mal davon aus sie haben sich ordentlich mit den aufgaben auseinandergesetzt
- werfen mal einen blick auf die erste aufgabenliste mich leicht markieren sie hier was ist ein blatt was den wurzel was ist ein kind und was ist ein eltern
- knoten ok gucken wir uns das mal was ist die wurzel das ist klar aus der wurzel da entspringt dieser ganze baum
- die wurzel habe ich jetzt hier gleich mal mit dem weg markiert gleichzeitig ist die wurzel dann auch
- ein eltern knoten weil die wurzel ja kinder hat da können wir gleich mal alle anderen eltern knoten auch noch markieren
- und wo es eltern gibt da gibt es auch kinder die kinder knoten sind diese damen und
- als allerletztes fehlen uns dann noch die blätter die ich jetzt auch ganz schnell mal markieren
- so und das war's damit haben wir hier die wurzel die blätter die kinder und die eltern knoten markiert okay machen wir gleich mal weiter kreuzen sie an
- nämlich dass da ist dieser binär baum geordnet um herauszufinden ob ein binär baum geordnet ist da müssen wir ja im prinzip
- alles nach unten ziehen ist ein bisschen der baum ist ein bisschen arg zusammengeschoben also wenn ich das hier alles nach unten ziehen das muss
- eigentlich dahin ziehen dann kommt das dass das dann sehe ich hier 58 14 18 und die 13 passt überhaupt nicht das heißt wir haben hier nicht die richtige
- reihenfolge also geordnet ist der baum schon mal nicht also das kreuzen war mal nicht an ist der baum wenigstens voll da hilft vielleicht noch mal ein blick
- darauf zu werfen was war noch mal ein voller baum ein voller baum das war ja leicht das ist ein baum bei dem jeder knoten ein
- blatt ist oder zwei kinder besitzt und das können wir hier natürlich schnell beurteilen ja entweder an knoten
- dessen blatt das hier ist ein blatt das ist ein blatt das ist ein blatt und alle anderen knoten besitzen zwei kinder der besitzt zwei kinder er besitzt zwei
- kinder also tatsächlich ist dieser baum voll das kreuzen wenn man ja und jetzt kommt natürlich die frage ist dieser baum
- vollständig da ist es hilfreich wenn wir uns nochmal genau anschauen was waren nochmal vollständige binär bäume in einer
- älteren version des arbeitsplatzes hatte ich hier auch noch eine kleine ungenauigkeit es stand nur drin warum ist dann vollständig wenn sich alle
- blätter auf der gleichen höhe befinden ja das stimmt aber gleichzeitig muss der baum auch noch voll sein das heißt wenn ein baum nicht
- vorlässt müssen wir gar nicht überprüfen ob er vollständig ist warum ist dann vollständig wenn auch voll ist und wenn sich alle blätter auf der gleichen höhe
- befinden gut dieser baum ist voll das heißt wir müssen jetzt noch testen befinden sich die blätter auf der gleichen höhe und
- das sehen wir ja hier an dieser stelle das ist nicht der fall skizziert das nochmal ich mag ihr das nochmal der baum war ja voll aber hier
- das sind die blätter und die sind nicht auf der gleichen höhe deswegen ist der baum nicht vollständig ok dann können wir als letztes noch die
- höhe des baumes hier notieren 1 23 und damit hat dieser baum die höhe 3 damit können wir uns sofort auf die
- nächste aufgabe stürzen diesen bisschen fies muss ich sagen die frage lautet nämlich ist das hier ein baum und dass deswegen weil das ding
- sieht ja überhaupt gar nicht aus wie ein baum das liegt daran dass das die bäume die wir dargestellt haben dass die bisher
- eben immer anders aussahen also unsere bäume die haben wir immer ganz ordentlich gemacht oben ist die wurzel und dann wächst der baum eben von oben
- nach unten aber ehrlich gesagt das ist gar keine regeln ist noch ordentlich aber es ist keine regel die definiert was ein baum ist gucken wir uns noch mal
- an was ist denn eigentlich ein baum hier ist die definition ein baum besteht aus knoten der durch kanten verbunden
- sind und jetzt kommt es nur noch ein baum wenn es zwischen zwei beliebigen knoten nur einen weg gibt also ich darf zum beispiel einzelne knoten nicht wild
- noch untereinander verbinden sondern die haben immer genau eine verbindung zu ihren eltern knoten
- schauen wir uns vor diesem hintergrund noch mal dieses gebilde hier an ehrlich gesagt er habe das sind knoten die über kanten miteinander verbunden sind und
- es gibt immer nur genau einen weg von einem knoten zu einem anderen zu kommen also es gibt keine zusätzlichen verbindungen zwischen den knoten das
- hier ist ein baum er ist nur schlampig aufgemalt also eigentlich müsste der baum müssten diese diese diese knoten also dieser kind knoten das
- ist ja der kind knoten von dem oder schwer zu sagen ja eigentlich ist das der kind knoten von dem an die müsste der nach unten gezogen werden der müsste
- nach rechts gezogen werden usw also die darstellung ist ziemlich fies aber nach definition ist das ein baum also ja
- dann stürzen wir uns mal auf diese aufgabe kreuzes jahren ist dieser binär baum hier geordnet voll vollständig das ist jetzt erst mal ziemlich leicht er
- ist tatsächlich geordnet denn wenn wir mal hier der reihe nach alles nach unten ziehen ich stelle fest 588 sehen ja der baum ist der reihe nach
- geordnet und dann gibt es ja noch die weitere bedingung es darf kein knoten geben der nur ein rechtes kind hat also wenn ein knoten kinder hat dann darf ein
- linkes kind haben oder ein linkes und rechtes aber nicht nur ein recht ist und genau das haben wir hier linkes und rechtes kind also alles gut wir haben
- hier einen geordneten binär war dann ist die frage ist dieser binär baum voll ein voller baumes der einer bei dem jeder knoten entweder zwei kinder hat
- oder ein blatt ist und genau das ist der fall dieser knoten hier also die wurzel der knoten hat zwei kinder alle anderen knoten sind blätter damit ist dieser
- baum voll letzte frage ist dieser baum vollständig ein baum ist ja dann vollständig wenn alle blätter sich auf der gleichen höhe befinden das ist jetzt
- nämlich leicht es gibt nur zwei blätter und die sind tatsächlich auf der gleichen höhe also haben wir auch hier einen vollständigen bau und die
- einfachste übung ist natürlich zu sagen welche höhe hat dieser baum wir fangen wir an zu zählen 12 der bau hat also die höhe 2
- so jetzt kommt noch mal eine vergleichbare aufgabe bei der ich jetzt ankreuzen muss ist dieser bin eher warum geordnet voll vollständig so schauen wir
- uns erstmal geordnet an ist er geordnet wenn ich alles nach unten ziehe also dieses spiel mache dass das das da ist schon unten wären die zahlen dann gucke
- 12 13 18 22 okay würde ich denken ja es geordnet aber da gibt es ja noch die bedingung es darf nicht nur rechte kinder geben und der knoten 18 der hat
- aber nur ein rechtes kind also dieser baum ist nicht geordnet weil der knoten 18 eben nur ein rechtes kids hat
- ist dieser baum voll mit voller bin er war ja wenn jeder knoten entweder zwei kinder hat oder ein blatt ist und da sehen wir schon ja der knoten 18 der ist
- an allem schuld der hat nur ein kind also ist der baum auch nicht voll und vollständig ist der baum wir haben alle blätter sich auf der gleichen höhe
- befinden und das sehen sie glaube ich sofort ja der ist auch nicht vollständig weil es zwei blätter gibt die sich eben auf der afa verschiedenen höhe befinden
- also nichts davon dann können wir gleich zur nächsten aufgabe springen ist das ein baum und ich glaube das sehen sie sofort dass es
- kein baum weil es einen knoten gibt es nämlich die 14 zu der es zwei wege gibt also genau auf dieser thematik bin ich
- vorhin schon herumgeritten ist auch immer nur einen weg geben wie man zu einem knoten kommt [Musik]
- und hier haben wir eben zwei knoten die genau auf den verweisen damit ist das kein baum mehr
- so hier immer noch eine kreuzen sie an gleiches spiel wie immer sie merken dass die aufgaben gewisse monotonie haben okay auch hier sollen wir sagen ist
- dieser baum geordnet bis maine zwischen ja ich musste jetzt nicht runterziehen es gibt recht die
- kinder da ist ein echtes kind dessen rechtes kind also geordnet ist das schon mal nicht ist er war im foyer voll ist natürlich auch nicht weil da müsste ja
- jeder eltern knoten zwei kinder haben den knoten eltern knoten und die haben beide nur ein kind also voll ist auch nicht
- und wenn der baum nicht voll ist dann kann er auch nicht vollständig sein das wissen wir gucken wir uns hier noch mal die definition an was ist ein
- vollständiger beerbaum dass die einer der voll ist und alle blätter befinden sich auf der selben höhe und so weiter aber wenn alles kann auch nicht
- vollständig sein das heißt also bei dieser aufgabe hier haben wir keinen geordneten keinen vollen und damit automatisch auch keinen vollständigen
- binär baum soll dann können bei uns jetzt hier noch die letzte aufgabe anschauen ist dieser baum geordnet okay das spiel kennen wir inzwischen der
- eltern knoten die 200 hat nur ein rechtes kind damit ist also dieser binär baum schon mal nicht geordnet ist er voll
- das würde heißen dass jeder eltern knoten zwei kinder hat nähe ist nicht der fall also es auch nicht voll und wenn er nicht voll ist dann müssen wir
- das vollständige gar nicht überprüfen denn nur volle binär bäume können vollständig sein so und dann gibt es ganz und noch eine
- aufgabe nämlich diese darüber führen sie die knoten sieben acht neun zehn elf in einen vollen geordneten binär baum weil sie das überlesen haben und diese
- aufgabe nicht gemacht haben bei dem man selbst jetzt plötzlich malen muss halten sie das video bitte nochmal machen sie das nochmal und dann schauen sie sich
- danach biete meine lösung an wir sind jetzt hier zwei mögliche lösungen eingefallen ok schauen
- wir uns das mal an haben ich soll das ganze jahr in einen vollen baum überführen soll kann ich hier ganz schnell überprüfen
- jeder knoten ist ja ein platz wieder da und die da oder eltern knoten also wenn ein knoten den eltern knoten ist dann hat er zwei
- kinder okay das ist hier der fall dass es da drüben offensichtlich auch der fall geordnet ist ja auch wenn sie immer alles runter ziehen sieben acht neun
- zehn elf ist alles in der reihenfolge hier ebenso und es gibt nicht nur rechte kinder ich glaube auch dass es die beiden einzigen lösungen sind wenn sie
- eine andere haben zeigen sie mir gucken wir uns das mal an ok wunderbar dann haben wir diese aufgaben zu den bäumen erschlagen ich
- glaube sie haben gemerkt dass die aufgabenstellungen immer sehr sehr ähnlich sind und dann bis zum nächsten video
Zum Nachlesen
BinärbaumBinärbäume sind in der Informatik die am häufigsten verwendete Unterart der Bäume. Im Gegensatz zu anderen Arten von Bäumen können die Knoten eines …
Baum (Datenstruktur)In der Informatik ist ein Baum (engl. tree) eine Datenstruktur und ein abstrakter Datentyp, mit dem sich hierarchische Strukturen abbilden lassen.
Baum (Graphentheorie)Ein Baum ist in der Graphentheorie ein spezieller Typ von Graph, der zusammenhängend ist und keine geschlossenen Pfade enthält, d. h. ein Graph, …
Binärer SuchbaumIn der Informatik ist ein binärer Suchbaum eine Kombination der abstrakten Datenstrukturen Suchbaum und Binärbaum. Ein binärer Suchbaum, häufig abgekürzt …