Angenommen, ein Binärbaum hat n gewichtete Blattknoten, dann wird die Summe der Pfadlänge vom Wurzelknoten zu jedem Blattknoten und das Produkt des entsprechenden Knotengewichts als gewichtete Pfadlänge WPL (gewichtete Pfadlänge) des Binärbaums bezeichnet . .

Dieselben Blattknoten konstruieren unterschiedliche Binärbäume

Der Binärbaum mit der minimal gewichteten Pfadlänge wird Huffman-Baum (auch optimaler Baum genannt) genannt.

grundsätzlich

Verfahren

Huffman-Kodierung (Präfixkodierung)

left<root<right

Eine verbesserte Version des binären Sortierbaums (ein spezieller binärer Sortierbaum). Versuchen Sie, den Baum so kurz wie möglich zu halten!

Wie erkennt man, ob ein Baum normal wächst?

Binärer Sortierbaum mit Balancefaktor <= 1

Balancieren Sie die maximale Tiefe und die minimale Anzahl von Knoten eines Binärbaums

einfügen

Prolog

mittlerer Ordnung

Nachwort

Zeile für Zeile durchlaufen

Erfordern

Für Fragen mit wenigen Knoten

Die Kernschritte des Prime-Algorithmus sind: In einem gewichteten verbundenen Diagramm ist V eine Menge, die alle Scheitelpunkte enthält. U ist bereits ein Knoten im minimalen Spannbaum, beginnend mit jedem Scheitelpunkt v im Diagramm ={v}, Wiederholen Sie die folgenden Operationen: Finden Sie eine Kante mit dem kleinsten Gewicht unter allen Kanten (u,w)∈E aller u∈U,w∈V-U und fügen Sie die Kante (u,w) zur Menge hinzu Kanten gefunden. Und Punkt w zur Menge U hinzufügen. Wenn U=V, wird der minimale Spannbaum gefunden.

Bestimmen Sie zunächst die Knoten und wählen Sie der Reihe nach diejenigen mit den kürzesten Pfaden aus.

Für Fragen mit wenigen Seiten

Grundidee: kantengeführt. In einem gewichteten zusammenhängenden Graphen ist U die Menge aller Kanten, N die Anzahl der Eckpunkte und SU die Menge der Kanten, die sich bereits im minimalen Spannbaum befinden. Wiederholen Sie die folgenden Vorgänge: Wählen Sie jedes Mal eine Kante e∈U-SU mit dem kleinsten Gewicht und eine Kante aus, die mit den Kanten in SU keinen Kreis bildet, und fügen Sie sie zu SU hinzu. Wenn die Anzahl der Kanten in SU gleich N-1 ist, wird der minimale Spannbaum gefunden.

Die Anzahl der Knoten ohne rechten Zeiger beträgt: Wurzelknoten, Anzahl der Nicht-Blattknoten

Schließen Sie symmetrische aus, zählen Sie die Zahl und stellen Sie sicher, dass links immer weniger und rechts mehr oder links mehr und rechts weniger ist.

Der Wurzelknoten ist eindeutig

Die Anzahl der Teilbäume ist unbegrenzt, sie überschneiden sich jedoch nicht.

Natur

vollständiger Binärbaum

vollständiger Binärbaum

Muss ein vollständiger Binärbaum sein

dagendui

kleiner Wurzelhaufen

Heap-Speicher

Oberer Filter

Nach unten filtern

Wie konvertiere ich ein ungeordnetes Array in einen Heap?

zwei Operationen

Kann mit einem kleinen Root-Heap implementiert werden

Komplexität: O(NlogN)