Anmeldung
Anmelden

Mindmap-Galerie „Datenstruktur“ Kapitel 5 – Baum und Binärbaum

„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:00

tyyii7sc@bccto.c

Aktuelle Werke Weitere Werke anzeigen>>

Welche Preismethoden gibt es für Projektunteraufträge im Rahmen des EPC-Generalvertragsmodells
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.
Wissenspunkte, die Java-Ingenieure in jeder Phase beherrschen müssen
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.
Systemanalytiker – Software-Anforderungsentwicklung
Das Software-Anforderungs-Engineering ist ein Schlüsselkapitel für Systemanalytiker. Zu den Kapiteln „Anforderungserhebung“ und „Anforderungsanalyse“ gehören häufig Veröffentlichungen.

„Datenstruktur“ Kapitel 5 – Baum und Binärbaum

tyyii7sc@bccto.c

Aktuelle Werke Weitere Werke anzeigen>>

Für Sie empfohlen
Gliederung

Datenstruktur
- 3
tyyii7sc@bccto.c

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