[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki15\/2020\/11\/25\/baumdurchquerung-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki15\/2020\/11\/25\/baumdurchquerung-wikipedia\/","headline":"Baumdurchquerung – Wikipedia","name":"Baumdurchquerung – Wikipedia","description":"before-content-x4 “Baumsuche” leitet hier weiter. Es ist nicht mit dem Suchbaum zu verwechseln. In der Informatik Baumdurchquerung (auch bekannt als","datePublished":"2020-11-25","dateModified":"2020-11-25","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki15\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki15\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/d\/dc\/Sorted_binary_tree_ALL.svg\/281px-Sorted_binary_tree_ALL.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/d\/dc\/Sorted_binary_tree_ALL.svg\/281px-Sorted_binary_tree_ALL.svg.png","height":"240","width":"281"},"url":"https:\/\/wiki.edu.vn\/wiki15\/2020\/11\/25\/baumdurchquerung-wikipedia\/","wordCount":3882,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4“Baumsuche” leitet hier weiter.  Es ist nicht mit dem Suchbaum zu verwechseln.In der Informatik Baumdurchquerung (auch bekannt als Baumsuche und auf dem Baum spazieren gehen) ist eine Form der Diagrammdurchquerung und bezieht sich auf den Prozess des Besuchs (\u00dcberpr\u00fcfens und \/ oder Aktualisierens) jedes Knotens in einer Baumdatenstruktur genau einmal.  Solche Durchquerungen werden nach der Reihenfolge klassifiziert, in der die Knoten besucht werden.  Die folgenden Algorithmen werden f\u00fcr einen Bin\u00e4rbaum beschrieben, k\u00f6nnen jedoch auch auf andere B\u00e4ume verallgemeinert werden.Im Gegensatz zu verkn\u00fcpften Listen, eindimensionalen Arrays und anderen linearen Datenstrukturen, die kanonisch in linearer Reihenfolge durchlaufen werden, k\u00f6nnen B\u00e4ume auf mehrere Arten durchlaufen werden.  Sie k\u00f6nnen in der Reihenfolge Tiefe zuerst oder Breite zuerst durchlaufen werden.  Es gibt drei g\u00e4ngige Methoden, um sie in der Reihenfolge erster Tiefe zu durchlaufen: in der Reihenfolge, vor der Reihenfolge und nach der Reihenfolge.[1]  \u00dcber diese grundlegenden Durchquerungen hinaus sind verschiedene komplexere oder hybride Schemata m\u00f6glich, z. B. tiefenbegrenzte Suchvorg\u00e4nge wie die iterative vertiefende Tiefensuche.  Letzteres sowie die Breitensuche k\u00f6nnen auch zum Durchqueren unendlicher B\u00e4ume verwendet werden (siehe unten).Table of ContentsDatenstrukturen f\u00fcr die Baumdurchquerung[edit]Tiefensuche des Bin\u00e4rbaums[edit]Vorbestellung (NLR)[edit]In-order (LNR)[edit]In umgekehrter Reihenfolge umkehren (RNL)[edit]Nachbestellung (LRN)[edit]Generischer Baum[edit]Breitensuche \/ Ebenenreihenfolge[edit]Andere Arten[edit]Anwendungen[edit]Implementierungen[edit]Tiefensuche[edit]Vorbestellung[edit]In Ordnung[edit]Nachbestellung[edit]Morris In-Order-Traversal mit Threading[edit]Breitensuche[edit]Unendliche B\u00e4ume[edit]Verweise[edit]Externe Links[edit]Datenstrukturen f\u00fcr die Baumdurchquerung[edit]Beim Durchlaufen eines Baums werden auf irgendeine Weise alle Knoten durchlaufen.  Da von einem bestimmten Knoten mehr als ein m\u00f6glicher n\u00e4chster Knoten vorhanden ist (es handelt sich nicht um eine lineare Datenstruktur), m\u00fcssen unter der Annahme einer sequentiellen Berechnung (nicht parallel) einige Knoten zur\u00fcckgestellt und f\u00fcr einen sp\u00e4teren Besuch auf irgendeine Weise gespeichert werden.  Dies erfolgt h\u00e4ufig \u00fcber einen Stapel (LIFO) oder eine Warteschlange (FIFO).  Da ein Baum eine selbstreferenzielle (rekursiv definierte) Datenstruktur ist, kann die Durchquerung durch Rekursion oder subtiler durch Corecursion auf sehr nat\u00fcrliche und klare Weise definiert werden.  In diesen F\u00e4llen werden die zur\u00fcckgestellten Knoten implizit im Aufrufstapel gespeichert.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Die Tiefensuche kann leicht \u00fcber einen Stapel implementiert werden, einschlie\u00dflich rekursiv (\u00fcber den Aufrufstapel), w\u00e4hrend die Breitensuche leicht \u00fcber eine Warteschlange implementiert wird, einschlie\u00dflich Kernkurs.  Tiefendurchquerung eines Beispielbaums: Vorbestellung (rot): F, B, A, D, C, E, G, I, H; in der Reihenfolge (gelb): A, B, C, D, E, F, G, H, I; Nachbestellung (gr\u00fcn): A, C, E, D, B, H, I, G, F.Tiefensuche des Bin\u00e4rbaums[edit]Diese Suchen werden als bezeichnet Tiefensuche (DFS), da der Suchbaum bei jedem Kind so weit wie m\u00f6glich vertieft wird, bevor zum n\u00e4chsten Geschwister \u00fcbergegangen wird.  F\u00fcr einen Bin\u00e4rbaum werden sie als Zugriffsoperationen an jedem Knoten definiert, beginnend mit dem aktuellen Knoten, dessen Algorithmus wie folgt lautet:[2][3]Das allgemeine rekursive Muster zum Durchlaufen eines Bin\u00e4rbaums lautet wie folgt:       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Gehen Sie eine Ebene nach unten zum rekursiven Argument N..  Wenn N. existiert (ist nicht leer) F\u00fchren Sie die folgenden drei Operationen in einer bestimmten Reihenfolge aus:(L)Rekursiv durchqueren N.linker Teilbaum.(R)Rekursiv durchqueren N.ist der richtige Teilbaum.(N)Verarbeiten Sie den aktuellen Knoten N. selbst.Kehren Sie zur\u00fcck, indem Sie eine Ebene h\u00f6her gehen und den \u00fcbergeordneten Knoten von erreichen N..In den Beispielen wird (L) meistens vor (R) durchgef\u00fchrt.  Aber (R) vor (L) ist auch m\u00f6glich, siehe (RNL).Vorbestellung (NLR)[edit]Greifen Sie auf den Datenteil des aktuellen Knotens zu.Durchlaufen Sie den linken Teilbaum, indem Sie die Vorbestellungsfunktion rekursiv aufrufen.Durchlaufen Sie den rechten Teilbaum, indem Sie die Vorbestellungsfunktion rekursiv aufrufen.Die Durchquerung vor der Bestellung ist topologisch sortiert, da ein \u00fcbergeordneter Knoten verarbeitet wird, bevor einer seiner untergeordneten Knoten ausgef\u00fchrt wird.In-order (LNR)[edit]Durchlaufen Sie den linken Teilbaum, indem Sie die Funktion in der Reihenfolge rekursiv aufrufen.Greifen Sie auf den Datenteil des aktuellen Knotens zu.Durchlaufen Sie den rechten Teilbaum, indem Sie die Funktion in der Reihenfolge rekursiv aufrufen.In einem bin\u00e4ren Suchbaum, der so angeordnet ist, dass in jedem Knoten der Schl\u00fcssel gr\u00f6\u00dfer als alle Schl\u00fcssel in seinem linken Teilbaum und kleiner als alle Schl\u00fcssel in seinem rechten Teilbaum ist, werden die Schl\u00fcssel in der Reihenfolge des Durchlaufs abgerufen aufsteigend sortierte Reihenfolge.[4]In umgekehrter Reihenfolge umkehren (RNL)[edit]Durchlaufen Sie den rechten Teilbaum, indem Sie die Funktion “In umgekehrter Reihenfolge” rekursiv aufrufen.Greifen Sie auf den Datenteil des aktuellen Knotens zu.Durchlaufen Sie den linken Teilbaum, indem Sie die Funktion f\u00fcr die umgekehrte Reihenfolge rekursiv aufrufen.In einem bin\u00e4ren Suchbaum werden die Schl\u00fcssel in umgekehrter Reihenfolge abgerufen absteigend sortierte Reihenfolge.Nachbestellung (LRN)[edit]Durchlaufen Sie den linken Teilbaum, indem Sie die Nachbestellfunktion rekursiv aufrufen.Durchlaufen Sie den rechten Teilbaum, indem Sie die Nachbestellfunktion rekursiv aufrufen.Greifen Sie auf den Datenteil des aktuellen Knotens zu.Die Spur einer Durchquerung wird als Sequentialisierung des Baumes bezeichnet.  Die Traversal-Trace ist eine Liste jeder besuchten Wurzel.  Keine Sequenzierung nach Vor-, In- oder Post-Order beschreibt den zugrunde liegenden Baum eindeutig.  Bei einem Baum mit unterschiedlichen Elementen reicht eine Vor- oder Nachbestellung in Kombination mit einer Reihenfolge aus, um den Baum eindeutig zu beschreiben.  Die Vorbestellung mit der Nachbestellung f\u00fchrt jedoch zu Unklarheiten in der Baumstruktur.[5]Generischer Baum[edit]F\u00fchren Sie die folgenden Operationen an jedem Knoten rekursiv aus, um einen Baum mit Tiefensuche zu durchlaufen.Vorbestellungsvorgang durchf\u00fchren.F\u00fcr jeden ich von 1 bis zur Anzahl der Kinder:Besuch ich-th, falls vorhanden.F\u00fchren Sie den ordnungsgem\u00e4\u00dfen Betrieb durch.Nachbestellungsvorgang durchf\u00fchren.Abh\u00e4ngig vom jeweiligen Problem sind die Vorbestellungs-, In-Order- oder Nachbestellungsvorg\u00e4nge m\u00f6glicherweise ung\u00fcltig, oder Sie m\u00f6chten m\u00f6glicherweise nur ein bestimmtes untergeordnetes Element besuchen. Daher sind diese Vorg\u00e4nge optional.  In der Praxis kann auch mehr als eine Vorbestellungs-, In-Order- und Nachbestellungsoperation erforderlich sein.  Wenn Sie beispielsweise in einen tern\u00e4ren Baum einf\u00fcgen, wird eine Vorbestellungsoperation ausgef\u00fchrt, indem Elemente verglichen werden.  M\u00f6glicherweise ist anschlie\u00dfend eine Nachbestellungsoperation erforderlich, um den Baum neu auszugleichen.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Breitensuche \/ Ebenenreihenfolge[edit]  Level-Reihenfolge: F, B, G, A, D, I, C, E, H.B\u00e4ume k\u00f6nnen auch durchquert werden Level-Reihenfolge, wo wir jeden Knoten auf einer Ebene besuchen, bevor wir zu einer niedrigeren Ebene gehen.  Diese Suche wird als bezeichnet Breitensuche (BFS), da der Suchbaum in jeder Tiefe so weit wie m\u00f6glich erweitert wird, bevor zur n\u00e4chsten Tiefe gewechselt wird.Andere Arten[edit]Es gibt auch Tree-Traversal-Algorithmen, die weder als Tiefensuche noch als Breitensuche klassifiziert werden.  Ein solcher Algorithmus ist die Monte-Carlo-Baumsuche, die sich auf die Analyse der vielversprechendsten Bewegungen konzentriert und die Erweiterung des Suchbaums auf zuf\u00e4lligen Stichproben des Suchraums basiert.Anwendungen[edit]  Baum, der den arithmetischen Ausdruck darstellt EIN * (B. – – C.) + (D. + E.)Das Durchlaufen der Vorbestellung kann verwendet werden, um einen Pr\u00e4fixausdruck (polnische Notation) aus Ausdrucksb\u00e4umen zu erstellen: Durchlaufen Sie den Ausdrucksbaum vorab.  Wenn Sie beispielsweise den dargestellten arithmetischen Ausdruck in Vorbestellung durchlaufen, erhalten Sie “+ * EIN – – B. C. + D. E.“.Nachbestellungsdurchlauf kann eine Postfix-Darstellung (umgekehrte polnische Notation) eines Bin\u00e4rbaums erzeugen.  Durchlaufen des dargestellten arithmetischen Ausdrucks in Nachbestellungsertr\u00e4gen “EIN B. C. – * D. E. + + “; letzteres kann leicht in Maschinencode umgewandelt werden, um den Ausdruck von einer Stapelmaschine auszuwerten.In-Order-Traversal wird sehr h\u00e4ufig f\u00fcr bin\u00e4re Suchb\u00e4ume verwendet, da es Werte aus der zugrunde liegenden Menge in der angegebenen Reihenfolge zur\u00fcckgibt, gem\u00e4\u00df dem Komparator, der den bin\u00e4ren Suchbaum eingerichtet hat.Durch die Nachbestellung beim L\u00f6schen oder Freigeben von Knoten und Werten kann ein ganzer Bin\u00e4rbaum gel\u00f6scht oder freigegeben werden.  Dadurch wird der Knoten freigegeben, nachdem seine untergeordneten Knoten freigegeben wurden.Auch das Duplizieren eines Bin\u00e4rbaums ergibt eine Folge von Aktionen nach der Reihenfolge, weil der Zeiger Kopieren der Kopie eines Knotens wird das entsprechende untergeordnete Feld zugeordnet N.child innerhalb der Kopie des Elternteils N. gleich nach returnKopieren   in der rekursiven Prozedur.  Dies bedeutet, dass der Elternteil nicht fertig sein kann, bevor nicht alle Kinder fertig sind.Implementierungen[edit]Tiefensuche[edit]Vorbestellung[edit]preorder(node)    if (node == null)        return    visit(node)    preorder(node.left)    preorder(node.right)iterativePreorder(node)  if (node == null)    return  s \u2190 empty stack  s.push(node)  while (not s.isEmpty())    node \u2190 s.pop()    visit(node)    \/\/right child is pushed first so that left is processed first    if node.right \u2260 null      s.push(node.right)    if node.left \u2260 null      s.push(node.left)In Ordnung[edit]inorder(node)    if (node == null)        return    inorder(node.left)    visit(node)    inorder(node.right)iterativeInorder(node)  s \u2190 empty stack  while (not s.isEmpty() or node \u2260 null)    if (node \u2260 null)      s.push(node)      node \u2190 node.left    else      node \u2190 s.pop()      visit(node)      node \u2190 node.rightNachbestellung[edit]postorder(node)    if (node == null)        return    postorder(node.left)    postorder(node.right)    visit(node)iterativePostorder(node)  s \u2190 empty stack  lastNodeVisited \u2190 null  while (not s.isEmpty() or node \u2260 null)    if (node \u2260 null)      s.push(node)      node \u2190 node.left    else      peekNode \u2190 s.peek()      \/\/ if right child exists and traversing node      \/\/ from left child, then move right      if (peekNode.right \u2260 null and lastNodeVisited \u2260 peekNode.right)        node \u2190 peekNode.right      else        visit(peekNode)        lastNodeVisited \u2190 s.pop()Alle obigen Implementierungen erfordern einen Stapelplatz proportional zur H\u00f6he des Baums, der ein Aufrufstapel f\u00fcr die rekursiven und ein \u00fcbergeordneter Stapel f\u00fcr die iterativen ist.  Bei einem schlecht ausbalancierten Baum kann dies erheblich sein.  Mit den iterativen Implementierungen k\u00f6nnen wir die Stapelanforderung entfernen, indem wir \u00fcbergeordnete Zeiger in jedem Knoten beibehalten oder den Baum einf\u00e4deln (n\u00e4chster Abschnitt).Morris In-Order-Traversal mit Threading[edit]Ein Bin\u00e4rbaum wird eingef\u00e4delt, indem jeder linke untergeordnete Zeiger (der sonst null w\u00e4re) auf den Vorg\u00e4nger in der Reihenfolge des Knotens zeigt (falls vorhanden) und jeder rechte untergeordnete Zeiger (der sonst null w\u00e4re) auf den in zeigt Auftragsnachfolger des Knotens (falls vorhanden).Vorteile:Vermeidet Rekursion, die einen Aufrufstapel verwendet und Speicher und Zeit verbraucht.Der Knoten zeichnet sein \u00fcbergeordnetes Element auf.Nachteile:Der Baum ist komplexer.Wir k\u00f6nnen jeweils nur eine Durchquerung durchf\u00fchren.Es ist anf\u00e4lliger f\u00fcr Fehler, wenn beide untergeordneten Elemente nicht vorhanden sind und beide Knotenwerte auf ihre Vorfahren verweisen.Morris Traversal ist eine Implementierung von In-Order-Traversal, die Threading verwendet:[6]Erstellen Sie Links zum Nachfolger in der Reihenfolge.Drucken Sie die Daten \u00fcber diese Links.Setzen Sie die \u00c4nderungen zur\u00fcck, um den urspr\u00fcnglichen Baum wiederherzustellen.Breitensuche[edit]Im Folgenden ist der Pseudocode f\u00fcr eine einfache Warteschlangen-basierte Durchquerung der Ebenenreihenfolge aufgef\u00fchrt und erfordert Speicherplatz proportional zur maximalen Anzahl von Knoten in einer bestimmten Tiefe.  Dies kann so viel sein wie die Gesamtzahl der Knoten \/ 2. Ein platzsparenderer Ansatz f\u00fcr diese Art der Durchquerung kann mithilfe einer iterativen vertiefenden Tiefensuche implementiert werden.levelorder(root)    q \u2190 empty queue    q.enqueue(root)    while not q.isEmpty() do        node \u2190 q.dequeue()        visit(node)        if node.left \u2260 null then            q.enqueue(node.left)        if node.right \u2260 null then            q.enqueue(node.right)Unendliche B\u00e4ume[edit]W\u00e4hrend das Durchqueren normalerweise f\u00fcr B\u00e4ume mit einer endlichen Anzahl von Knoten (und damit endlicher Tiefe und endlichem Verzweigungsfaktor) durchgef\u00fchrt wird, kann es auch f\u00fcr unendliche B\u00e4ume durchgef\u00fchrt werden.  Dies ist von besonderem Interesse f\u00fcr die funktionale Programmierung (insbesondere bei verz\u00f6gerter Auswertung), da unendliche Datenstrukturen h\u00e4ufig leicht definiert und bearbeitet werden k\u00f6nnen, obwohl sie nicht (streng) ausgewertet werden, da dies unendlich lange dauern w\u00fcrde.  Einige endliche B\u00e4ume sind zu gro\u00df, um explizit dargestellt zu werden, z. B. der Spielbaum f\u00fcr Schach oder Go. Daher ist es n\u00fctzlich, sie so zu analysieren, als w\u00e4ren sie unendlich.Eine Grundvoraussetzung f\u00fcr das Durchlaufen ist es, jeden Knoten irgendwann zu besuchen.  Bei unendlichen B\u00e4umen scheitern einfache Algorithmen h\u00e4ufig daran.  Wenn beispielsweise ein bin\u00e4rer Baum mit unendlicher Tiefe gegeben ist, wird eine Tiefensuche eine Seite (gem\u00e4\u00df Konvention die linke Seite) des Baums hinuntergehen und niemals den Rest besuchen, und tats\u00e4chlich wird eine Durchquerung in der Reihenfolge oder nach der Reihenfolge niemals stattfinden Besuch irgendein Knoten, da es kein Blatt erreicht hat (und in der Tat nie wird).  Im Gegensatz dazu durchl\u00e4uft eine Durchquerung der Breite zuerst (Ebenenordnung) problemlos einen Bin\u00e4rbaum mit unendlicher Tiefe und tats\u00e4chlich jeden Baum mit begrenztem Verzweigungsfaktor.Bei einem Baum der Tiefe 2, in dem die Wurzel unendlich viele Kinder hat und jedes dieser Kinder zwei Kinder hat, werden bei einer Tiefensuche alle Knoten besucht, sobald die Enkelkinder (Kinder von Kindern von ein Knoten), geht es weiter zum n\u00e4chsten (vorausgesetzt, es ist keine Nachbestellung, in diesem Fall erreicht es nie die Wurzel).  Im Gegensatz dazu wird eine Breitensuche niemals die Enkelkinder erreichen, da sie versucht, die Kinder zuerst zu ersch\u00f6pfen.Eine differenziertere Analyse der Laufzeit kann \u00fcber unendliche Ordnungszahlen erfolgen.  Zum Beispiel wird die Breitensuche des obigen Baums der Tiefe 2 \u03c9 \u00b7 2 Schritte dauern: \u03c9 f\u00fcr die erste Ebene und dann ein weiteres \u03c9 f\u00fcr die zweite Ebene.Einfache Tiefensuchen oder Breitensuchen durchlaufen daher nicht jeden unendlichen Baum und sind bei sehr gro\u00dfen B\u00e4umen nicht effizient.  Hybridmethoden k\u00f6nnen jedoch jeden (z\u00e4hlbar) unendlichen Baum durchlaufen, im Wesentlichen \u00fcber ein diagonales Argument (“Diagonale” – eine Kombination aus vertikal und horizontal – entspricht einer Kombination aus Tiefe und Breite).Konkret bezeichnen Sie angesichts des unendlich verzweigten Baumes von unendlicher Tiefe die Wurzel (), die Kinder der Wurzel (1), (2),\u2026, die Enkelkinder (1, 1), (1, 2),\u2026, (2 , 1), (2, 2), … und so weiter.  Die Knoten befinden sich somit in einer Eins-zu-Eins-Entsprechung mit endlichen (m\u00f6glicherweise leeren) Folgen positiver Zahlen, die z\u00e4hlbar sind und zuerst durch die Summe der Eintr\u00e4ge und dann durch lexikografische Reihenfolge innerhalb einer gegebenen Summe (nur endlich) geordnet werden k\u00f6nnen Viele Sequenzen summieren sich zu einem bestimmten Wert, so dass alle Eintr\u00e4ge erreicht sind – formal gibt es eine endliche Anzahl von Kompositionen einer bestimmten nat\u00fcrlichen Zahl, insbesondere 2n\u22121 Kompositionen von n \u2265 1), was eine Durchquerung ergibt.  Ausdr\u00fccklich:0: ()1: (1)2: (1, 1) (2)3: (1, 1, 1) (1, 2) (2, 1) (3)4: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)etc.Dies kann so interpretiert werden, dass der Bin\u00e4rbaum mit unendlicher Tiefe auf diesen Baum abgebildet und dann die Breitensuche angewendet wird: Ersetzen Sie die “Abw\u00e4rts” -Kanten, die einen \u00fcbergeordneten Knoten mit seinem zweiten und sp\u00e4teren untergeordneten Knoten verbinden, durch “rechte” Kanten vom ersten zum zweiten untergeordneten Knoten Kind, vom zweiten Kind zum dritten Kind usw. Somit kann man bei jedem Schritt entweder nach unten gehen (ein (, 1) an das Ende anh\u00e4ngen) oder nach rechts gehen (eins zur letzten Zahl hinzuf\u00fcgen) (mit Ausnahme der Wurzel, die ist extra und kann nur runter gehen), was die Entsprechung zwischen dem unendlichen Bin\u00e4rbaum und der obigen Nummerierung zeigt;  Die Summe der Eintr\u00e4ge (minus eins) entspricht dem Abstand von der Wurzel, der mit der 2 \u00fcbereinstimmtn\u22121 Knoten in der Tiefe n – 1 im unendlichen Bin\u00e4rbaum (2 entspricht bin\u00e4r).Verweise[edit]AllgemeinesDale, Nell.  Lilly, Susan D. “Pascal Plus Datenstrukturen”.  DC Heath and Company.  Lexington, MA.  1995. Vierte Ausgabe.Drozdek, Adam.  “Datenstrukturen und Algorithmen in C ++”.  Brook \/ Cole.  Pacific Grove, CA.  2001. Zweite Auflage.[2]Externe Links[edit]     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki15\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki15\/2020\/11\/25\/baumdurchquerung-wikipedia\/#breadcrumbitem","name":"Baumdurchquerung – Wikipedia"}}]}]