Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Dieser Artikel beginnt mit den Konzepten im Zusammenhang mit Bäumen und Binärbäumen, um uns dabei zu helfen, mehr über Binärbäume zu erfahren.

🌈个人主页：Es ist der Kellner
🌈C语言笔记专栏：Hinweise zur C-Sprache
🌈C++笔记专栏： C++-Hinweise
🌈初阶数据结构笔记专栏： Hinweise zur elementaren Datenstruktur

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅

1. Baumkonzept und -struktur

Baum ist eine nichtlineare Datenstruktur, bestehend ausn(n>=0)Begrenzte Knoten bilden eine Menge mit einer hierarchischen Beziehung. Der Baum ist jedoch in der Praxis von geringem Wert, aber der Binärbaum hat einen größeren praktischen Wert (der Grund, warum diese Menge als Baum bezeichnet wird, liegt darin, dass die Wurzel nach oben zeigt und die Blätter nach oben zeigen). nach unten gerichtet. Es sieht aus wie ein Baum.

• Es gibt einen speziellen Knoten, der Wurzelknoten genannt wird. Der Wurzelknoten hat keine Vorgängerknoten.
• Mit Ausnahme des Wurzelknotens sind die übrigen Knoten unterteiltM(M>0)disjunkte MengenT1、T2、....、Tm, jeder Satz davonTi(1<=i<=m) Es handelt sich um einen weiteren Teilbaum mit einer baumähnlichen Struktur. Der Wurzelknoten jedes Teilbaums hat genau einen Vorgänger und kann 0 oder mehr Nachfolger haben.
• Bäume werden rekursiv definiert, und gleichzeitig ist Vorsicht geboten.in BaumstrukturEs darf keine Schnittmenge zwischen Teilbäumen geben, sonst entsteht keine Baumstruktur

1.1 Verwandte Konzepte von Bäumen

• Grad des Knotens: Die Anzahl der in einem Knoten enthaltenen Teilbäume wird als Grad des Knotens bezeichnet, wie in der Abbildung oben gezeigt: A ist 6
• Blattknoten oder Endknoten: Knoten mit Grad 0 werden als Blattknoten bezeichnet. Wie in der Abbildung oben gezeigt: Knoten wie B, C, H, I ... sind Blattknoten.
• Nichtterminaler Knoten oder Verzweigungsknoten: Ein Knoten, dessen Grad nicht 0 ist; Wie in der Abbildung oben gezeigt: Knoten wie D, E, F, G ... sind Verzweigungsknoten.
• Übergeordneter Knoten oder übergeordneter Knoten: Wenn ein Knoten untergeordnete Knoten enthält, wird dieser Knoten als übergeordneter Knoten seines untergeordneten Knotens bezeichnet. Wie in der Abbildung oben gezeigt: A ist der übergeordnete Knoten von B
• untergeordneter Knoten oder untergeordneter Knoten: Der Wurzelknoten des in einem Knoten enthaltenen Teilbaums wird als untergeordneter Knoten des Knotens bezeichnet. Wie in der Abbildung oben gezeigt: B ist der untergeordnete Knoten von A
• Geschwisterknoten: Knoten mit demselben übergeordneten Knoten werden wie oben gezeigt als Geschwisterknoten bezeichnet: B und C sind Geschwisterknoten.
• Grad des Baumes: In einem Baum wird der Grad des größten Knotens als Baumgrad bezeichnet, wie oben gezeigt: Der Baumgrad beträgt 6
• Knotenebene: Ausgehend von der Definition der Wurzel ist die Wurzel die erste Ebene, die untergeordneten Knoten der Wurzel sind die zweite Ebene und so weiter.
• Höhe oder Tiefe des Baumes: Die maximale Knotenebene im Baum, wie oben gezeigt: Die Höhe des Baums beträgt 4
• Cousin-Knoten: Knoten, deren Eltern auf derselben Ebene liegen, sind Cousins ​​voneinander, wie in der Abbildung oben gezeigt: H und I sind Bruderknoten voneinander.
• Vorfahr des Knotens: Alle Knoten auf den Zweigen von der Wurzel bis zum Knoten, wie in der Abbildung oben gezeigt: A ist der Vorfahre aller Knoten
• Nachkommenschaft : Jeder Knoten im Unterbaum, der an einem bestimmten Knoten wurzelt, wird als Nachkomme dieses Knotens bezeichnet.Wie oben gezeigt: Alle Knoten sind Nachkommen von A
• Wald: Eine Menge von m (m>0) disjunkten Bäumen wird Wald genannt.

2. Speicherdarstellung des Baumes

