Tutoriel de structure de données d'arbre pour les débutants

Introduction

Un arbre en logiciel est comme un arbre biologique, mais avec les différences suivantes:

• Il est tiré à l'envers.
• Il n'a qu'une seule racine et pas de tige.
• Les branches émergent de la racine.
• Un point où une branche décolle d'une autre branche ou la racine est appelée le nœud.
• Chaque nœud a une valeur.

Les branches de l'arborescence du logiciel sont représentées par des lignes droites. Un bon exemple d'arbre de logiciel que vous pourriez avoir utilisé est l'arbre de répertoire du disque dur de votre ordinateur.

Il existe différents types d'arbres. Il y a l'arbre général à partir de laquelle d'autres arbres dérivent. D'autres arbres sont dérivés en introduisant des contraintes dans l'arbre général. Par exemple, vous voudrez peut-être un arbre où pas plus de deux branches émanent d'un nœud; Un tel arbre serait appelé un arbre binaire. Cet article décrit l'arbre général et comment accéder à tous ses nœuds.

L'hyperlien pour télécharger le code est donné en bas de cet article.

Pour comprendre les échantillons de code dans cet article, vous devez avoir des connaissances de base en JavaScript (ECMAScript). Si vous n'avez pas ces connaissances, vous pouvez l'obtenir à partir de http: // www.en réseau.com / chrysanthusforcha-1 / ecmascript-2015-cours.htm

Le diagramme des arbres généraux

«A» est le nœud racine; c'est le nœud de premier niveau. B, C, D sont sur la deuxième ligne; Ce sont des nœuds de deuxième niveau. E, F, G, H, I, J, K sont sur la troisième ligne, et ce sont des nœuds de troisième niveau. Une quatrième ligne aurait produit des nœuds de quatrième niveau, et ainsi de suite.

Propriétés des arbres

- Toutes les branches pour tous les niveaux de nœuds ont une source, qui est le nœud racine.

- Un arbre a n - 1 branches, où n est le nombre total de nœuds. Le diagramme ci-dessus pour l'arbre général a 11 nœuds et 10 branches.

- Contrairement aux humains, où chaque enfant a deux parents, avec l'arbre du logiciel, chaque enfant n'a qu'un seul parent. Le nœud racine est le plus grand parent d'ancêtre. Un parent peut avoir plus d'un enfant. Chaque nœud, à l'exception du nœud racine, est un enfant.

Vocabulaire des arbres

• Noeud principal: C'est le nœud le plus élevé de l'arbre, et il n'a pas de parent. Tous les autres nœuds ont un parent.
• Nœuds de feuilles: Un nœud feuille est un nœud qui n'a pas d'enfant. Ils sont généralement au fond de l'arbre et sont parfois sur les côtés gauche et / ou droit de l'arbre.
• Clé: C'est la valeur d'un arbre. Cela peut être un nombre; Il peut s'agir d'une chaîne; il peut même être un opérateur tel que + ou - ou x.
• Les niveaux: Le nœud racine est au premier niveau. Ses enfants sont au deuxième niveau; Les enfants des nœuds de deuxième niveau sont au troisième niveau, et ainsi de suite.
• Node parent: Chaque nœud, à l'exception du nœud racine, a un nœud parent qui lui est connecté par une branche. Tout nœud, à l'exception du nœud racine, est un nœud enfant.
• Nœuds de frères et sœurs: Les nœuds de frères et sœurs sont des nœuds qui ont le même parent.
• Chemin: Les branches (lignes droites) qui connectent un nœud à un autre, à travers d'autres nœuds, forment un chemin. Les branches peuvent ou non être des flèches.
• Node d'ancêtre: Tous les nœuds supérieurs connectés à un enfant, y compris le parent et le nœud racine, sont des nœuds d'ancêtre.
• Node descendant: Tous les nœuds inférieurs connectés à un nœud, jusqu'à des feuilles connectées, sont des nœuds descendants. Le nœud en question ne fait pas partie des nœuds descendant. Le nœud en question, ne doit pas être le nœud racine.
• Subtree: Un nœud plus tous ses descendants jusqu'aux feuilles apparentées, forment un sous-arbre. Le nœud de départ est inclus et il n'est pas nécessaire que ce soit la racine; Sinon, ce serait l'arbre entier.
• Degré: Le nombre d'enfants d'un nœud est appelé le degré du nœud.

Traverser tous les nœuds d'un arbre

Tous les nœuds d'un arbre sont accessibles pour lire ou modifier toute valeur du nœud. Cependant, cela ne se fait pas arbitrairement. Il y a trois façons de le faire, qui impliquent toutes une traversée en profondeur d'abord comme suit:

1) Ordre: Autrement dit, dans ce schéma, le sous-arbre gauche est traversé en premier; Ensuite, le nœud racine est accessible; Ensuite, le sous-arbre droit est traversé. Ce schéma est symbolisé comme gauche-> root-> à droite. La figure 1 est redéfinie ici pour une référence facile:

