Traversion de la précommande des arbres binaires en java

Un arbre en informatique est comme un arbre dans la forêt, mais il n'a pas de tige. C'est à l'envers. Il a des branches et des nœuds. Il n'y a qu'une seule racine, qui est un nœud. Les nœuds sont liés par des branches simples de haut en bas. Il n'y a pas de liaison horizontalement. Le diagramme suivant est un exemple d'arbre.

C'est en fait un arbre binaire. Un arbre binaire est un arbre où chaque nœud a au plus deux nœuds d'enfants. Si un nœud n'a qu'un seul nœud enfant, ce nœud doit être fait le nœud gauche. S'il a les deux enfants, il y a un nœud gauche et un nœud droit.

Vocabulaire des arbres

L'explication de la traversée des arbres se fait en utilisant le vocabulaire des arbres.

Noeud principal: Chaque nœud d'un arbre a un parent sauf le nœud racine.
Nœuds de feuille: Les nœuds de fin sont des nœuds de feuilles. Un nœud feuille n'a pas d'enfant.
Clé: C'est la valeur d'un nœud. Il peut s'agir d'une valeur de type de données primitive ou d'un caractère. Il peut également être un opérateur, e.g., + ot - .
Les niveaux: Un arbre est organisé en niveaux, avec le nœud racine au premier niveau. Les nœuds peuvent être imaginés à des niveaux horizontaux. L'arbre ci-dessus a quatre niveaux.
Nœud parent: Le nœud racine est le seul nœud qui n'a pas de parent. Tout autre nœud a un nœud parent.
Nœuds de frères: Les enfants d'un nœud particulier sont des nœuds de frères et sœurs.
Chemin: Un chemin est une chaîne de nœuds et leurs branches uniques.
Nœud 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.
Nœud descendant: Tous les nœuds inférieurs, connectés à un nœud particulier, jusqu'à des feuilles connectés, 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.
Sous-arbre: Un nœud plus tous ses descendants, jusqu'aux feuilles associé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 nœud d'un arbre binaire peut avoir un ou deux enfants. Si un nœud a un enfant, son diplôme est censé être un. S'il a deux enfants, son diplôme serait deux.

Cet article explique comment traverser un arbre binaire de manière pré-commande, en utilisant la langue java.

Contenu de l'article

• Modèle de traversée
• L'approche de traversée illustrée
• Cours Java
• La méthode principale ()
• Conclusion

Modèle de traversée

Ordres

Le plus petit sous-arbre typique d'un arbre binaire se compose d'un nœud parent et de deux nœuds d'enfants. Les nœuds d'enfants sont des frères et sœurs composés du nœud enfant gauche et du nœud enfant droit. Un nœud enfant droit peut être absent.

Pré-commander

Le nœud parent est visité d'abord avec cet ordre, puis le nœud gauche, puis le nœud droit. Si le nœud de gauche a son propre sous-arbre, alors tous les nœuds de sous-arbre seront visités avant le nœud droit. Si le nœud droit a son propre sous-arbre, alors tout son sous-arbre sera visité enfin. En visitant un sous-arbre, le schéma de précommande de la parent-gauche-droite est suivi pour chaque triangle de trois nœuds. Si un nœud n'a qu'un seul enfant, ce qui signifie qu'il n'y a pas de véritable triangle, le seul enfant doit être considéré comme le nœud de gauche tandis que le nœud droit est absent.

Post-ordre

Le nœud gauche est visité d'abord avec cet ordre, puis le nœud droit, puis le nœud parent. Si le nœud de gauche a son propre sous-arbre, alors tous les nœuds de sous-arbre seront visités avant le nœud droit. Si le nœud droit a son propre sous-arbre, alors tout son sous-arbre sera visité deuxièmement avant la visite du parent. En visitant un sous-arbre, le schéma post-ordre du parent gauche-droit est suivi pour chaque triangle de trois nœuds.

En ordre

Le nœud gauche est visité d'abord avec cet ordre, puis le nœud parent, puis le nœud droit. Si le nœud de gauche a son propre sous-arbre, tous les nœuds de sous-arbre seront visités avant la visite du nœud parent. Si le nœud droit a son propre sous-arbre, alors tout son sous-arbre sera visité enfin. En visitant un sous-arbre, le schéma en ordre de la droite gauche est suivi pour chaque triangle de trois nœuds.

