Teil 3 ist hier
Bisher habe ich den Umriss des gegabelten Baumes erklärt. Ab diesem Zeitpunkt werde ich ein konkretes Beispiel für einen dichotomisierten Baum erläutern. Das erste Beispiel ist ein dichotomisierter Baum, der als binärer Heap bezeichnet wird. Die Struktur ist einfach, es ist nur eine vollständige Zweiteilung, bei der die übergeordneten Daten immer kleiner als die untergeordneten Daten sind. Ein vollständig gegabelter Baum war ein gegabelter Baum ohne Leerzeichen an den Knoten, die keine Blätter waren, und alle Blätter waren linksbündig. Da der dichotomisierte Heap eine Art vollständiger dichotomisierter Baum ist, kann er unter Verwendung eines Arrays realisiert werden.
C++
BinaryHeap.cpp
#include <iostream>
using namespace std;
void breadthFirstSearch(int binaryTree[], int nodeNum);
int insertNode(int binaryHeap[], int value, int nodeNum);
int deleteNode(int binaryHeap[], int value, int nodeNum);
int searchNode(int binaryHeap[], int value, int nodeNum, int index);
//Funktion zur Anzeige in der Reihenfolge der Suche nach Breitenpriorität
void breadthFirstSearch(int binaryTree[], int nodeNum)
{
for (int i = 0; i < nodeNum; i++) {
cout << binaryTree[i] << " ";
}
cout << endl;
}
//Eine Funktion, die einen neuen Knoten in den Dichotomie-Heap einfügt
//Gibt bei Erfolg 1 und bei Misserfolg 0 zurück
int insertNode(int binaryHeap[], int value, int nodeNum)
{
//Tun Sie nichts, wenn es bereits Wert gibt
if (searchNode(binaryHeap, value, nodeNum, 0) != -1) {
return 0;
}
//Am Ende vorübergehend eingefügt
binaryHeap[nodeNum] = value;
int i = nodeNum;
//Folgen Sie vom Ende bis zur Wurzel
while (i > 0) {
//Wenn der Elternteil größer ist
if (binaryHeap[i] < binaryHeap[(i - 1) / 2]) {
//Kind mit Eltern austauschen
binaryHeap[i] = binaryHeap[(i - 1) / 2];
binaryHeap[(i - 1) / 2] = value;
i = (i - 1) / 2;
}
//Wenn der Elternteil kleiner ist
else {
return 1;
}
}
return 1;
}
//Eine Funktion, die Knoten mit Wert in den Daten aus dem Dichotomie-Heap entfernt
//Gibt bei Erfolg 1 und bei Misserfolg 0 zurück
int deleteNode(int binaryHeap[], int value, int nodeNum)
{
int index = searchNode(binaryHeap, value, nodeNum, 0);
//Tun Sie nichts, wenn in binaryHeap kein Wert vorhanden ist
if (index == -1) {
return 0;
}
//Verschieben Sie die letzten Daten vorübergehend
binaryHeap[index] = binaryHeap[nodeNum - 1];
// binaryHeap[index]Schleife solange es Kinder gibt
//Beachten Sie, dass die Gesamtzahl der Knoten um eins reduziert wurde.
while (2 * index + 1 < nodeNum - 1) {
int childIndex, childValue;
//Wenn es nur das linke Kind gibt
if (2 * index + 1 == nodeNum - 2) {
childIndex = 2 * index + 1;
childValue = binaryHeap[2 * index + 1];
}
//Wenn Sie linke und rechte Kinder haben
else {
//Wenn das Kind links kleiner ist
if (binaryHeap[2 * index + 1] <= binaryHeap[2 * index + 2]) {
childIndex = 2 * index + 1;
childValue = binaryHeap[2 * index + 1];
}
//Wenn das richtige Kind kleiner ist
else {
childIndex = 2 * index + 2;
childValue = binaryHeap[2 * index + 2];
}
}
//Vergleichen Sie Ihre aktuelle Position mit dem kleineren Kind
//Wenn die aktuelle Position größer ist
if (binaryHeap[index] > childValue) {
//Tauschen Sie die aktuelle Position und das Kind aus
binaryHeap[childIndex] = binaryHeap[index];
binaryHeap[index] = childValue;
index = childIndex;
}
//Wenn das Kind größer ist
else {
return 1;
}
}
return 1;
}
//Eine Funktion, die den dichotomisierten Heap nach Knoten durchsucht, deren Daten einen Wert haben
//Index des Knotens, wenn erfolgreich, wenn nicht erfolgreich-Rückgabe 1
int searchNode(int binaryHeap[], int value, int nodeNum, int index)
{
//Tun Sie nichts, wenn die Anzahl der Knoten 0 ist
if (nodeNum == 0) {
return -1;
}
//Scannen Sie in der Reihenfolge des Ziels
//Erfolgreiche Suche
if (binaryHeap[index] == value) {
return index;
}
//Suchfehler
else if (binaryHeap[index] > value) {
return -1;
}
//Weiter so
else {
int leftResult = -1, rightResult = -1;
if (2 * index + 1 < nodeNum) {
leftResult = searchNode(binaryHeap, value, nodeNum, 2 * index + 1);
}
if (2 * index + 2 < nodeNum) {
rightResult = searchNode(binaryHeap, value, nodeNum, 2 * index + 2);
}
if (leftResult == -1 && rightResult == -1) {
return -1;
}
else if (leftResult != -1) {
return leftResult;
}
else {
return rightResult;
}
}
}
int main()
{
int binaryHeap[100];
int nodeNum = 0;
nodeNum += insertNode(binaryHeap, 8, nodeNum);
nodeNum += insertNode(binaryHeap, 12, nodeNum);
nodeNum += insertNode(binaryHeap, 19, nodeNum);
nodeNum += insertNode(binaryHeap, 9, nodeNum);
nodeNum += insertNode(binaryHeap, 4, nodeNum);
nodeNum += insertNode(binaryHeap, 21, nodeNum);
nodeNum += insertNode(binaryHeap, 2, nodeNum);
nodeNum += insertNode(binaryHeap, 14, nodeNum);
//Keine doppelte Einfügung zulassen
nodeNum += insertNode(binaryHeap, 14, nodeNum);
breadthFirstSearch(binaryHeap, nodeNum);
cout << "nodeNum: " << nodeNum << endl;
int index = searchNode(binaryHeap, 14, nodeNum, 0);
cout << "index: " << index << ", value: " << binaryHeap[14] << endl;
//Wenn Sie nach einem Knoten suchen, der nicht vorhanden ist-1 ist zurück
index = searchNode(binaryHeap, 1, nodeNum, 0);
cout << "index: " << index << endl;
nodeNum -= deleteNode(binaryHeap, 14, nodeNum);
nodeNum -= deleteNode(binaryHeap, 2, nodeNum);
nodeNum -= deleteNode(binaryHeap, 21, nodeNum);
//Sie können nicht löschen, was Sie nicht haben
nodeNum -= deleteNode(binaryHeap, 14, nodeNum);
breadthFirstSearch(binaryHeap, nodeNum);
cout << "nodeNum: " << nodeNum << endl;
}
Java
BinaryHeap.java
public class BinaryHeapAnswer {
//Funktion zur Anzeige in der Reihenfolge der Suche nach Breitenpriorität
public static void breadthFirstSearch(int[] binaryTree, int nodeNum) {
for (int i = 0; i < nodeNum; i++) {
System.out.print(binaryTree[i] + " ");
}
System.out.println("");
}
//Eine Funktion, die einen neuen Knoten in den Dichotomie-Heap einfügt
//Gibt bei Erfolg 1 und bei Misserfolg 0 zurück
public static int insertNode(int[] binaryHeap, int value, int nodeNum) {
//Tun Sie nichts, wenn es bereits Wert gibt
if (searchNode(binaryHeap, value, nodeNum, 0) != -1) {
return 0;
}
//Am Ende vorübergehend eingefügt
binaryHeap[nodeNum] = value;
int i = nodeNum;
//Folgen Sie vom Ende bis zur Wurzel
while (i > 0) {
//Wenn der Elternteil größer ist
if (binaryHeap[i] < binaryHeap[(i - 1) / 2]) {
//Kind mit Eltern austauschen
binaryHeap[i] = binaryHeap[(i - 1) / 2];
binaryHeap[(i - 1) / 2] = value;
i = (i - 1) / 2;
}
//Wenn der Elternteil kleiner ist
else {
return 1;
}
}
return 1;
}
//Eine Funktion, die Knoten mit Wert in den Daten aus dem Dichotomie-Heap entfernt
//Gibt bei Erfolg 1 und bei Misserfolg 0 zurück
public static int deleteNode(int[] binaryHeap, int value, int nodeNum) {
int index = searchNode(binaryHeap, value, nodeNum, 0);
//Tun Sie nichts, wenn in binaryHeap kein Wert vorhanden ist
if (index == -1) {
return 0;
}
//Verschieben Sie die letzten Daten vorübergehend
binaryHeap[index] = binaryHeap[nodeNum - 1];
// binaryHeap[index]Schleife solange es Kinder gibt
//Beachten Sie, dass die Gesamtzahl der Knoten um eins reduziert wurde.
while (2 * index + 1 < nodeNum - 1) {
int childIndex, childValue;
//Wenn es nur das linke Kind gibt
if (2 * index + 1 == nodeNum - 2) {
childIndex = 2 * index + 1;
childValue = binaryHeap[2 * index + 1];
}
//Wenn Sie linke und rechte Kinder haben
else {
//Wenn das Kind links kleiner ist
if (binaryHeap[2 * index + 1] <= binaryHeap[2 * index + 2]) {
childIndex = 2 * index + 1;
childValue = binaryHeap[2 * index + 1];
}
//Wenn das richtige Kind kleiner ist
else {
childIndex = 2 * index + 2;
childValue = binaryHeap[2 * index + 2];
}
}
//Vergleichen Sie Ihre aktuelle Position mit dem kleineren Kind
//Wenn die aktuelle Position größer ist
if (binaryHeap[index] > childValue) {
//Tauschen Sie die aktuelle Position und das Kind aus
binaryHeap[childIndex] = binaryHeap[index];
binaryHeap[index] = childValue;
index = childIndex;
}
//Wenn das Kind größer ist
else {
return 1;
}
}
return 1;
}
//Eine Funktion, die den dichotomisierten Heap nach Knoten durchsucht, deren Daten einen Wert haben
//Index des Knotens, wenn erfolgreich, wenn nicht erfolgreich-Rückgabe 1
public static int searchNode(int[] binaryHeap, int value, int nodeNum, int index) {
//Tun Sie nichts, wenn die Anzahl der Knoten 0 ist
if (nodeNum == 0) {
return -1;
}
//Scannen Sie in der Reihenfolge des Ziels
//Erfolgreiche Suche
if (binaryHeap[index] == value) {
return index;
}
//Suchfehler
else if (binaryHeap[index] > value) {
return -1;
}
//Weiter so
else {
int leftResult = -1, rightResult = -1;
if (2 * index + 1 < nodeNum) {
leftResult = searchNode(binaryHeap, value, nodeNum, 2 * index + 1);
}
if (2 * index + 2 < nodeNum) {
rightResult = searchNode(binaryHeap, value, nodeNum, 2 * index + 2);
}
if (leftResult == -1 && rightResult == -1) {
return -1;
}
else if (leftResult != -1) {
return leftResult;
}
else {
return rightResult;
}
}
}
public static void main(String[] args) {
int[] binaryHeap = new int[100];
int nodeNum = 0;
nodeNum += insertNode(binaryHeap, 8, nodeNum);
nodeNum += insertNode(binaryHeap, 12, nodeNum);
nodeNum += insertNode(binaryHeap, 19, nodeNum);
nodeNum += insertNode(binaryHeap, 9, nodeNum);
nodeNum += insertNode(binaryHeap, 4, nodeNum);
nodeNum += insertNode(binaryHeap, 21, nodeNum);
nodeNum += insertNode(binaryHeap, 2, nodeNum);
nodeNum += insertNode(binaryHeap, 14, nodeNum);
//Keine doppelte Einfügung zulassen
nodeNum += insertNode(binaryHeap, 14, nodeNum);
breadthFirstSearch(binaryHeap, nodeNum);
System.out.println("nodeNum: " + nodeNum);
int index = searchNode(binaryHeap, 14, nodeNum, 0);
System.out.println("index: " + index + ", value: " + binaryHeap[14]);
//Wenn Sie nach einem Knoten suchen, der nicht vorhanden ist-1 ist zurück
index = searchNode(binaryHeap, 1, nodeNum, 0);
System.out.println("index: " + index);
nodeNum -= deleteNode(binaryHeap, 14, nodeNum);
nodeNum -= deleteNode(binaryHeap, 2, nodeNum);
nodeNum -= deleteNode(binaryHeap, 21, nodeNum);
//Sie können nicht löschen, was Sie nicht haben
nodeNum -= deleteNode(binaryHeap, 14, nodeNum);
breadthFirstSearch(binaryHeap, nodeNum);
System.out.println("nodeNum: " + nodeNum);
}
}
Das Ausführungsergebnis ist wie folgt.
2 8 4 12 9 21 19 14
nodeNum: 8
index: 7, value: 0
index: -1
4 8 19 12 9
nodeNum: 5
Die folgenden Funktionen sind im obigen Programm implementiert.
--void widththFirstSearch (int [] binaryTree, int nodeNum): Eine Funktion, die einen Halbbaum in der Reihenfolge der Suche nach Breitenpriorität anzeigt. --int insertNode (int [] binaryHeap, int value, int nodeNum): Eine Funktion, die einen neuen Knoten mit Wert als Daten in den Dichotomie-Heap einfügt. --int searchNode (int [] binaryHeap, int value, int nodeNum): Eine Funktion, die den dichotomen Heap nach Knoten durchsucht, die einen Wert als Daten haben. --int deleteNode (int [] binaryHeap, int value, int nodeNum): Eine Funktion, die einen Knoten mit einem Wert als Daten aus dem Dichotomie-Heap löscht.
Die searchNode-Funktion scannt in der Reihenfolge des Ziels. Im dichotomisierten Heap sind die untergeordneten Daten immer größer als die übergeordneten Daten. Daher versuche ich, zurückzukehren, wenn die aktuellen Knotendaten größer als der Wert sind.
Verwenden Sie in der Funktion insertNode zuerst die Funktion searchNode, um zu überprüfen, ob sich im dichotomisierten Heap ein Knoten befindet, der einen Wert als Daten hat. Wenn es bereits vorhanden ist, wird es zurückgegeben, ohne einen neuen Knoten zu erstellen. Wenn nicht, fügen Sie zuerst einen Knoten am Ende des Arrays hinzu. Vergleichen Sie dann die Größe mit dem Elternteil für diese Position und tauschen Sie sich mit dem Elternteil aus, wenn das Elternteil größer ist. Wiederholen Sie den vorherigen Vorgang, bis die aktuelle Position zur Wurzel oder das übergeordnete Element kleiner wird und das Einfügen abgeschlossen ist.
Abschließend werde ich in Bezug auf die Funktion deleteNode das Verfahren zum Vergleichen von Knoten erläutern. Dies ist ein Engpass bei der Betrachtung der Funktionsweise dieser Funktion. Vergleichen Sie zunächst, welches der linken und rechten Kinder kleiner ist, und erinnern Sie sich an das kleinere. Wenn es nur das linke Kind gibt, denken Sie an das linke Kind. Da der dichotomisierte Heap ein vollständiger dichotomisierter Baum ist, ist es übrigens unwahrscheinlich, dass es nur das richtige Kind gibt. Vergleichen Sie als Nächstes, welches der gespeicherten Kinder und der Knoten an der aktuellen Position kleiner sind. Wenn das Kind größer ist, kann es sich nicht weiter bewegen und beendet den Vergleich. Wenn die aktuelle Position größer ist, wird sie durch das untergeordnete Element ersetzt und als aktuelle Position verwendet, um sie erneut mit dem untergeordneten Element zu vergleichen. Wiederholen Sie diesen Vergleich, und wenn Ihre aktuelle Position ein Blatt ist, beenden Sie dort.
Verwenden Sie nun zum Betrieb der Funktion deleteNode zunächst die Funktion searchNode, um den Index des Zielknotens zu ermitteln. Bewegen Sie dann den letzten Knoten an diese Position. Jetzt müssen Sie nur noch den Knoten mit dem untergeordneten Knoten vergleichen und ihn verschieben, bis er in die richtige Position passt.
Es mag ein wenig schwierig gewesen sein, aber ich hoffe, Sie können den Dichotomie-Haufen verstehen. Nächstes Mal werde ich den Dichotomiebaum erklären.
Teil 5 ist hier
Recommended Posts