Mindmap-Galerie „Datenstruktur“ Kapitel 5 – Baum und Binärbaum
Kapitel 5 von „Datenstruktur“ – Sortierung des Wissens über Bäume und Binärbäume, einschließlich der Grundkonzepte von Bäumen, des Konzepts von Binärbäumen, der Durchquerung von Binärbäumen und von Hinweis-Binärbäumen usw.
Bearbeitet um 2022-11-23 16:07:00Welche Preismethoden gibt es für Projektunteraufträge im Rahmen des EPC-Generalvertragsmodells? EPC (Engineering, Procurement, Construction) bedeutet, dass der Generalunternehmer für den gesamten Prozess der Planung, Beschaffung, Konstruktion und Installation des Projekts verantwortlich ist und für die Testbetriebsdienste verantwortlich ist.
Die Wissenspunkte, die Java-Ingenieure in jeder Phase beherrschen müssen, werden ausführlich vorgestellt und das Wissen ist umfassend. Ich hoffe, es kann für alle hilfreich sein.
Das Software-Anforderungs-Engineering ist ein Schlüsselkapitel für Systemanalytiker. Zu den Kapiteln „Anforderungserhebung“ und „Anforderungsanalyse“ gehören häufig Veröffentlichungen.
Welche Preismethoden gibt es für Projektunteraufträge im Rahmen des EPC-Generalvertragsmodells? EPC (Engineering, Procurement, Construction) bedeutet, dass der Generalunternehmer für den gesamten Prozess der Planung, Beschaffung, Konstruktion und Installation des Projekts verantwortlich ist und für die Testbetriebsdienste verantwortlich ist.
Die Wissenspunkte, die Java-Ingenieure in jeder Phase beherrschen müssen, werden ausführlich vorgestellt und das Wissen ist umfassend. Ich hoffe, es kann für alle hilfreich sein.
Das Software-Anforderungs-Engineering ist ein Schlüsselkapitel für Systemanalytiker. Zu den Kapiteln „Anforderungserhebung“ und „Anforderungsanalyse“ gehören häufig Veröffentlichungen.
Zahlen und Binärbäume
Grundbegriffe von Bäumen
Definition
Ein Baum ist eine endliche Menge von n Knoten. Ein nicht leerer Baum sollte Folgendes erfüllen:
Es gibt nur einen Wurzelknoten
Wenn n>1 ist, können die verbleibenden Knoten in m disjunkte endliche Mengen Ti unterteilt werden, wobei jede Menge ein Teilbaum der Wurzel ist.
Grundbegriffe
Vorfahren, Nachkommen, Eltern, Kinder, Brüder
Grad: die Anzahl der Kinder des Knotens
Der maximale Grad eines Knotens wird als Baumgrad bezeichnet
Blattknoten (Endknoten), Zweigknoten (Nicht-Endknoten)
Die Summe der Knotengrade des Baums = die Summe der Anzahl der Zweige = die Anzahl der Knoten – 1
Tiefe: ausgehend vom Wurzelknoten und akkumulierend Schicht für Schicht von oben nach unten.
Höhe: beginnend am Blattknoten und akkumulierend Schicht für Schicht von unten nach oben.
Geordneter Baum, ungeordneter Baum
Pfad, Pfadlänge
Wald: eine Sammlung von m disjunkten Bäumen
Natur
Die Anzahl der Knoten im Baum = die Summe der Grade aller Knoten 1
Es gibt höchstens m^(i-1) Knoten auf der i-ten Ebene eines Baums vom Grad m.
Ein m-ärer Baum mit der Höhe h hat höchstens (m^h-1)/(m-1) Knoten.
Die minimale Höhe eines m-ären Baums mit n Knoten beträgt:
Binärbaumkonzept
Definition und Eigenschaften
Definition: Jeder Knoten hat höchstens zwei Teilbäume, und die Teilbäume können in linke und rechte Teilbäume unterteilt werden.
spezieller Binärbaum
vollständiger Binärbaum
Die Höhe beträgt h und die Anzahl der Knoten beträgt 2^h-1
Für den Knoten mit der Nummer i
Eltern:
Linkes Kind: 2i
Rechtes Kind: 2i 1
vollständiger Binärbaum
Die Anzahl jedes Knotens entspricht einem vollständigen Binärbaum (d. h. nur der Blattknoten rechts ist leer).
Natur
①Wenn i≤Ln/2", dann ist Knoten i ein Verzweigungsknoten, andernfalls ist er ein Blattknoten.
②Blattknoten können nur auf den beiden größten Ebenen erscheinen. Die Blattknoten in der größten Ebene sind der Reihe nach an der äußersten linken Position der Ebene angeordnet.
③Wenn es einen Knoten mit Grad 1 gibt, kann es nur einen geben, und der Knoten hat nur linke Kinder, aber keine rechten Kinder.
④Nach der Nummerierung in hierarchischer Reihenfolge ist die Nummer größer als i, sobald ein Knoten (mit der Nummer i) als Blattknoten erscheint oder nur ein linkes untergeordnetes Element hat Die Knoten sind alle Blattknoten.
⑤ Wenn n eine ungerade Zahl ist, hat jeder Zweigknoten ein linkes und ein rechtes Kind. Wenn r eine gerade Zahl ist, hat der Zweigknoten mit der größten Zahl (Nummer n/2) nur ein linkes Kind und kein rechtes Kind , und die anderen Zweigknoten haben Es gibt Kinder, die nach links und rechts klicken.
⑥Die Höhe eines vollständigen Binärbaums mit n Knoten beträgt:
Binärer Sortierbaum
Schlüsselwort des linken Teilbaums<Wurzelknoten<rechter Teilbaum
Der linke und der rechte Teilbaum sind jeweils ein binärer Sortierbaum.
ausgeglichener Binärbaum
Der Tiefenunterschied zwischen dem linken Teilbaum und dem rechten Teilbaum eines Knotens im Baum überschreitet nicht 1
Eigenschaften von Binärbäumen
Die Anzahl der Blattknoten in einem nicht leeren Binärbaum = die Anzahl der Knoten mit Grad 2 1, d. h. n0=n2 1
Es gibt höchstens 2^(k-1) Knoten auf der k-ten Ebene eines nicht leeren Binärbaums.
Ein Binärbaum der Höhe h hat höchstens 2^h-1 Knoten.
Binäre Baumspeicherstruktur
Sequentielle Speicherstruktur
Kettenspeicherstruktur
Binärbaumdurchquerung und Hinweis auf Binärbäume
Durchquerung eines Binärbaums
Vorbestellungsdurchquerung (NLR)
In-Order-Traversal (LNR)
Postorder-Traversal (LRN)
Rekursiver Algorithmus → nicht rekursiv (mit Hilfe von Stack)
Nicht rekursiver Algorithmus für die Durchquerung in der Reihenfolge
Leveldurchquerung (mit Hilfe von Warteschlangen)
Konstruieren Sie einen Binärbaum aus einer Traversierungssequenz
Ein Binärbaum kann durch seine Vorbestellungs- (oder Nachbestellungs-)Sequenz und Inorder-Sequenz eindeutig bestimmt werden.
Der erste Knoten der Vorbestellungssequenz muss der Wurzelknoten sein, und der Wurzelknoten unterteilt die Inorder-Sequenz in zwei Sequenzen: den linken und den rechten Teilbaum.
Suchen Sie den linken und rechten Teilbaum in der Vorbestellung entsprechend dem linken und rechten Teilbaum in der Inorder und wiederholen Sie die obigen Schritte rekursiv.
Ein Binärbaum kann durch seine hierarchische Reihenfolge und In-Order-Sequenz eindeutig bestimmt werden.
Anhand der Vorbestellungs- und Nachbestellungssequenzen des Binärbaums kann die Ahnenbeziehung einiger Knoten bestimmt werden: Wenn die Vorbestellung aX und die Nachbestellung Xa ist, dann sind die Knoten in der Menge vorhanden Brüder, die Reihenfolge sollte konsistent sein, das heißt, der linke Bruder steht an erster Stelle)
Hinweis Binärbaum
Konzept
Konstruieren Sie einen geordneten Hinweis-Binärbaum
Hinweis-Binärbaum mit führendem Knoten
Durchquerung binärer Bäume mit Inorder-Hinweisen
Suchen Sie den ersten Knoten unter der Inorder-Sequenz im Inorder-Hinweis-Binärbaum
Suchen Sie den Nachfolger von Knoten p im In-Order-Clue-Binärbaum unter der In-Order-Sequenz
In-Order-Traversal-Algorithmus für In-Order-Clued-Binärbäume ohne Kopfknoten
Hinweis-Binärbaum vorbestellen und Hinweis-Binärbaum nachbestellen
Finden Sie den Knotennachfolger im Vorbestellungshinweis-Binärbaum
Wenn ein Kind übrig bleibt, wird es sein Nachfolger
Gibt es kein linkes, aber ein rechtes Kind, wird das zweite Kind zum Nachfolger.
Andernfalls zeigt die rechte Kettendomäne auf den Nachfolger
Finden des Nachfolgers eines Knotens in einem Binärbaum mithilfe von Postorder-Hinweisen
Wenn x die Wurzel eines Binärbaums ist, ist der Nachfolger leer
Wenn x das rechte Kind beider Elternteile oder das linke Kind beider Elternteile ist und die Eltern keine Nachkommen haben, dann sind seine Eltern der Nachfolger
Wenn x das linke Kind des Elternteils ist und das Elternteil ein rechtes Kind hat, ist der Nachfolger der erste Knoten, der in der absteigenden Reihenfolge des Durchlaufs im rechten Teilbaum des Elternteils aufgeführt ist.
Anwendungen von Bäumen und Binärbäumen
Huffman-Bäume und Huffman-Codierung
Definition
Gewichtete Pfadlänge: Das Produkt aus der Pfadlänge (Anzahl der durchlaufenen Kanten) von der Wurzel des Baums zu einem beliebigen Knoten und der Gewichtung des Knotens
Die gewichtete Pfadlänge des Baums: die Summe der gewichteten Pfadlängen aller Blattknoten im Baum
Huffman-Baum: Unter den Binärbäumen mit n gewichteten Blattknoten wird der Binärbaum mit der kleinsten gewichteten Pfadlänge (WPL) auch als optimaler Binärbaum bezeichnet.
Die Struktur des Huffman-Baums
Konstruktionsprozess
Bei n Knoten mit den Gewichten w1, w2,...,wn wird der Algorithmus zum Aufbau eines Huffman-Baums wie folgt beschrieben:
1) Behandeln Sie diese n Knoten als n binäre Bäume, die nur einen Knoten enthalten, um einen Wald F zu bilden.
2) Erstellen Sie einen neuen Knoten, wählen Sie die beiden Bäume mit den kleinsten Wurzelknotengewichten aus F als linken und rechten Teilbaum des neuen Knotens aus und legen Sie die Gewichte des neuen Knotens auf die Wurzeln des linken und rechten Teilbaums fest der Knotengewichte.
3) Löschen Sie die beiden gerade ausgewählten Bäume aus F und fügen Sie die neu erhaltenen Bäume zu F hinzu.
4) Wiederholen Sie die Schritte 2) und 3), bis in F nur noch ein Baum übrig ist.
Merkmale
1) Jeder Anfangsknoten wird schließlich zu einem Blattknoten. Je kleiner das Gewicht, desto größer die Pfadlänge vom Knoten zum Wurzelknoten.
2) Während des Konstruktionsprozesses werden insgesamt n-1 neue Knoten (Doppelzweigknoten) erstellt, sodass die Gesamtzahl der Knoten des Huffman-Baums 2n-1 beträgt.
3) Jede Konstruktion wählt 2 Bäume als Kinder des neuen Knotens aus, sodass es im Huffman-Baum keinen Knoten mit Grad 1 gibt.
Huffman-Codierung
Codierung mit variabler Länge
Unterschiedliche Zeichen werden durch Binärbits unterschiedlicher Länge dargestellt; Zeichen mit niedriger Häufigkeit werden längere Codes zugewiesen, Zeichen mit hoher Häufigkeit werden kürzere Codes zugewiesen.
Präfixkodierung
Keine Kodierung ist ein Präfix einer anderen, daher ist die Dekodierung sehr einfach
Bei der Huffman-Kodierung handelt es sich um eine Datenkomprimierungskodierung, die unter Verwendung einer Kodierung mit variabler Länge und Präfixen entwickelt wurde.
Huffman-Baum→Huffman-Codierung
1) Behandeln Sie jedes erscheinende Zeichen als unabhängigen Knoten, dessen Gewicht der Häufigkeit des Auftretens (Anzahl) entspricht, und erstellen Sie den entsprechenden Huffman-Baum
2) Interpretieren Sie die Kodierung eines Zeichens als eine Folge von Kantenmarkierungen auf dem Pfad von der Wurzel zum Zeichen, wobei eine Kantenmarkierung von 0 „zum linken Kind wenden“ und eine Kantenmarkierung von 1 „zum linken Kind wenden“ bedeutet richtiges Kind“
Und durchsuchen Sie die Sammlung
Die Grundidee
Normalerweise wird die übergeordnete Darstellung eines Baums (Wald) als Speicherstruktur der Union-Find-Menge verwendet, und jede Teilmenge wird durch einen Baum dargestellt. Alle Bäume, die Teilmengen darstellen, bilden einen Wald, der die gesamte Menge darstellt, und werden im übergeordneten Darstellungsarray gespeichert. Normalerweise wird der Index des Array-Elements verwendet, um den Elementnamen darzustellen, und der Index des Wurzelknotens wird verwendet, um den Namen der Untersammlung darzustellen. Der übergeordnete Knoten des Wurzelknotens ist eine negative Zahl.
arbeiten
1) Initial(S): Initialisieren Sie jedes Element in der Menge s zu einer Teilmenge mit nur einem einzigen Element.
2) Union(S, Root1, Root2): Füge die Teilmenge Root2 in der Menge S mit der Teilmenge Root1 zusammen. Erfordern Root1 und Root2 sind voneinander disjunkt, andernfalls wird die Zusammenführung nicht durchgeführt.
3) Find(S,x): Suchen Sie die Teilmenge, in der sich das einzelne Element x in der Menge s befindet, und geben Sie den Wurzelknoten der Teilmenge zurück.
Baum, Wald
Baumspeicherstruktur
Elternvertretung
Zum Speichern von Knoten wird eine Reihe kontinuierlicher Leerzeichen verwendet. Gleichzeitig wird jedem Knoten ein Pseudozeiger hinzugefügt, um den Standort der übergeordneten Knoten anzuzeigen.
Sie können die übergeordneten Knoten eines Knotens schnell abrufen, müssen jedoch das Array durchlaufen, um die untergeordneten Knoten des Knotens zu finden.
Kindervertretung
Verbinden Sie die untergeordneten Knoten jedes Knotens mit einer einzelnen verknüpften Liste. n Knoten entsprechen n verknüpften Listen
Das Finden von Kindern ist einfach, aber das Finden von Eltern erfordert das Durchlaufen von n verknüpften Listen
Darstellung des Kindesbruders (Binärbaumdarstellung)
Verwendung einer binär verknüpften Liste als Speicherstruktur des Baums
Knoten
Knotenwert
Zeiger auf das erste untergeordnete Element des Knotens
Zeiger auf den nächsten Geschwisterknoten des Knotens
Es ist einfach, untergeordnete Knoten zu finden, aber es ist schwieriger, übergeordnete Knoten zu finden (ein übergeordneter Zeiger kann hinzugefügt werden).
Umwandlung von Bäumen, Wäldern und Binärbäumen
Baum ↔ Binärbaum
Unter Verwendung einer binär verknüpften Liste als Medium gibt es für jeden Baum einen eindeutigen Binärbaum (und umgekehrt).
Umrechnungsregel: „Linkes Kind, rechter Bruder“
Root-First-Traversal-Sequenz: ABEFCDG
Post-Root-Traversal-Sequenz: EFBCGDA
Wald ↔ Binärbaum
Ähnlich wie bei der obigen Konvertierung wird jeder Baum zunächst in einen Binärbaum umgewandelt, und dann wird die Wurzel des n-ten Baums als das rechte Geschwister der Wurzel des n-ten Baums betrachtet.
Sequenzdurchlauf vorbestellen: ABCDEFGHI
Durchlaufsequenz in der richtigen Reihenfolge: BCDAFEHIG
Baum- und Walddurchquerung
Baumdurchquerung
Zuerst Root-Traversierung
Besuchen Sie zuerst den Wurzelknoten und dann nacheinander jeden Unterbaum
Die Durchlaufsequenz ist dieselbe wie die Vorbestellungssequenz des entsprechenden Binärbaums
Back-Root-Traversal
Besuchen Sie zunächst nacheinander jeden Teilbaum und dann den Wurzelknoten
Die Durchlaufsequenz ist dieselbe wie die In-Order-Sequenz des entsprechenden Binärbaums
Leveldurchquerung
Unterwegs durch den Wald
Durchquerung vorbestellen
Besuchen Sie den Wurzelknoten des ersten Baums im Wald
Durchlaufen Sie vorab den Teilbaumwald des Wurzelknotens im ersten Baum
Vorbestellung: Durchqueren Sie den verbleibenden Wald, nachdem Sie den ersten Baum entfernt haben
Inorder-Durchquerung
Beim Durchlaufen in der Reihenfolge wird der Teilbaumwald des Wurzelknotens des ersten Baums im Wald durchquert.
Besuchen Sie den Wurzelknoten des ersten Baums
Nach dem Entfernen des ersten Baumes wird der Wald, der aus den verbleibenden Bäumen besteht, in der richtigen Reihenfolge durchquert