Dans cet article, seul le schéma de précommande est illustré.

Récursivité ou itération

Le schéma de précommande peut être mis en œuvre en utilisant une récursivité ou une itération. Dans cet article, la seule récursion est illustrée.

L'approche de traversée illustrée

Dans cet article, le schéma de précommande et la récursivité sont utilisés. Le diagramme ci-dessus sera utilisé. Le diagramme a été remis en place ici pour une référence facile:

Dans cette section, ce diagramme est utilisé pour montrer la séquence de valeurs (lettres) qui sont affichées (consultées), en utilisant le schéma de précommande et la récursivité. Les lettres a, b, c, etc., sont les valeurs (clés) des différents nœuds.

L'accès à la précommande à l'arbre commence à partir de la racine. Donc a est accès d'abord. A a deux enfants: B (à gauche) et C (à droite). La précommande est parent-left-droite. Donc b est accessible ensuite. Si B n'avait jamais eu d'enfants, alors C aurait été accessible ensuite. Puisque B a des enfants: D (à gauche) et E (à droite), son enfant gauche doit être accessible ensuite. Rappelez-vous que la précommande est parent-left-droite. Après B, le parent a été accessible, son enfant gauche, D, doit être accessible ensuite, conformément à la parent-leftcild-rightchild.

Le triangle du nœud parent, B, est BDE. Dans ce triangle, le nœud parent, suivi du nœud gauche-enfant, vient d'être accessible. L'accès à tous les nœuds du triangle doit être achevé en premier. Ainsi, le nœud suivant à accéder est le bon enfant du nœud B, qui est e.

Maintenant, le triangle BDE est un sous-arbre, qui est conduit par le nœud B. À ce stade, le nœud B et son triangle ont été complètement accessibles. Le nœud B est l'enfant gauche du nœud A. L'accès du nœud B et de son sous-arbre vient d'être terminé. Après le parent-left-droit, après l'enfant de gauche, le nœud B a été accessible, l'enfant droit de parent a, c, doit être accessible ensuite.

Le triangle que C mène est CFG. C est le parent, F est l'enfant gauche, et g est l'enfant droit. Ainsi, dès que C a été accessible, F doit être accessible en fonction de la règle parentale-droite. F a également un enfant, H. Ainsi, dès que F a été accessible, son enfant gauche, H, doit être accessible par la règle parent-gauche-droite.

Après cela, F et son sous-arbre auraient été complètement accessibles. À ce stade, il n'y aurait pas de question à nouveau d'accéder à F. F est l'enfant gauche de C, qui a un enfant droit, g. Après l'enfant de gauche, F a été complètement accessible, l'enfant droit, G, doit ensuite être accessible par la règle parent-gauche-droite.

Et donc la séquence d'accès est: abdecfhg.

Cours Java

L'arbre est redéfini ici pour une référence facile:

Nœud

lettre) du nœud. Il devrait également avoir deux autres propriétés nommées à gauche et à droite. La propriété gauche se verra attribuer un nœud enfant si le nœud a un enfant gauche. La bonne propriété se verra attribuer le nœud enfant «A» si le nœud a un bon enfant «A».

La classe de nœud a besoin d'un constructeur qui créera l'objet de nœud et affectera une valeur à la clé. Le code de la classe est:

classe node
CLÉ CHAR;
Nœud gauche, à droite;
Node public (valeur char)
key = valeur;
gauche = droite = null;

Lorsqu'un nœud vient d'être créé, il n'a pas d'enfant. C'est pourquoi les propriétés gauche et droite sont attribuées nuls. Dans la méthode principale (), si un nœud particulier a un enfant gauche, l'enfant sera créé et affecté à la propriété gauche du nœud particulier. Si un nœud particulier a un bon enfant, l'enfant sera créé et affecté à la bonne propriété du nœud particulier.

La classe d'arbre

Le code de la classe d'arborescence est:

classe binarytree
Racine de nœud;
BinaryTree ()
root = null;

