Implémenter la structure de données d'arbre binaire en C++

1. Implémenter l’arbre binaire à l’aide du mot-clé struct en C++
2. Implémenter des fonctions pour calculer la taille et la hauteur de l’arborescence et une fonction pour imprimer des éléments en C++

Cet article explique comment implémenter la structure de données d’arborescence binaire en C++.

Implémenter l’arbre binaire à l’aide du mot-clé struct en C++

Les arbres sont des structures de données abstraites utilisées dans divers algorithmes fondamentaux. Ce sont généralement des structures hiérarchiques où il doit y avoir un nœud racine et ses enfants formant des sous-arbres. En outre, il existe plusieurs types d’arborescence, chacune adaptée à des besoins particuliers et offrant certains compromis.

Un arbre binaire est l’une des sous-classes de structures de données arborescentes, et il est défini comme un arbre où chaque nœud doit avoir au plus deux enfants, y compris les nœuds enfants désignés comme left et right. Dans ce cas, nous implémentons un arbre binaire en utilisant la fonction struct puisqu’elle déclare une classe dont les membres sont publics par défaut. Un nœud dans un arbre binaire contient deux pointeurs vers les nœuds gauche/droite et les données nécessaires. Notez que nous avons déclaré un seul membre int pour représenter les données stockées au nœud à des fins d’explication uniquement.

Nous définissons un constructeur qui prend un entier comme argument et initialise le membre data avec sa valeur. Ensuite, il initialise les pointeurs à deux nœuds avec des valeurs nullptr, ce qui est une façon courante de désigner les nœuds feuilles. L’exemple de code de pilote construit un exemple de graphique et stocke des entiers aléatoires dans chaque nœud. Il existe plusieurs sous-types d’arbres binaires, par exemple, un arbre binaire complet est une structure où chaque nœud a 0 ou 2 enfants. Un autre est appelé un arbre binaire parfait, où tous les nœuds intérieurs ont deux enfants et tous les nœuds feuilles ont des profondeurs identiques.

#include <iostream>
#include <random>

using std::cout;
using std::endl;

struct BinTreeNode {
  int data;
  struct BinTreeNode *left;
  struct BinTreeNode *right;

  BinTreeNode() = default;
  explicit BinTreeNode(int d) : data(d) {
    left = nullptr;
    right = nullptr;
  }
};

constexpr int MIN = 1;
constexpr int MAX = 10000;

int main() {
  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  auto root = new BinTreeNode(distr(eng));
  root->left = new BinTreeNode(distr(eng));
  root->right = new BinTreeNode(distr(eng));
  root->right->left = new BinTreeNode(distr(eng));
  root->right->right = new BinTreeNode(distr(eng));

  return EXIT_SUCCESS;
}

Notez que le code ci-dessus donne une structure arborescente binaire complète, comme illustré dans le graphique suivant. Nous avons alloué chaque nœud à l’aide de l’opérateur new et transmis une valeur d’initialisation à l’aide du générateur de nombres pseudo-aléatoires.

root / left right / \ / nullptr nullptr left right /   \ /
    nullptr nullptr nullptr nullptr

Implémenter des fonctions pour calculer la taille et la hauteur de l’arborescence et une fonction pour imprimer des éléments en C++

Étant donné que la structure arborescente est la forme sous laquelle les algorithmes de division et de conquête s’exécutent, cette dernière méthode est souvent utilisée pour implémenter les fonctions qui manipulent leurs éléments. La fonction treeSize récupère la taille de l’arbre qui désigne le nombre de tous les nœuds, y compris la racine. Notez que nous n’avons besoin que d’utiliser une simple récursivité et de retourner la taille de la valeur root (qui est 1) plus les tailles des nœuds gauche/droit.

La fonction suivante est treeHeight qui récupère la hauteur de l’arbre, qui est généralement connue comme le nombre de nœuds sur le chemin le plus long d’une racine à une feuille. Cette fonction utilise également la récursivité en s’appelant sur les deux nœuds enfants et en retournant la hauteur de la valeur root (qui est 1) plus la valeur la plus élevée des appels précédents.

D’autre part, la fonction printData sort le membre data de chaque nœud vers le flux cout. Il existe plusieurs manières de parcourir l’arborescence binaire : parcours inorder, preorder et postorder.

Dans l’exemple suivant, le chemin de parcours inorder est utilisé. Le processus imprime d’abord les données des nœuds feuilles les plus à gauche vers la droite sur la même profondeur, puis se déplace vers les niveaux supérieurs. L’extrait de code suivant construit un arbre binaire partiellement aléatoire, puis appelle chacune des fonctions ci-dessus. Si la nature récursive de ces fonctions semble déroutante à première vue, vous devriez essayer de les déboguer étape par étape sur les objets d’arborescence plus petits et observer le comportement sur chaque appel de fonction récursive.

#include <iostream>
#include <random>

using std::cout;
using std::endl;

struct BinTreeNode {
  int data;
  struct BinTreeNode *left;
  struct BinTreeNode *right;

  BinTreeNode() = default;
  explicit BinTreeNode(int d) : data(d) {
    left = nullptr;
    right = nullptr;
  }
};

int treeSize(BinTreeNode *n) {
  if (n == nullptr)
    return 0;
  else
    return 1 + treeSize(n->left) + treeSize(n->right);
}

int treeHeight(BinTreeNode *n) {
  int lh, rh;

  if (n == nullptr)
    return -1;
  else {
    lh = treeHeight(n->left);
    rh = treeHeight(n->right);
    return 1 + (lh > rh ? lh : rh);
  }
}

void printData(BinTreeNode *n) {
  if (n != nullptr) {
    printData(n->left);
    cout << n->data << "; ";
    printData(n->right);
  }
}

constexpr int MIN = 1;
constexpr int MAX = 10000;

int main() {
  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  auto root = new BinTreeNode(distr(eng));
  auto tmp = root;

  auto iter = 100;
  while (iter > 0) {
    auto val = distr(eng);
    if (val % 5 == 0) {
      tmp->left = new BinTreeNode(distr(eng));
      tmp = tmp->left;
    } else if (val % 4 == 0) {
      tmp->right = new BinTreeNode(distr(eng));
      tmp = tmp->right;
    } else if (val % 6 == 0) {
      tmp->left = new BinTreeNode(distr(eng));
    } else if (val % 100 == 0) {
      tmp = root;
    } else if (val % 2 == 0) {
      tmp->right = new BinTreeNode(distr(eng));
    }
    iter -= 1;
  }

  cout << "size of tree = " << treeSize(root) << endl;
  cout << "height of tree = " << treeHeight(root) << endl;
  printData(root);

  return EXIT_SUCCESS;
}

Production:

size of tree = 45 height of tree = 37 ...(elements in the tree)