Menu

Arbres en C ++: terminologie de base, techniques de traversée et types d'arbres C ++

  • Principal
  • Autre
  • Arbres en C ++: terminologie de base, techniques de traversée et types d'arbres C ++

trees c basic terminology

Essayez Notre Instrument Pour Éliminer Les Problèmes

Ce didacticiel détaillé sur les arbres C ++ explique les types d'arbres, les techniques de traversée des arbres et la terminologie de base avec des images et des exemples de programmes:

Dans cette série C ++, jusqu'à présent, nous avons vu la structure de données linéaire de nature à la fois statique et dynamique. Nous allons maintenant passer à la structure de données non linéaire. La première structure de données de cette catégorie est «Arbres».

Les arbres sont des structures de données hiérarchiques non linéaires. Un arbre est un ensemble de nœuds connectés les uns aux autres au moyen de «bords» qui sont soit dirigés soit non dirigés. L'un des nœuds est désigné comme «nœud racine» et les nœuds restants sont appelés nœuds enfants ou nœuds feuilles du nœud racine.

En général, chaque nœud peut avoir autant d'enfants mais un seul nœud parent.

=> Découvrez toute la série de formations C ++

Arborescence en C ++

Les nœuds d'un arbre sont soit au même niveau appelés nœuds soeurs, soit ils peuvent avoir une relation parent-enfant. Les nœuds avec le même parent sont des nœuds frères.

Ce que vous apprendrez:

Arbres en C ++

Vous trouverez ci-dessous un exemple d'arbre avec ses différentes parties.

Arbre en C ++ avec ses différentes parties

Passons en revue les définitions de certains termes de base que nous utilisons pour les arbres.

  • Noeud principal: Il s'agit du nœud le plus élevé de la hiérarchie de l'arborescence. Dans le diagramme ci-dessus, le nœud A est le nœud racine. Notez que le nœud racine n'a aucun parent.
  • Noeud feuille: C'est le nœud le plus bas d'une hiérarchie arborescente. Les nœuds feuilles sont les nœuds qui n'ont aucun nœud enfant. Ils sont également appelés nœuds externes. Les nœuds E, F, G, H et C dans l'arborescence ci-dessus sont tous des nœuds feuilles.
  • Sous-arbre: Le sous-arbre représente divers descendants d'un nœud lorsque la racine n'est pas nulle. Un arbre se compose généralement d'un nœud racine et d'un ou plusieurs sous-arbres. Dans le diagramme ci-dessus, (B-E, B-F) et (D-G, D-H) sont des sous-arbres.
  • Noeud parent: Tout nœud à l'exception du nœud racine qui a un nœud enfant et une arête vers le haut vers le parent.
  • Nœud ancêtre: Il s'agit de n'importe quel nœud prédécesseur sur un chemin allant de la racine à ce nœud. Notez que la racine n'a aucun ancêtre. Dans le diagramme ci-dessus, A et B sont les ancêtres d'E.
  • Clé: Il représente la valeur d'un nœud.
  • Niveau: Représente la génération d'un nœud. Un nœud racine est toujours au niveau 1. Les nœuds enfants de la racine sont au niveau 2, les petits-enfants de la racine sont au niveau 3 et ainsi de suite. En général, chaque nœud est à un niveau supérieur à son parent.
  • Chemin: Le chemin est une séquence d'arêtes consécutives. Dans le diagramme ci-dessus, le chemin vers E est A => B-> E.
  • Degré: Le degré d'un nœud indique le nombre d'enfants qu'un nœud a. Dans le diagramme ci-dessus, le degré de B et D est de 2 chacun tandis que le degré de C est de 0.

Types d'arbres C ++

La structure de données arborescente peut être classée dans les sous-types suivants, comme illustré dans le diagramme ci-dessous.

Types d

# 1) Arbre général

L'arbre général est la représentation de base d'un arbre. Il a un nœud et un ou plusieurs nœuds enfants. Le nœud de niveau supérieur, c'est-à-dire le nœud racine, est présent au niveau 1 et tous les autres nœuds peuvent être présents à différents niveaux.

Un arbre général est illustré dans la figure ci-dessous.

Arbre général

