Structure de données arborescente en C#

1. Structure de données arborescente en C#
2. Étapes pour construire une structure de données arborescente en C#

Les arbres en C# seront le sujet de discussion dans cet article. La structure des données est la première chose que nous devons savoir.

Vous pouvez organiser et stocker vos données sur l’ordinateur en utilisant une structure de données plus efficacement. Les piles, les listes chaînées et les files d’attente sont tous des exemples de structures de données séquentielles.

Structure de données arborescente en C#

Une sorte de données hiérarchiques organisées sous la forme d’un arbre est appelée structure de données arborescente. Il comprend un nœud central, des nœuds structurels et des sous-nœuds reliés entre eux par des arêtes.

Il est également possible d’affirmer que les racines, les branches et les feuilles de la structure de données arborescente sont liées.

Un arbre peut être utilisé pour représenter des données dans une structure hiérarchique. Chaque nœud composant un arbre comprend deux sous-parties : les données et les références.

Le nœud tout en haut de l’arborescence est appelé la racine. Les deux produits directement en dessous sont appelés le sous-arbre gauche et le sous-arbre droit.

Le code pour écrire un nœud d’arbre pourrait ressembler à ceci :

struct node {
  int Data;
  struct node
  *Leftchild;
  struct node
  *Rightchild;
};

Terminologies de base dans la structure de données arborescente en C#

Vous trouverez ci-dessous les terminologies de base que vous devez connaître dans la structure de données arborescente en C# :

• Noeud racine : Le nœud situé au sommet de l’arbre est appelé la racine. Chaque arbre a une seule racine, et une seule route mène de la racine à tout autre noeud.
• Noeud de niveau : Les niveaux des noeuds reflètent le nombre de noeuds qui ont été générés. Les nœuds descendent par incréments de niveau de 1, 2, et ainsi de suite, le nœud racine étant toujours au sommet.
• Noeud de sous-arbre : Les descendants d’un noeud sont représentés par le sous-arbre.
• Noeud parent : Si un noeud autre que la racine est connecté à un noeud parent, il est appelé parent.
• Noeud enfant : Lorsque l’arête d’un nœud descend, on parle de nœud enfant.

Avantages de la structure de données arborescente en C#

Voici deux avantages de l’utilisation de la structure de données arborescente en C# :

1. Il n’est pas nécessaire d’indiquer la taille d’un arbre lorsque vous le comparez à d’autres structures de données, telles que des tableaux ou des listes chaînées. En conséquence, l’arbre est efficace en termes d’espace de stockage.
2. En revanche, travailler avec des arbres élimine le besoin d’opérations à forte intensité de main-d’œuvre telles que l’insertion, la suppression et la recherche de nœuds, qui sont requises par les listes chaînées.

Étapes pour construire une structure de données arborescente en C#

Nous avons ici un exemple de structure de données arborescente en C#. Lisez les étapes ci-dessous pour suivre.

1. Pour commencer, nous devons disposer des bibliothèques suivantes :

   using System;
   using System.Collections.Generic;
   using System.Linq;
   using System.Text;
   using System.Threading.Tasks;
   

2. Créez une classe appelée node dans la classe Shanii qui stocke les variables de type int key, leftn comme nœud gauche et rightn comme nœud droit.

   class node {
     public int key;
     public node leftn, rightn;
   };
   

3. Ensuite, créez un nœud racine et une liste de nœuds appelés z à partir de l’objet d’un nœud.

   static node rootnode = null;
   static List<node> z = new List<node>();
   

4. Pour générer un nœud avec les données, nous devons écrire une fonction appelée newnode qui le fera. Initialement, les deux enfants de ce nouveau nœud sont null.

   static node newnode(int val) {
     node y = new node();
     y.key = val;
     y.leftn = null;
     y.rightn = null;
     return y;
   }
   

5. Maintenant, nous allons voir si le nœud est accessible en utilisant la vérification if. Si oui, alors l’enfant gauche du nœud actuel sera utilisé.

   if (rootnode == null) {
     rootnode = node;
   }
   

6. S’il est disponible, le nœud enfant actuel est utilisé. Étant donné que l’enfant gauche de ce nœud a déjà été utilisé, l’enfant droit est utilisé.

   else if (z[0].leftn == null) {
     z[0].leftn = node;
   }
   

7. L’adresse d’un nœud nouvellement ajouté dans l’arborescence est ajoutée à la file d’attente. Par conséquent, il peut être utilisé pour stocker des informations sur les nœuds de ses enfants.

   else {
     z[0].rightn = node;
     z.RemoveAt(0);
   }
   z.Add(node);
   

8. La classe suivante sera utilisée pour construire un arbre.

   static void Constructtree(int[] ar, int a) {
     for (int i = 0; i < a; i++) InsrtVal(ar[i]);
   }
   

9. La fonction suivante organisera les nœuds selon leur niveau.

   static void OrderData(node root) {}
   

10. Enfin, nous appellerons les fonctions nécessaires pour créer et organiser un arbre et ses paramètres.

    static void Main() {
      int[] array = { 29, 39, 49, 59, 69, 79 };
      int n = array.Length;
      Constructtree(array, n);
      OrderData(rootnode);
      Console.ReadKey();
    }
    

Code source complet :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace tree_example {
  class Shanii {
    class node {
      public int key;
      public node leftn, rightn;
    };
    static node rootnode = null;
    static List<node> z = new List<node>();

    static node newnode(int val) {
      node y = new node();
      y.key = val;
      y.leftn = null;
      y.rightn = null;
      return y;
    }

    static void InsrtVal(int newval) {
      node node = newnode(newval);
      if (rootnode == null) {
        rootnode = node;
      }

      else if (z[0].leftn == null) {
        z[0].leftn = node;
      }

      else {
        z[0].rightn = node;
        z.RemoveAt(0);
      }
      z.Add(node);
    }

    static void Constructtree(int[] ar, int a) {
      for (int i = 0; i < a; i++) InsrtVal(ar[i]);
    }

    static void OrderData(node root) {
      if (root == null)
        return;
      List<node> n = new List<node>();
      n.Add(root);
      while (n.Count > 0) {
        Console.Write(n[0].key + " ");
        if (n[0].leftn != null)
          n.Add(n[0].leftn);
        if (n[0].rightn != null)
          n.Add(n[0].rightn);
        n.RemoveAt(0);
      }
    }

    static void Main() {
      int[] array = { 29, 39, 49, 59, 69, 79 };
      int n = array.Length;
      Constructtree(array, n);
      OrderData(rootnode);
      Console.ReadKey();
    }
  }
}

Production:

29 39 49 59 69 79