La classe d'arbre indique la racine. Il a une propriété appelée racine, qui est pour le nœud racine. Il a un constructeur sans aucun paramètre. Ce constructeur attribue nul à la racine. Lorsqu'un arbre est juste créé, il n'a pas de nœud, et c'est pourquoi la racine de propriété est nul. Le premier nœud créé sera le nœud racine, et il sera affecté à cette propriété, racine. De là, l'arbre se développera dans la méthode principale () (voir ci-dessous).

La classe BinaryTree a les méthodes, précommande () et main () voir ci-dessous.

La méthode de précommande

C'est le cœur du programme, bien que la méthode principale () soit également importante. La méthode de précommande implémente la règle parent-leftchild-rightchild. Ceci est une fonction récursive, dont le code est:

vide précommande (nœud nœud)
if (node ​​== null)
retour;
// accéder au nœud parent
Système.dehors.imprimer (nœud.clé + "->");
// accéder à l'enfant gauche
précommande (nœud.gauche);
// accéder au bon enfant
précommande (nœud.droite);

À la fin de la traversée des arbres, aucun nœud ne traversera, donc la valeur de tout nœud sera nul. Cela explique la première instruction de la fonction de précommande. La deuxième instruction imprime la clé du nœud actuel. La troisième instruction rappelle la même fonction de précommande avec le nœud enfant gauche. La prochaine et dernière déclaration rappelle la fonction de précommande avec le bon nœud enfant. De cette façon, l'arbre entier est traversé.

En affichant la séquence, a-> b-> d, après que b a été accessible: «Préortif (nœud.à droite) ”est appelé pour le nœud C mais réservé. Une fois que D a été accessible, «Précommande (nœud.à droite) »est appelé pour le nœud e. L'appel pour le nœud C, qui a été réservé, est exécuté après cela. Cette explication s'applique à la branche droite de l'arbre entier.

Et donc la séquence de sortie doit être: a-> b-> d-> e-> c-> f-> h-> g .

La méthode principale ()

La méthode principale construit l'arbre en attribuant de nouveaux nœuds avec leurs clés à la propriété gauche ou droite d'un nœud parent. Tout d'abord, un arbre vide est créé. À la fin de la méthode principale (), la méthode de précommande est appelée une fois. Puisqu'il s'agit d'une fonction récursive, elle continuera de s'appeler jusqu'à ce que l'arbre entier soit traversé. Le code est:

public static void main (String [] args)
// Créer un objet d'arbre sans aucun nœud
BinaryTree Tree = new BinaryTree ();
// Créer des nœuds pour l'arbre
arbre.root = nouveau nœud ('a');
arbre.racine.Left = new nœud ('b');
arbre.racine.droit = ​​nouveau nœud ('c');
arbre.racine.gauche.Left = new nœud ('d');
arbre.racine.gauche.droite = nouveau nœud ('e');
arbre.racine.droite.Left = new nœud ('f');
arbre.racine.droite.droite = nouveau nœud ('g');
arbre.racine.droite.gauche.Left = new nœud ('h');
// Traversé de l'arbre précommande
Système.dehors.println ("Traversal de précommande");
arbre.précommande (arbre.racine);
Système.dehors.println ();

Tous les codes ci-dessus peuvent être assemblés en un seul programme pour tester.

La sortie est:

A-> b-> d-> e-> c-> f-> h-> g->

Le dernier -> peut être ignoré.

Conclusion

La traversée de précommande binaire de l'arbre en Java, qui utilise la récursivité, a deux classes. Il a la classe de nœuds et la classe BinaryTree. La classe de nœuds a une propriété pour la clé. Il a également deux propriétés de nœud pour le nœud enfant gauche et le nœud enfant droit. La classe BinaryTree a deux méthodes: la méthode précommande () et la méthode principale (). La méthode de précommande () implémente le schéma parent-leftchild-rightchild récursivement. La méthode principale () construit l'arbre en attribuant de nouveaux nœuds avec leurs clés en tant qu'enfants gauche et droite aux nœuds parentaux.

Le problème avec l'algorithme récursif pour la précommande est que si l'arbre est trop grand, la mémoire peut devenir courte. Pour résoudre ce problème, utilisez l'algorithme itératif - voir plus tard.