Comme le montre la figure ci-dessus, un arbre général peut contenir n'importe quel nombre de sous-arbres. Les nœuds B, C et D sont présents au niveau 2 et sont des nœuds frères. De même, les nœuds E, F, G et H sont également des nœuds frères.

Les nœuds présents à différents niveaux peuvent présenter une relation parent-enfant. Dans la figure ci-dessus, les nœuds B, C et D sont des enfants de A. Les nœuds E et F sont des enfants de B tandis que les nœuds G et H sont des enfants de D.

L'arborescence générale est illustrée ci-dessous à l'aide de l'implémentation C ++:

#include using namespace std; //declaration for new tree node struct node { int data; struct node *left; struct node *right; }; //allocates new node struct node* newNode(int data) { // declare and allocate new node struct node* node = new struct node(); node->data = data; // Assign data to this node // Initialize left and right children as NULL node->left = NULL; node->right = NULL; return(node); } int main() { /*create root node*/ struct node *rootNode = newNode(10); cout<<'General tree created is as follows:'<data<left = newNode(20); rootNode->right = newNode(30); cout<<' '<left->data<<' '<right->data; cout<left->left = newNode(40); cout<<' '<<'/'<left->left->data; return 0; }

Production:

L'arborescence générale créée est la suivante:

dix

/

20 30

/

40

# 2) Forêts

Chaque fois que nous supprimons le nœud racine de l'arbre et les arêtes joignant les éléments de niveau suivant et la racine, nous obtenons des ensembles d'arbres disjoints comme indiqué ci-dessous.

Les forêts

Dans la figure ci-dessus, nous avons obtenu deux forêts en supprimant le nœud racine A et les trois arêtes qui connectaient le nœud racine aux nœuds B, C et D.

programmes qui utilisent C ++

# 3) Arbre binaire

Une structure de données arborescente dans laquelle chaque nœud a au plus deux nœuds enfants est appelée un arbre binaire. Un arbre binaire est la structure de données arborescente la plus populaire et est utilisé dans une gamme d'applications telles que l'évaluation d'expression, les bases de données, etc.

La figure suivante montre un arbre binaire.

Arbre binaire

Dans la figure ci-dessus, nous voyons que les nœuds A, B et D ont chacun deux enfants. Un arbre binaire dans lequel chaque nœud a exactement zéro ou deux enfants est appelé un arbre binaire complet. Dans cette arborescence, aucun nœud n'a un enfant.

Un arbre binaire complet a un arbre binaire qui est complètement rempli à l'exception du niveau le plus bas qui est rempli de gauche à droite. L'arbre binaire illustré ci-dessus est un arbre binaire complet.

Voici un programme simple pour illustrer un arbre binaire. Notez que la sortie de l'arborescence est la séquence de traversée dans l'ordre de l'arborescence d'entrée.

#include using namespace std; struct bintree_node{ bintree_node *left; bintree_node *right; int data; } ; class bst{ bintree_node *root; public: bst(){ root=NULL; } int isempty() { return(root==NULL); } void insert(int item); void displayBinTree(); void printBinTree(bintree_node *); }; void bst::insert(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL){ parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bst::displayBinTree(){ printBinTree(root); } void bst::printBinTree(bintree_node *ptr){ if(ptr!=NULL){ printBinTree(ptr->left); cout<<' '<data<<' '; printBinTree(ptr->right); } } int main(){ bst b; b.insert(20); b.insert(10); b.insert(5); b.insert(15); b.insert(40); b.insert(45); b.insert(30); cout<<'Binary tree created: '<

Production:

Arbre binaire créé:

5 10 15 20 30 40 45

# 4) Arbre de recherche binaire

L'arbre binaire qui est ordonné s'appelle l'arbre de recherche binaire. Dans un arbre de recherche binaire, les nœuds à gauche sont inférieurs au nœud racine tandis que les nœuds à droite sont supérieurs ou égaux au nœud racine.

Un exemple d'arbre de recherche binaire est présenté ci-dessous.

Arbre de recherche binaire

Dans la figure ci-dessus, nous pouvons voir que les nœuds de gauche sont tous inférieurs à 20, ce qui est l'élément racine. Les bons nœuds, en revanche, sont plus grands que le nœud racine. L'arbre de recherche binaire est utilisé dans les techniques de recherche et de tri.

