Structure des données et algorithmes - Arbre

L'arbre représente les nœuds connectés par des arêtes. Nous discuterons spécifiquement de l'arbre binaire ou de l'arbre de recherche binaire.

L'arbre binaire est une structure de données spéciale utilisée à des fins de stockage de données. Un arbre binaire a une condition spéciale selon laquelle chaque nœud peut avoir un maximum de deux enfants. Un arbre binaire présente les avantages à la fois d'un tableau ordonné et d'une liste chaînée car la recherche est aussi rapide que dans un tableau trié et les opérations d'insertion ou de suppression sont aussi rapides que dans une liste chaînée.

Termes importants

Voici les termes importants concernant l'arbre.

Path - Chemin fait référence à la séquence de nœuds le long des bords d'un arbre.
Root- Le nœud en haut de l'arbre s'appelle root. Il n'y a qu'une seule racine par arbre et un chemin entre le nœud racine et n'importe quel nœud.
Parent - Tout nœud à l'exception du nœud racine a un bord vers le haut jusqu'à un nœud appelé parent.
Child - Le nœud en dessous d'un nœud donné connecté par son bord descendant est appelé son nœud enfant.
Leaf - Le nœud qui n'a pas de nœud enfant est appelé le nœud feuille.
Subtree - Le sous-arbre représente les descendants d'un nœud.
Visiting - La visite fait référence à la vérification de la valeur d'un nœud lorsque le contrôle est sur le nœud.
Traversing - Traverser signifie passer par des nœuds dans un ordre spécifique.
Levels- Le niveau d'un nœud représente la génération d'un nœud. Si le nœud racine est au niveau 0, alors son nœud enfant suivant est au niveau 1, son petit-enfant est au niveau 2, et ainsi de suite.
keys - La clé représente une valeur d'un nœud sur la base de laquelle une opération de recherche doit être effectuée pour un nœud.

Représentation de l'arbre de recherche binaire

L'arbre de recherche binaire présente un comportement spécial. L'enfant gauche d'un nœud doit avoir une valeur inférieure à la valeur de son parent et l'enfant droit du nœud doit avoir une valeur supérieure à sa valeur parent.

Nous allons implémenter l'arborescence en utilisant l'objet nœud et en les connectant via des références.

Noeud d'arbre

Le code pour écrire un nœud d'arbre serait similaire à ce qui est donné ci-dessous. Il a une partie de données et des références à ses nœuds enfants gauche et droit.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

Dans une arborescence, tous les nœuds partagent une construction commune.

Opérations de base BST

Les opérations de base qui peuvent être effectuées sur une structure de données d'arbre de recherche binaire sont les suivantes:

Insert - Insère un élément dans un arbre / crée un arbre.
Search - Recherche un élément dans un arbre.
Preorder Traversal - Traverse un arbre en pré-commande.
Inorder Traversal - Traverse un arbre dans l'ordre.
Postorder Traversal - Traverse un arbre de manière post-ordre.

Nous allons apprendre à créer (insérer dans) une structure arborescente et à rechercher une donnée dans une arborescence dans ce chapitre. Nous en apprendrons davantage sur les méthodes de traversée des arbres dans le prochain chapitre.

Insérer une opération

La toute première insertion crée l'arborescence. Ensuite, chaque fois qu'un élément doit être inséré, recherchez d'abord son emplacement approprié. Commencez la recherche à partir du nœud racine, puis si les données sont inférieures à la valeur de clé, recherchez l'emplacement vide dans le sous-arbre de gauche et insérez les données. Sinon, recherchez l'emplacement vide dans le sous-arbre de droite et insérez les données.

Algorithme

If root is NULL 
   then create root node
return

If root exists then
   compare the data with node.data
   
   while until insertion position is located

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

   endwhile 
   
   insert data
	
end If

la mise en oeuvre

L'implémentation de la fonction d'insertion devrait ressembler à ceci -

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty, create root node
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent  = NULL;

      while(1) {                
         parent = current;

         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }
			
         //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

Opération de recherche

Chaque fois qu'un élément doit être recherché, commencez la recherche à partir du nœud racine, puis si les données sont inférieures à la valeur de clé, recherchez l'élément dans le sous-arbre de gauche. Sinon, recherchez l'élément dans le sous-arbre de droite. Suivez le même algorithme pour chaque nœud.

Algorithme

If root.data is equal to search.data
   return root
else
   while data not found

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
         
      If data found
         return node
   endwhile 
   
   return data not found
   
end if

L'implémentation de cet algorithme devrait ressembler à ceci.

struct node* search(int data) {
   struct node *current = root;
   printf("Visiting elements: ");

   while(current->data != data) {
      if(current != NULL)
      printf("%d ",current->data); 
      
      //go to left tree

      if(current->data > data) {
         current = current->leftChild;
      }
      //else go to right tree
      else {                
         current = current->rightChild;
      }

      //not found
      if(current == NULL) {
         return NULL;
      }

      return current;
   }  
}

Pour connaître la mise en œuvre de la structure de données de l'arborescence de recherche binaire, veuillez cliquer ici .