En supposant qu'il y a deux frères et sœurs par nœud; puis gauche-> root-> droit à droite, vous accédez d'abord au nœud le plus bas et le plus à gauche, puis le parent du nœud, puis le frère droit. Lorsqu'il y a plus de deux frères et sœurs, prenez le premier comme la gauche et le reste des nœuds de droite, comme droit. Pour l'arborescence générale ci-dessus, le sous-arbre inférieur gauche est accessible pour avoir, [EBF]. C'est un sous-arbre. Le parent de ce sous-arbre est un; Ainsi, A est ensuite accessible pour avoir [EBF] A. Ensuite, le sous-arbre [GCHI] est accessible pour avoir un sous-arbre plus grand, [[EBF] A [GCHI]]. Vous pouvez voir le profil gauche-> root-> droit se décrivant. Ce grand sous-arbre gauche aura le sous-arbre, [JDK] à sa droite pour terminer la traversée pour obtenir, [[eBf] a [gchi]] [JDK].

2) Pré-commande: Autrement dit, dans ce schéma, le nœud racine est accessible d'abord, puis le sous-arbre gauche est traversé ensuite, puis le sous-arbre droit est traversé. Ce schéma est symbolisé comme root-> gauche-> à droite. La figure 1 est redéfinie ici pour une référence facile.

En supposant qu'il y a deux frères et sœurs par nœud; puis root-> gauche-> droite signifie, vous accédez d'abord à la racine, puis à l'enfant immédiat gauche, puis à l'enfant immédiat droit. Lorsqu'il y a plus de deux frères et sœurs, prenez le premier comme la gauche et le reste des nœuds de droite, comme droit. L'enfant le plus à gauche de l'enfant de gauche est le suivant à être accessible. Pour l'arbre général ci-dessus, le sous-arbre racine est [ABCD]. À gauche de ce sous-arbre, vous avez le sous-arbre, [EF], donnant la séquence d'accès, [ABCD] [EF]. À droite de ce sous-arbre plus grand, vous avez deux sous-arbres, [Ghi] et [JK], donnant la séquence complète, [ABCD] [EF] [GHI] [JK]. Vous pouvez voir la racine-> gauche-> profil droit se décrivant.

3) Ordre: Ordre: Autrement dit, dans ce schéma, le sous-vtree gauche est en premier traversé, puis le sous-arbre droit est traversé, puis la racine est accessible. Ce schéma est symbolisé comme gauche-> droite-> racine. La figure 1 est redéfinie ici pour une référence facile.