Da die Baumstruktur komplexer ist als die lineare Tabelle, ist die Speichermethode problematischer. Es ist erforderlich, sowohl den Wertebereich als auch die Beziehung zwischen den Knoten zu speichern.

Hier sind mehrere Methoden, die auf Vorkenntnissen basieren:

• Jedes Kind hat eine Adresse und kann Daten über ein Zeiger-Array speichern (der Speicherplatz ist fest, und bei der Beantragung eines neuen Speicherplatzes treten Kosten und Platzprobleme auf).
• Zur Optimierung der ersten Methode wird das Zeiger-Array als Sequenztabelle zum Speichern von untergeordneten Elementen verwendet, wodurch das Problem des festen Speicherplatzes gelöst wird.
• Empfohlene häufig verwendete Lösung: Methode des linken Kindes und des rechten Bruders (der älteste Bruder nimmt das zweite Kind und das zweite Kind das dritte Kind, sodass beide Elternteile nicht müde sein müssen)

typedef int DataType;
struct Node
{
    struct Node* _firstChild1; // 第一个孩子结点
    struct Node* _pNextBrother; // 指向其下一个兄弟结点
    DataType _data; // 结点中的数据域
};
1
2
3
4
5
6
7

Natürlich sind die oben genannten Methoden nicht eingeschränkt, es gibt auch übergeordnete Ausdrücke, untergeordnete Ausdrücke, untergeordnete Elternausdrücke und untergeordnete Bruderausdrücke usw.Hier werden wir kurz die am häufigsten verwendeten verstehenVertretung des Kindesbruders

3. Binärbaumkonzept

Ein Binärbaum ist eine endliche Menge von Knoten. Diese Menge kann zwei Situationen haben:

1. leerer Baum
2. Es besteht aus einem Wurzelknoten und zwei Binärbäumen, die als linker Teilbaum und rechter Teilbaum bezeichnet werden (der Teilbaum kann ein leerer Baum sein).

Aus der Abbildung lassen sich zwei Schlussfolgerungen ziehen:

1. In einem Binärbaum gibt es keinen Knoten mit einem Grad größer als 2

2. Die Teilbäume eines Binärbaums können in linke und rechte Teilbäume unterteilt werden, und die Reihenfolge kann nicht umgekehrt werden, sodass der Binärbaum ein geordneter Baum ist.

Beachten: Für jeden Binärbaum besteht er aus den folgenden Situationen (Die Situation mit einem leeren Baum vergisst man am leichtesten)

3.1 Binärbaum in Wirklichkeit (man muss sich mehrmals verbeugen, wenn man ihn sieht)

4. Spezieller Binärbaum

• vollständiger Binärbaum :Ein Binärbaum ist ein vollständiger Binärbaum, wenn die Anzahl der Knoten in jeder Schicht das Maximum erreicht. Mit anderen Worten, die Ebene eines Binärbaums ist K und die Gesamtzahl der Knoten beträgt 2^K-1, dann handelt es sich um einen vollständigen Binärbaum
• vollständiger Binärbaum : Ein vollständiger Binärbaum ist eine sehr effiziente Datenstruktur. Ein vollständiger Binärbaum wird aus einem vollständigen Binärbaum abgeleitet. Ein Binärbaum mit der Höhe K und n Knoten wird genau dann als vollständiger Binärbaum bezeichnet, wenn jeder Knoten eins zu eins mit den von 1 bis n nummerierten Knoten im vollständigen Binärbaum mit der Höhe K übereinstimmt.

Um es kurz zusammenzufassen:

• Jede Ebene eines vollständigen Binärbaums ist voll

• Wenn die Höhe eines vollständigen Binärbaums n beträgt, sind die ersten n-1 Ebenen voll, die letzte Ebene jedoch möglicherweise nicht.Aber es muss von links nach rechts durchgehend sein

• Ein vollständiger Binärbaum ist eine sehr effiziente Datenstruktur, und ein vollständiger Binärbaum ist eine spezielle Art eines vollständigen Binärbaums.

• Ein vollständiger Binärbaum ist eine notwendige und hinreichende Bedingung für einen vollständigen Binärbaum

4.1 Situationen, die nicht zu einem vollständigen Binärbaum gehören

Dies ist ein gewöhnlicher Binärbaum, der nicht von links nach rechts kontinuierlich ist.

5. Speicherstruktur des Binärbaums

Binärbäume können im Allgemeinen in zwei Strukturen gespeichert werden, eine ist eine sequentielle Struktur und die andere ist eine Kettenstruktur.

