Insertion d'arbre de recherche binaire en C++

Cet article montrera comment implémenter la fonction d’insertion pour la structure de données d’arborescence de recherche binaire en C++.

Insérer de nouveaux nœuds dans l’arborescence de recherche binaire en C++

Les arbres binaires représentent généralement un sous-ensemble de structures arborescentes. Ils sont appelés binaires car ils ont au plus deux enfants à un nœud donné. Dans ce cas, nous discutons d’un arbre de recherche binaire où chaque nœud contient un membre de données appelé clé, et à chaque niveau de l’arbre, la clé du nœud donné doit être supérieure aux clés de son sous-arbre de gauche et inférieure à toutes les clés de droite. sous-arbre. Cette fonctionnalité nous permettra d’utiliser un algorithme de recherche binaire sur l’arbre lorsque nous recherchons dans un tableau trié.

Dans un premier temps, nous devons déclarer un nœud d’arbre struct, qui comprend deux pointeurs vers les nœuds left/right et une clé. Par souci de simplicité, nous stockons les clés sous forme de valeurs int, mais il peut être nécessaire de construire une disposition différente pour le nœud en fonction du problème. Nous construisons également cet arbre manuellement en déclarant un seul pointeur TreeNode comme racine de l’arbre puis en appelant la fonction insertNode pour ajouter de nouveaux nœuds.

Pour une meilleure démonstration et vérification de notre exemple, nous incluons également une fonction pour trouver un nœud avec la clé donnée et une autre pour imprimer le contenu de l’arbre entier. Ce dernier nous aidera à inspecter facilement l’arborescence à chaque étape du programme. Notez que les trois fonctions utilisent la récursivité car une structure arborescente est inhérente aux algorithmes de division et de conquête.

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::string;
using std::vector;

struct TreeNode {
  int key;
  struct TreeNode *left{};
  struct TreeNode *right{};
};

void insertNode(TreeNode *&root, const int k) {
  if (root == nullptr) {
    root = new TreeNode;
    root->key = k;
    root->left = nullptr;
    root->right = nullptr;
  } else {
    if (k < root->key)
      insertNode(root->left, k);
    else
      insertNode(root->right, k);
  }
}

TreeNode *findNode(TreeNode *root, const int k) {
  if (root == nullptr) return nullptr;

  if (k == root->key) return root;

  if (k < root->key)
    return findNode(root->left, k);
  else
    return findNode(root->right, k);
}

void printTree(TreeNode *n) {
  if (n != nullptr) {
    printTree(n->left);
    cout << n->key << "; ";
    printTree(n->right);
  }
}

int main() {
  std::vector<int> v1{11, 23, 3, 5, 9, 15, 2, 20};

  TreeNode *root = nullptr;

  for (const auto &item : v1) {
    insertNode(root, item);
  }
  printTree(root);
  cout << endl;

  std::vector<int> v2{1, 22, 4, 16};
  for (const auto &item : v2) {
    insertNode(root, item);
  }
  printTree(root);
  cout << endl;

  return EXIT_SUCCESS;
}

Production:

2; 3; 5; 9; 11; 15; 20; 23;
1; 2; 3; 4; 5; 9; 11; 15; 16; 20; 22; 23;

Dans la fonction main, nous déclarons deux vecteurs int arbitraires puis poussons leurs éléments dans l’arbre. Notez que notre fonction insertNode prend deux paramètres : un nœud racine et une valeur de clé. Il doit vérifier si le nœud racine donné est valide ou simplement un nullptr, ce dernier indiquant que la fonction doit créer le contenu du nœud racine.

Si le nœud racine est déjà initialisé, la fonction doit se dérouler en fonction de la valeur de la clé, qui est comparée à la clé du nœud actuel. Si la valeur de la clé transmise est inférieure à la clé donnée, nous devons passer au sous-arbre de gauche. Sinon - le bon sous-arbre.

Finalement, nous atteindrons le nœud où la clé doit être stockée, et la traversée dans l’ordre imprimera toujours les valeurs de clé triées comme indiqué dans l’extrait de code.