# 5) Arbre d'expression

Un arbre binaire utilisé pour évaluer des expressions arithmétiques simples est appelé un arbre d'expression.

Un arbre d'expression simple est présenté ci-dessous.

Arbre d

Dans l'exemple d'arbre d'expression ci-dessus, nous représentons l'expression (a + b) / (a-b). Comme le montre la figure ci-dessus, les nœuds non-feuilles de l'arborescence représentent les opérateurs de l'expression tandis que les nœuds feuilles représentent les opérandes.

Les arbres d'expressions sont principalement utilisés pour résoudre des expressions algébriques.

Techniques de traversée des arbres

Nous avons vu des structures de données linéaires comme des tableaux, des listes chaînées, des piles, des files d'attente, etc. Toutes ces structures de données ont une technique de traversée commune qui ne traverse la structure que d'une seule manière, c'est-à-dire linéairement.

qu'est-ce qu'un fichier .bin?

Mais dans le cas des arbres, nous avons différentes techniques de traversée énumérées ci-dessous:

# 1) Dans l'ordre: Dans cette technique de traversée, nous traversons d'abord le sous-arbre gauche jusqu'à ce qu'il n'y ait plus de nœuds dans le sous-arbre gauche. Après cela, nous visitons le nœud racine, puis nous traversons le sous-arbre droit jusqu'à ce qu'il n'y ait plus de nœuds à traverser dans le sous-arbre droit. Ainsi, l'ordre de traversée inOrder est gauche-> racine-> droite.

# 2) Pré-commande: Pour la technique de traversée de pré-ordre, nous traitons d'abord le nœud racine, puis nous traversons tout le sous-arbre gauche et enfin, nous traversons le sous-arbre droit. Par conséquent, l'ordre de traversée des pré-ordres est racine-> gauche-> droite.

# 3) Post-commande: Dans la technique de traversée post-ordre, nous traversons le sous-arbre gauche, puis le sous-arbre droit et enfin le nœud racine. L'ordre de traversée pour la technique de post-ordre est gauche-> droite-> racine.

Si n est le nœud racine et «l» et «r» sont respectivement les nœuds gauche et droit de l’arbre, alors les algorithmes de traversée de l’arbre sont les suivants:

Dans l'ordre (lnr) algorithme:

  1. Traversez le sous-arbre gauche en utilisant inOrder (gauche-sous-arbre).
  2. Visitez le nœud racine (n).
  3. Traverser le sous-arbre droit en utilisant inOrder (sous-arbre droit).

Algorithme de précommande (nlr):

  1. Visitez le nœud racine (n).
  2. Traversez le sous-arbre gauche en utilisant le précommande (sous-arbre gauche).
  3. Parcourez le sous-arbre droit en utilisant le précommande (sous-arbre droit).

Algorithme de post-commande (lrn):

  1. Traversez le sous-arbre gauche à l'aide de postOrder (sous-arbre gauche).
  2. Parcourez le sous-arbre droit à l'aide de postOrder (sous-arbre droit).
  3. Visitez le nœud racine (n).

À partir des algorithmes ci-dessus des techniques de traversée, nous voyons que les techniques peuvent être appliquées à un arbre donné de manière récursive pour obtenir le résultat souhaité.

Considérez l'arbre suivant.

Algorithme de post-commande (LRN)

En utilisant les techniques de parcours ci-dessus, la séquence de parcours de l'arbre ci-dessus est donnée ci-dessous:

  1. Traversée InOrder: 2 3 5 6 10
  2. Traversée de la pré-commande: 6 3 2 5 10
  3. Traversée PostOrder: 2 5 3 10 6

Conclusion

Les arbres sont une structure de données hiérarchique non linéaire qui est utilisée dans de nombreuses applications du domaine logiciel.

Contrairement aux structures de données linéaires qui n'ont qu'un seul moyen de parcourir la liste, nous pouvons parcourir les arbres de différentes manières. Nous avons eu une étude détaillée des techniques de traversée et des différents types d'arbres dans ce tutoriel.

=> Jetez un œil au guide du débutant C ++ ici

lecture recommandée

^