5.1 Sequentielle Speicherung

Bei der sequentiellen Strukturspeicherung werden Arrays zum Speichern verwendet.Generell eignen sich Arrays nur zur Darstellung vollständiger Binärbäume. , denn wenn der Binärbaum nicht voll ist, wird Speicherplatz verschwendet. In Wirklichkeit verwendet nur der Heap Arrays zur Speicherung. Die sequentielle Speicherung eines Binärbaums ist physikalisch ein Array und logisch ein Binärbaum. Um die nächste Frage zu lösen, müssen wir die Kombination aus dem physischen Array und dem logischen Binärbaum verwenden, um eine Frage zu lösen.

5.2 Regelmäßige Indexbeziehung zwischen übergeordneten und untergeordneten Knoten (wichtig)

• leftchild = parent * 2 + 1;

• rightchild = paretn * 2 +2;

• parent = (child - 1) / 2;(Unterscheidet nicht zwischen linken und rechten Kindern)

• Zum dritten Punkt, basierend auf persönlichen Überlegungen,leftchildDer Index ist aufgeteilt inleftchild- 1Und1,fürleftchild-1fürparentzweimal tiefgestellt, z(child - 1) / 2Der Betreiber wirdleftchildNehmen Sie es heraus als1Teilweise durch 2 dividiert, ist die ganze Zahl 0,leftchild -1Ein Teil davon kann als angesehen werdenleftchild,Undrightchild与leftchild相差1,Weilrightchild = leftchild - 1und durch obenleftchild - 1 ~= leftchild, daraus lässt sich schließenrightchild = leftchild(在进行/2运算，取整数情况下)

5.3 Kettenlagerung

Die verknüpfte Speicherstruktur eines Binärbaums bezieht sich auf die Verwendung einer verknüpften Liste zur Darstellung eines Binärbaums, dh die Verwendung einer Kette zur Angabe der logischen Beziehung von Elementen. Die übliche Methode besteht darin, dass jeder Knoten in der verknüpften Liste aus drei Feldern besteht, dem Datenfeld und den linken und rechten Zeigerfeldern. Die linken und rechten Zeiger werden verwendet, um die Speicheradressen der Verknüpfungspunkte anzugeben, an denen sich das linke und rechte Kind befinden des Knotens liegen jeweils.Kettenstrukturen werden in Binärketten und Dreifachketten unterteilt. Derzeit verwenden wir in unseren Studien im Allgemeinen Binärketten. Wenn wir später Datenstrukturen höherer Ordnung wie Rot-Schwarz-Bäume lernen, werden Dreifachketten verwendet.

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
        struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.4 Zusammenfassung

Der sequentielle Strukturspeicher wird über Arrays gespeichert.Im Allgemeinen eignen sich Arrays nur für vollständige Binärbäume. Nicht vollständige Binärbäume eignen sich nicht für die Speicherung von Array-Strukturen. Gewöhnliche Binärbäume eignen sich nur für die Speicherung von Kettenstrukturen. . In Wirklichkeit werden Arrays jedoch nur dann zur Speicherung verwendet, wenn Heaps verwendet werden, und die meisten davon werden über Kettenstrukturen gespeichert.

der Grund ist:

1. Zunächst müssen wir wissen, dass der Binärbaum eine eigene spezielle logische Struktur hat. Er unterscheidet sich von anderen Datenstrukturen und eignet sich zum Hinzufügen, Löschen, Überprüfen und Ändern von Heap-Daten, da er viel Platz und Logik verbraucht ist komplexer.Wenn eine so komplexe Struktur zum Speichern von Daten verwendet wird, ist sie nicht ohne großen Wert. , wäre es besser, eine sequentielle Tabelle zu verwenden, um Daten von Anfang an zu speichern. Gleichzeitig ist die Struktur eines Binärbaums im Allgemeinen rekursiv und es ist schwieriger, sie nicht rekursiv zu implementieren.
2. Die Dichte der Speicherelemente in einem gewöhnlichen Binärbaum kann sehr gering sein, und die kontinuierliche Speicherstruktur führt zu einer großen Platzverschwendung.
3. Der Heap wird nach dem „Heap-Attribut“ sortiert, das die Position des Knotens im Baum bestimmt (erläutert in der Einführung des Heaps unten).

---

Das Obige ist der gesamte Inhalt dieses Artikels. Vielen Dank an alle fürs Lesen! Hier sind Dian Xiaoers Anmerkungen zu elementaren Datenstrukturen. Ich hoffe, sie werden Ihnen beim Erlernen elementarer Datenstrukturen hilfreich sein!