Pour cet arbre, les sous-arbres sont [[EFB], [GHIC], [JKD] et [A] qui forment la séquence, [EFB], [GHIC], [JKD] [A]. Vous pouvez voir le profil root gauche-> droit se décrivant.

Créer l'arbre

L'arbre ci-dessus sera créé à l'aide d'Ecmascript, qui est comme la dernière version de JavaScript. Chaque nœud est un tableau. Le premier élément de chaque tableau de nœud est le parent du nœud, un autre tableau. Les autres éléments du nœud sont les enfants du nœud, à partir de l'enfant le plus à gauche. Il existe une carte ECMAScript qui relie chaque tableau à sa chaîne (lettre) correspondante. Le premier segment de code est:

O = nouveau Array ();
A = nouveau array ();
B = nouveau array ();
C = nouveau tableau ();
D = nouveau array ();
//feuilles
E = nouveau tableau (b); F = nouveau tableau (b); G = nouveau tableau (c); H = nouveau tableau (c);
I = nouveau tableau (c); J = nouveau tableau (d); K = nouveau tableau (d);
// Ajout du contenu
O [0] = non défini; O [1] = a;
A [0] = o; A [1] = b; A [2] = c; A [3] = D;
B [0] = a; B [1] = e; B [2] = f;
C [0] = a; C [1] = g; C [2] = H; C [3] = i;
D [0] = a; D [1] = J; D [2] = k;
// mappage des objets aux lettres
paires = [[a, 'a'], [b, 'b'], [c, 'c'], [d, 'd'], [e, 'e'], [f, 'f'] , [G, 'g'],
[H, 'h'], [i, 'i'], [j, 'j'], [k, 'k']];
MapoBj = nouvelle carte (paires);

Dans ECMascript, vous pouvez accéder à une fonction définie plus bas dans le programme. Cependant, avec des variables, vous ne pouvez pas faire cela. Vous ne pouvez pas accéder à une variable définie plus bas dans le programme. C'est la raison pour laquelle les variables ci-dessus ont été développées comme indiqué.

Notez également qu'au-dessus du nœud racine A, il y a un autre nœud O (pas zéro). Le premier élément de ce tableau (nœud) n'est pas défini, ce qui signifie que son propre parent n'est pas défini. Le nœud supplémentaire O a été ajouté pour faciliter le code traversant.

Il y a aussi une carte. La carte relie chaque tableau de noms à une lettre, au nom de chaîne correspondant d'une lettre.

Fonction récursive

Pour accéder à tous les éléments d'un arbre, vous avez besoin d'une fonction récursive. Une fonction récursive est une fonction qui continue de s'appeler jusqu'à ce qu'une condition soit remplie.

Visiter un nœud ne signifie pas nécessairement accéder au nœud. Pour accéder à un nœud signifie que sa valeur est lue ou modifiée. Dans les échantillons de code de cet article, l'accès à un nœud signifie lire et afficher la valeur (clé) du nœud. Dans les échantillons de code, un nœud peut être visité plus d'une fois, mais sa valeur n'est accessible qu'une seule fois.

Algorithme et programmation

Il y a un programme pour chacune des trois techniques de traversée.

Algorithme et programmation d'ordre

Ici, le nœud le plus bas et le plus à gauche est visité en premier. Les sous-arbres [EBF], [[EBF] A [GCHI]] et [JDK] sont développés pour donner la séquence complète, [[EBF] A [GCHI]] [JDK].

Il existe deux fonctions récursives pour ce programme, où chacun appelle l'autre. Le principal est appelé fn (nœud). Le programme (code) est court. Téléchargez le fichier combiné ci-dessous pour le codage détaillé.

Les trois programmes ont la même configuration d'arbre à table (nœud).

Algorithme de précommande et programmation

Ici, il n'y a qu'une seule fonction récursive. Il s'appelle, fn (nœud). Ici, les sous-arbres [ABCD], [EF], [GHI] et [JK] sont développés pour donner la séquence complète, [ABCD] [EF] [GHI] [JK]. Le programme pour cela est également court.

Les trois programmes ont la même configuration d'arbre à table (nœud).

Algorithme post-ordre et programmation

Ici, le nœud le plus bas et le plus à gauche est visité en premier. Les sous-arbres [EFB], [GHIC], [JKD] et [A] sont développés pour donner la séquence complète, [EFB], [GHIC], [JKD] [A] .

Il existe deux fonctions récursives pour ce programme, où chacun appelle l'autre. Le principal est appelé fn (nœud). Le programme pour cela est également court. Téléchargez le fichier combiné ci-dessous pour le codage détaillé.

Les trois programmes ont la même configuration d'arbre à table (nœud).

Types d'arbres

Les arbres de programmation informatique sont en fait des structures de données non linéaires. Les structures de données linéaires sont des listes, des tableaux, des piles, des files d'attente, des piles, etc. Un arbre avec n nœuds a des branches n-1. Lorsque le nombre de branches est égal ou supérieur au nombre de nœuds, un graphique est obtenu. Un graphique n'est pas vraiment un arbre.

Il y a des arbres de logiciels, qui décrivent des dispositions, comme l'arbre d'annuaire dans le disque dur d'un ordinateur. De nombreux arbres ne décrivent pas du tout les dispositions existantes. En fait, ils décrivent des algorithmes. Par exemple, l'algorithme mathématique (x + y) x (x-y) est décrit par un arbre où x est le nœud racine, alors + et - sont des nœuds enfants immédiats de la racine. x et y sont des nœuds d'enfants de +. x et y sont à nouveau des nœuds d'enfants de -. Un tel arbre est connu comme un arbre d'expression.

De nombreux types d'arbres différents peuvent être classés en différents titres; comme l'arbre binaire, le b-are, l'expression arbre, etc. Tous sont dérivés de l'arbre général.

Certaines des catégories d'arbres sont divisées en catégories supplémentaires. L'arbre binaire par exemple a au moins l'arbre de recherche binaire, l'arbre AVL et l'arbre cartésien.

Téléchargement

Trois programmes ont été fournis pour cet article. Il existe un programme pour la technique en ordre (algorithme), un autre pour la technique de précommande, et encore une autre pour la technique post-ordre. Tous ont été placés dans un fichier zip, appelé traversant. Le fichier zip peut être téléchargé à: github.

Conclusion

Un arbre de logiciel est comme un arbre normal dans le parc ou dans la forêt. Cependant, l'arbre de programmation informatique est à l'envers. Il existe différents types d'arbres. D'autres arbres sont dérivés en introduisant des contraintes dans l'arbre général. Tous les nœuds d'un arbre sont accessibles à l'aide d'un algorithme en ordre, pré-commande ou post-ordre. Une arborescence de logiciels peut être produite par n'importe quel langage informatique. Ecmascript a été choisi ici car c'est le langage informatique le plus simple. Le prochain type d'arbre que vous devez étudier est l'arbre binaire car c'est la structure des données de l'arbre la plus populaire.