Part 4 est ici
Cette fois, j'expliquerai l'arbre de la dichotomie. Encore une fois, la structure est simple: les données parent sont toujours plus grandes que les données enfants de gauche, et les données enfants de droite sont toujours plus grandes que les données parent. Ce n'est pas toujours une dichotomie complète, donc elle est réalisée à l'aide de classes.
C++
BST.cpp
#include <iostream>
using namespace std;
class BST
{
public:
friend class Main;
int value;
BST *left;
BST *right;
BST(int);
~BST();
};
void inorder(BST *);
BST *insertNode(BST *, int);
BST *deleteNode(BST *, int);
BST *deleteNodeEl(BST *, BST *, BST *, bool);
BST::BST(int value):value(value), left(0), right(0){}
BST::~BST()
{
delete left;
delete right;
}
void inorder(BST *root)
{
if (root->left != 0) {
inorder(root->left);
}
cout << root->value << " ";
if (root->right != 0) {
inorder(root->right);
}
return;
}
//Une fonction qui insère un nouveau nœud dans l'arbre de dichotomie
//Renvoie BST après l'insertion
BST *insertNode(BST *root, int value)
{
//Ne rien faire s'il y a déjà de la valeur
if (root->value == value) {
return root;
}
//Si la position actuelle est supérieure à la valeur
else if (root->value > value) {
//S'il n'y a pas d'enfant à gauche
if (root->left == 0) {
root->left = new BST(value);
}
//Si vous avez un enfant sur la gauche
else {
root->left = insertNode(root->left, value);
}
}
//Si la position actuelle est supérieure à la valeur
else {
//S'il n'y a pas de bon enfant
if (root->right == 0) {
root->right = new BST(value);
}
//Si vous avez le bon enfant
else {
root->right = insertNode(root->right, value);
}
}
return root;
}
//Une fonction qui supprime les nœuds qui ont une valeur dans les données
//Renvoie le BST supprimé
BST *deleteNode(BST *root, int value)
{
BST *parent = 0;
BST *present = root;
bool directionIsLeft = false;
while (present != 0) {
//Lorsque les données à la position actuelle sont plus grandes que la valeur
if (present->value > value) {
parent = present;
directionIsLeft = true;
present = present->left;
}
//Lorsque la valeur est supérieure aux données à la position actuelle
else if (present->value < value) {
parent = present;
directionIsLeft = false;
present = present->right;
}
//Lorsque les données de valeur et de position actuelle correspondent
else {
//Au moins un n'a pas d'enfants
if (present->left == 0 || present->right == 0) {
return deleteNodeEl(root, present, parent, directionIsLeft);
}
//Si vous avez les deux enfants
else {
BST *right = present->right;
parent = present;
directionIsLeft = false;
//Trouvez la valeur minimale sous le bon enfant
while (right->left != 0) {
parent = right;
right = right->left;
directionIsLeft = true;
}
//Au moment de quitter le while précédent, la droite indique le nœud avec la valeur minimale en dessous de l'enfant de droite.
//Échangez les données actuelles et correctes
present->value = right->value;
right->value = value;
return deleteNodeEl(root, right, parent, directionIsLeft);
}
}
}
return root;
}
//Une fonction qui reconstruit un arbre de dichotomie après la suppression d'un cadeau lorsqu'il y a un ou moins d'enfants
//Renvoie le BST reconstruit
BST *deleteNodeEl(BST *root, BST *present, BST *parent, bool directionIsLeft)
{
//Si vous n'avez pas d'enfants
if (present->left == 0 && present->right == 0) {
//Si la position actuelle est root
if (parent == 0) {
delete present;
return NULL;
}
//Si la position actuelle n'est pas la racine
else {
if (directionIsLeft) {
parent->left = 0;
}
else {
parent->right = 0;
}
delete present;
return root;
}
}
//Si vous n'avez qu'un seul enfant
else if (present->left == 0 || present->right == 0) {
//Si vous avez le bon enfant
if (present->right != 0) {
//Si la position actuelle est root
if (parent == 0) {
BST *right = present->right;
delete present;
return right;
}
//Si la position actuelle n'est pas la racine
else {
if (directionIsLeft) {
parent->left = present->right;
}
else {
parent->right = present->right;
}
delete present;
return root;
}
}
//Si vous avez un enfant sur la gauche
else {
//Si la position actuelle est root
if (parent == 0) {
BST *left = present->left;
delete present;
return left;
}
//Si la position actuelle n'est pas la racine
else {
if (directionIsLeft) {
parent->left = present->left;
}
else {
parent->right = present->left;
}
delete present;
return root;
}
}
}
delete present;
return root;
}
int main()
{
BST *root = new BST(20);
root = insertNode(root, 10);
root = insertNode(root, 26);
root = insertNode(root, 5);
root = insertNode(root, 14);
root = insertNode(root, 23);
root = insertNode(root, 25);
//L'insertion en double n'est pas autorisée
root = insertNode(root, 25);
inorder(root);
cout << endl;
cout << "10: " << boolalpha << searchNode(root, 10) << endl;
cout << "23: " << boolalpha << searchNode(root, 23) << endl;
//Vous ne pouvez pas rechercher ce que vous n'avez pas
cout << "15: " << boolalpha << searchNode(root, 15) << endl;
root = deleteNode(root, 25);
root = deleteNode(root, 14);
//Vous ne pouvez pas supprimer ce que vous n'avez pas
root = deleteNode(root, 14);
inorder(root);
cout << endl;
}
Java
BST.java
public class BST {
int value;
BST left;
BST right;
BST(int value) {
this.value = value;
this.left = null;
this.right = null;
}
public static void inorder(BST root) {
if (root.left != null) {
inorder(root.left);
}
System.out.print(root.value + " ");
if (root.right != null) {
inorder(root.right);
}
return;
}
//Une fonction qui insère un nouveau nœud dans l'arbre de dichotomie
//Renvoie BST après l'insertion
public static BST insertNode(BST root, int value) {
//Ne rien faire s'il y a déjà de la valeur
if (root.value == value) {
return root;
}
//Si la position actuelle est supérieure à la valeur
else if (root.value > value) {
//S'il n'y a pas d'enfant à gauche
if (root.left == null) {
root.left = new BST(value);
}
//Si vous avez un enfant sur la gauche
else {
root.left = insertNode(root.left, value);
}
}
//Si la position actuelle est supérieure à la valeur
else {
//S'il n'y a pas de bon enfant
if (root.right == null) {
root.right = new BST(value);
}
//Si vous avez le bon enfant
else {
root.right = insertNode(root.right, value);
}
}
return root;
}
//Une fonction qui supprime les nœuds qui ont une valeur dans les données
//Renvoie le BST supprimé
public static BST deleteNode(BST root, int value) {
BST parent = null;
BST present = root;
boolean directionIsLeft = false;
while (present != null) {
//Lorsque les données à la position actuelle sont plus grandes que la valeur
if (present.value > value) {
parent = present;
directionIsLeft = true;
present = present.left;
}
//Lorsque la valeur est supérieure aux données à la position actuelle
else if (present.value < value) {
parent = present;
directionIsLeft = false;
present = present.right;
}
//Lorsque les données de valeur et de position actuelle correspondent
else {
//Au moins un n'a pas d'enfants
if (present.left == null || present.right == null) {
return deleteNodeEl(root, present, parent, directionIsLeft);
}
//Si vous avez les deux enfants
else {
BST right = present.right;
parent = present;
directionIsLeft = false;
//Trouvez la valeur minimale sous le bon enfant
while (right.left != null) {
parent = right;
right = right.left;
directionIsLeft = true;
}
//Au moment de quitter le while précédent, la droite indique le nœud avec la valeur minimale en dessous de l'enfant de droite.
//Échangez les données actuelles et correctes
present.value = right.value;
right.value = value;
return deleteNodeEl(root, right, parent, directionIsLeft);
}
}
}
return root;
}
//Une fonction qui reconstruit un arbre de dichotomie après la suppression d'un cadeau lorsqu'il y a un ou moins d'enfants
//Renvoie le BST reconstruit
public static BST deleteNodeEl(BST root, BST present, BST parent, boolean directionIsLeft) {
//Si vous n'avez pas d'enfants
if (present.left == null && present.right == null) {
//Si la position actuelle est root
if (parent == null) {
return null;
}
//Si la position actuelle n'est pas la racine
else {
if (directionIsLeft) {
parent.left = null;
}
else {
parent.right = null;
}
return root;
}
}
//Si vous n'avez qu'un seul enfant
else if (present.left == null || present.right == null) {
//Si vous avez le bon enfant
if (present.right != null) {
//Si la position actuelle est root
if (parent == null) {
return present.right;
}
//Si la position actuelle n'est pas la racine
else {
if (directionIsLeft) {
parent.left = present.right;
}
else {
parent.right = present.right;
}
return root;
}
}
//Si vous avez un enfant sur la gauche
else {
//Si la position actuelle est root
if (parent == null) {
return present.left;
}
//Si la position actuelle n'est pas la racine
else {
if (directionIsLeft) {
parent.left = present.left;
}
else {
parent.right = present.left;
}
return root;
}
}
}
return root;
}
public static void main(String[] args) {
BST root = new BST(20);
root = insertNode(root, 10);
root = insertNode(root, 26);
root = insertNode(root, 5);
root = insertNode(root, 14);
root = insertNode(root, 23);
root = insertNode(root, 25);
//L'insertion en double n'est pas autorisée
root = insertNode(root, 25);
inorder(root);
System.out.println();
System.out.println("10: " + searchNode(root, 10));
System.out.println("23: " + searchNode(root, 23));
//Vous ne pouvez pas rechercher ce que vous n'avez pas
System.out.println("15: " + searchNode(root, 15));
root = deleteNode(root, 25);
root = deleteNode(root, 14);
//Vous ne pouvez pas supprimer ce que vous n'avez pas
root = deleteNode(root, 14);
inorder(root);
System.out.println();
}
}
Le résultat de l'exécution est le suivant.
5 10 14 20 23 25 26
10: true
23: true
15: false
5 10 20 23 26
Les explications suivantes sont basées sur des programmes Java. Les fonctions suivantes sont implémentées dans le programme ci-dessus.
--void inorder (racine BST): une fonction qui affiche un arbre de dichotomie dans l'ordre de passage. --BST insertNode (racine BST, valeur int): une fonction qui insère un nouveau nœud avec une valeur en tant que données dans l'arbre de dichotomie. --BST deleteNode (racine BST, valeur int): une fonction qui supprime un nœud qui a une valeur en tant que données de l'arbre de dichotomie. --BST deleteNodeEl (racine BST, BST présent, parent BST, booléen directionIsLeft): une fonction qui reconstruit un arbre de dichotomie lorsqu'il y a un ou moins d'enfants.
La fonction insertNode compare d'abord les données de position actuelles avec la valeur. S'ils sont égaux, ils reviennent sans créer de nouveau nœud. Si les données à la position actuelle sont supérieures à la valeur, déplacez la position actuelle vers l'enfant à gauche. Si la valeur est supérieure aux données à la position actuelle, déplacez la position actuelle vers le bon enfant. Répétez l'opération précédente jusqu'à ce qu'il n'y ait plus de destination à parcourir. Lorsqu'il n'y a pas de destination vers laquelle aller, créez un nouveau nœud avec une valeur sous forme de données et l'insertion est terminée.
La fonction searchNode se comporte de la même manière que la fonction insertNode que j'ai mentionnée précédemment. Tout d'abord, comparez les données de position actuelle avec la valeur, et si les données de position actuelle sont plus grandes que la valeur, déplacez la position actuelle vers l'enfant gauche. Si la valeur est supérieure aux données à la position actuelle, déplacez la position actuelle vers le bon enfant. Répétez l'opération précédente jusqu'à ce que vous atteigniez un nœud avec des données égales à value. Si le nœud cible est trouvé, true est renvoyé, et si la feuille est atteinte sans être trouvée, false est renvoyé et la recherche est terminée.
La fonction deleteNode est également très similaire aux fonctions searchNode et insertNode au début. Si les données à la position actuelle sont supérieures à la valeur, déplacez la position actuelle vers l'enfant à gauche. Si la valeur est supérieure aux données à la position actuelle, déplacez la position actuelle vers le bon enfant. Répétez l'opération précédente jusqu'à ce que vous atteigniez un nœud avec des données égales à value. Lorsque vous trouvez le nœud souhaité, supprimez-le. Cependant, si vous l'effacez simplement, même l'enfant du nœud à la position actuelle sera effacé. Par conséquent, il est nécessaire de recréer la zone sous le nœud à la position actuelle. Tout d'abord, découvrez si le nœud à la position actuelle a des enfants gauche et droit. Si vous n'avez qu'un seul enfant, déplacez-le simplement vers sa position actuelle et vous avez terminé. Si vous n'avez ni l'un ni l'autre, effacez simplement le nœud à votre emplacement actuel et vous avez terminé. Si vous avez les deux enfants, recherchez le nœud avec les plus petites données sous le bon enfant et échangez les données de ce nœud avec les données de votre emplacement actuel. Après cela, recréez le bas du nœud échangé et vous avez terminé.
C'est tout l'article sur le demi-arbre que je voulais commémorer. Merci d'avoir lu jusqu'ici. J'espère que cet article vous aidera dans vos études.
Recommended Posts