Partie 3 est ici
Jusqu'à présent, j'ai expliqué le contour de l'arbre bifurqué. A partir de ce moment, j'expliquerai un exemple concret d'arbre bifurqué. Le premier exemple est un arbre dichotomisé appelé tas binaire. La structure est simple, c'est juste une dichotomie complète dont les données parentes sont toujours plus petites que les données enfants. Un arbre bifurqué complet était un arbre bifurqué dans lequel il n'y avait pas d'espaces aux nœuds qui n'étaient pas des feuilles, et toutes les feuilles étaient justifiées à gauche. Puisque le tas dichotomisé est une sorte d'arbre dichotomisé complet, il peut être réalisé à l'aide d'un tableau.
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);
//Fonction à afficher par ordre de recherche de priorité de largeur
void breadthFirstSearch(int binaryTree[], int nodeNum)
{
for (int i = 0; i < nodeNum; i++) {
cout << binaryTree[i] << " ";
}
cout << endl;
}
//Une fonction qui insère un nouveau nœud dans le tas de dichotomie
//Renvoie 1 en cas de succès, 0 en cas d'échec
int insertNode(int binaryHeap[], int value, int nodeNum)
{
//Ne rien faire s'il y a déjà de la valeur
if (searchNode(binaryHeap, value, nodeNum, 0) != -1) {
return 0;
}
//Inséré temporairement à la fin
binaryHeap[nodeNum] = value;
int i = nodeNum;
//Suivez de la fin à la racine
while (i > 0) {
//Si le parent est plus grand
if (binaryHeap[i] < binaryHeap[(i - 1) / 2]) {
//Échange d'enfant avec un parent
binaryHeap[i] = binaryHeap[(i - 1) / 2];
binaryHeap[(i - 1) / 2] = value;
i = (i - 1) / 2;
}
//Si le parent est plus petit
else {
return 1;
}
}
return 1;
}
//Une fonction qui supprime les nœuds avec une valeur dans les données du tas de dichotomie
//Renvoie 1 en cas de succès, 0 en cas d'échec
int deleteNode(int binaryHeap[], int value, int nodeNum)
{
int index = searchNode(binaryHeap, value, nodeNum, 0);
//Ne rien faire s'il n'y a pas de valeur dans binaryHeap
if (index == -1) {
return 0;
}
//Déplacer temporairement les dernières données
binaryHeap[index] = binaryHeap[nodeNum - 1];
// binaryHeap[index]Boucle tant qu'il y a des enfants
//Notez que le nombre total de nœuds a été réduit de un.
while (2 * index + 1 < nodeNum - 1) {
int childIndex, childValue;
//S'il ne reste que l'enfant
if (2 * index + 1 == nodeNum - 2) {
childIndex = 2 * index + 1;
childValue = binaryHeap[2 * index + 1];
}
//Si vous avez des enfants à gauche et à droite
else {
//Si l'enfant à gauche est plus petit
if (binaryHeap[2 * index + 1] <= binaryHeap[2 * index + 2]) {
childIndex = 2 * index + 1;
childValue = binaryHeap[2 * index + 1];
}
//Si le bon enfant est plus petit
else {
childIndex = 2 * index + 2;
childValue = binaryHeap[2 * index + 2];
}
}
//Comparez votre position actuelle avec le plus petit enfant
//Si la position actuelle est plus grande
if (binaryHeap[index] > childValue) {
//Permuter la position actuelle et l'enfant
binaryHeap[childIndex] = binaryHeap[index];
binaryHeap[index] = childValue;
index = childIndex;
}
//Si l'enfant est plus grand
else {
return 1;
}
}
return 1;
}
//Une fonction qui recherche dans le tas dichotomisé les nœuds qui ont une valeur dans les données
//Index du nœud en cas de succès, en cas d'échec-Renvoie 1
int searchNode(int binaryHeap[], int value, int nodeNum, int index)
{
//Ne rien faire si le nombre de nœuds est égal à 0
if (nodeNum == 0) {
return -1;
}
//Scannez dans l'ordre de destination
//Recherche réussie
if (binaryHeap[index] == value) {
return index;
}
//Échec de la recherche
else if (binaryHeap[index] > value) {
return -1;
}
//Continue encore
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);
//Ne pas autoriser l'insertion en double
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;
//Si vous recherchez un nœud qui n'existe pas-1 est de retour
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);
//Vous ne pouvez pas supprimer ce que vous n'avez pas
nodeNum -= deleteNode(binaryHeap, 14, nodeNum);
breadthFirstSearch(binaryHeap, nodeNum);
cout << "nodeNum: " << nodeNum << endl;
}
Java
BinaryHeap.java
public class BinaryHeapAnswer {
//Fonction à afficher par ordre de recherche de priorité de largeur
public static void breadthFirstSearch(int[] binaryTree, int nodeNum) {
for (int i = 0; i < nodeNum; i++) {
System.out.print(binaryTree[i] + " ");
}
System.out.println("");
}
//Une fonction qui insère un nouveau nœud dans le tas de dichotomie
//Renvoie 1 en cas de succès, 0 en cas d'échec
public static int insertNode(int[] binaryHeap, int value, int nodeNum) {
//Ne rien faire s'il y a déjà de la valeur
if (searchNode(binaryHeap, value, nodeNum, 0) != -1) {
return 0;
}
//Inséré temporairement à la fin
binaryHeap[nodeNum] = value;
int i = nodeNum;
//Suivez de la fin à la racine
while (i > 0) {
//Si le parent est plus grand
if (binaryHeap[i] < binaryHeap[(i - 1) / 2]) {
//Échange d'enfant avec un parent
binaryHeap[i] = binaryHeap[(i - 1) / 2];
binaryHeap[(i - 1) / 2] = value;
i = (i - 1) / 2;
}
//Si le parent est plus petit
else {
return 1;
}
}
return 1;
}
//Une fonction qui supprime les nœuds avec une valeur dans les données du tas de dichotomie
//Renvoie 1 en cas de succès, 0 en cas d'échec
public static int deleteNode(int[] binaryHeap, int value, int nodeNum) {
int index = searchNode(binaryHeap, value, nodeNum, 0);
//Ne rien faire s'il n'y a pas de valeur dans binaryHeap
if (index == -1) {
return 0;
}
//Déplacer temporairement les dernières données
binaryHeap[index] = binaryHeap[nodeNum - 1];
// binaryHeap[index]Boucle tant qu'il y a des enfants
//Notez que le nombre total de nœuds a été réduit de un.
while (2 * index + 1 < nodeNum - 1) {
int childIndex, childValue;
//S'il ne reste que l'enfant
if (2 * index + 1 == nodeNum - 2) {
childIndex = 2 * index + 1;
childValue = binaryHeap[2 * index + 1];
}
//Si vous avez des enfants à gauche et à droite
else {
//Si l'enfant à gauche est plus petit
if (binaryHeap[2 * index + 1] <= binaryHeap[2 * index + 2]) {
childIndex = 2 * index + 1;
childValue = binaryHeap[2 * index + 1];
}
//Si le bon enfant est plus petit
else {
childIndex = 2 * index + 2;
childValue = binaryHeap[2 * index + 2];
}
}
//Comparez votre position actuelle avec le plus petit enfant
//Si la position actuelle est plus grande
if (binaryHeap[index] > childValue) {
//Permuter la position actuelle et l'enfant
binaryHeap[childIndex] = binaryHeap[index];
binaryHeap[index] = childValue;
index = childIndex;
}
//Si l'enfant est plus grand
else {
return 1;
}
}
return 1;
}
//Une fonction qui recherche dans le tas dichotomisé les nœuds qui ont une valeur dans les données
//Index du nœud en cas de succès, en cas d'échec-Renvoie 1
public static int searchNode(int[] binaryHeap, int value, int nodeNum, int index) {
//Ne rien faire si le nombre de nœuds est égal à 0
if (nodeNum == 0) {
return -1;
}
//Scannez dans l'ordre de destination
//Recherche réussie
if (binaryHeap[index] == value) {
return index;
}
//Échec de la recherche
else if (binaryHeap[index] > value) {
return -1;
}
//Continue encore
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);
//Ne pas autoriser l'insertion en double
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]);
//Si vous recherchez un nœud qui n'existe pas-1 est de retour
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);
//Vous ne pouvez pas supprimer ce que vous n'avez pas
nodeNum -= deleteNode(binaryHeap, 14, nodeNum);
breadthFirstSearch(binaryHeap, nodeNum);
System.out.println("nodeNum: " + nodeNum);
}
}
Le résultat de l'exécution est le suivant.
2 8 4 12 9 21 19 14
nodeNum: 8
index: 7, value: 0
index: -1
4 8 19 12 9
nodeNum: 5
Les fonctions suivantes sont implémentées dans le programme ci-dessus.
--void breadthFirstSearch (int [] binaryTree, int nodeNum): Une fonction qui affiche un demi-arbre dans l'ordre de recherche de priorité de largeur. --int insertNode (int [] binaryHeap, int value, int nodeNum): une fonction qui insère un nouveau nœud avec une valeur en tant que données dans le tas de dichotomie. --int searchNode (int [] binaryHeap, int value, int nodeNum): une fonction qui recherche dans le tas dichotomique les nœuds qui ont une valeur en tant que données. --int deleteNode (int [] binaryHeap, int value, int nodeNum): une fonction qui supprime un nœud qui a une valeur en tant que données du tas de dichotomie.
La fonction searchNode scanne dans l'ordre de destination. Dans le tas dichotomisé, les données enfants sont toujours plus grandes que les données parent, donc j'essaie de revenir lorsque les données du nœud actuel sont plus grandes que la valeur.
Dans la fonction insertNode, utilisez d'abord la fonction searchNode pour vérifier s'il existe un nœud dans le tas dichotomisé qui a une valeur en tant que données. S'il existe déjà, il reviendra sans créer de nouveau nœud. Sinon, ajoutez d'abord un nœud à la fin du tableau. Ensuite, comparez la taille avec le parent pour cette position et, si le parent est plus grand, échangez-vous avec le parent. Répétez l'opération précédente jusqu'à ce que la position actuelle devienne la racine ou que le parent devienne plus petit et que l'insertion soit terminée.
Enfin, concernant la fonction deleteNode, j'expliquerai la procédure de comparaison des nœuds, ce qui est un goulot d'étranglement lorsque l'on considère le fonctionnement de cette fonction. Tout d'abord, comparez lequel des enfants gauche et droit est le plus petit et souvenez-vous du plus petit. S'il n'y a que l'enfant gauche, souvenez-vous de l'enfant gauche. À propos, puisque le tas coupé en deux est un arbre complètement coupé en deux, il est peu probable qu'il y ait seulement le bon enfant. Ensuite, comparez lequel de l'enfant mémorisé et du nœud à la position actuelle est le plus petit. Si l'enfant est plus grand, il ne peut plus bouger et met fin à la comparaison. Si la position actuelle est plus grande, elle sera remplacée par l'enfant, et qui sera utilisée comme position actuelle pour comparer à nouveau avec l'enfant. Répétez cette comparaison, et si votre position actuelle est une feuille, arrêtez-vous là.
Maintenant, en ce qui concerne le fonctionnement de la fonction deleteNode, utilisez d'abord la fonction searchNode pour acquérir l'index du nœud cible. Déplacez ensuite le dernier nœud vers cette position. Tout ce que vous avez à faire maintenant est de comparer le nœud avec l'enfant et de le déplacer jusqu'à ce qu'il tienne dans la bonne position.
Cela a peut-être été un peu difficile, mais j'espère que vous pouvez comprendre le tas de dichotomie. La prochaine fois, j'expliquerai l'arbre de la dichotomie.
Partie 5 est ici
Recommended Posts