Cet article décrit les algorithmes de traversée de traversée et d'étendue en profondeur et d'étendue qui implémentent l'arbre binaire en Java. Partagez-le pour votre référence, comme suit:
1. Analyse
La pratique courante de la non-réactivité de la profondeur d'abord de la traversée des arbres binaires est d'adopter une pile, et la pratique courante de la non-réactivité de la traversée de largeur est d'adopter une file d'attente.
Profondeur en profondeur d'abord : chaque chemin de branche possible peut être pénétré jusqu'à ce qu'il ne puisse pas être plus profond, et chaque nœud ne peut être accessible qu'une seule fois. Il convient de noter que la pêche en profondeur d'abord de l'arbre binaire est assez spéciale et peut être subdivisée en traversée précommande, traversée intermédiaire et traversée ultérieure. La description spécifique est la suivante:
Traversion de premier ordre : pour tout sous-arbre, accédez d'abord à la racine, puis traversez son sous-arbre gauche, et enfin traverser son sous-arbre droit.
Traversion de l'ordre moyen : pour tout sous-arbre, traversez d'abord son sous-arbre gauche, puis accédez à la racine, et enfin traverser son sous-arbre droit.
Traversion post-ordre : Pour tout sous-arbre, traversez d'abord son sous-arbre gauche, puis traversez son sous-arbre droit et accédez enfin à la racine.
Traversement de l'étendue d'abord : également connu sous le nom de hiérarchie, accédant à chaque couche de haut en bas tour à tour. Dans chaque couche, accédez aux nœuds de gauche à droite (ou de droite à gauche). Après avoir accédé à une couche, vous entrerez la couche suivante jusqu'à ce qu'il n'y ait pas de nœuds accessibles.
2. Donnez des exemples
L'arbre de tri binaire illustré sur la figure ci-dessous nécessite l'utilisation de la traversée précommande (récursive, non réécursive), de traversée en ordre (récursive, non réécursive), de traversée post-ordre (récursive, non réécursive) et de traction de largeur de largeur.
① Code de référence
Package BinaryTreetRaverseTest; Importer Java.util.LinkedList; Importer Java.util.queue; / ** * Profondeur Priority Traversal and LEALTH Priority Traversal of Binary Trees * @Author Fantasy * @version 1.0 2016/10/05 - 2016/10/07 * / public class BinaryTreetratest {public static static void Main (String [] {args) BinarySortTree <Integer> Tree = new BinarySortTree <Integer> (); Tree.InsertNode (35); Tree.InsertNode (20); Tree.insertNode (15); Tree.InsertNode (16); Tree.InsertNode (29); Tree.InsertNode (28); Tree.insertNode (30); arbre.insertNode (40); Tree.insertNode (50); Tree.InsertNode (45); Tree.InsertNode (55); System.out.print ("Transfert de précommande (récursif):"); Tree.PreorderTaverse (arbre.getroot ()); System.out.println (); System.out.print ("Transfert en ordre (récursif):"); Tree.InorderTaverse (Tree.getRoot ()); System.out.println (); System.out.println (); System.out.print ("Transfert post-ordre (récursif):"); Tree.PostorderTraverse (arbre.getroot ()); System.out.println (); System.out.print ("Traversion précursive (non réécursive):"); Tree.PreorderTraversenOreCursion (Tree.getRoot ()); System.out.println (); System.out.print ("Transfert en ordre (non-réécursif):"); Tree.InorderTraversenOreCursion (Tree.getRoot ()); System.out.println (); System.out.println (); System.out.print ("Transfert post-ordre (non réécursif):"); Tree.PostorderTraversenOreCursion (Tree.GetRoot ()); System.out.println (); System.out.print ("Étendue de la traversée:"); Tree.BreadthFirstTaverse (Tree.getRoot ()); }} / ** * Node * / classe Node <E étend comparable <e>> {e valeur; Node <e> gauche; Node <e> à droite; Node (e valeur) {this.value = value; gauche = null; à droite = null; }} / ** * Utilisez une séquence précédente pour construire une arborescence de tri binaire (également connue sous le nom d'un arborescence de recherche binaire) * / class binarysortree <e étend comparable <e>> {nœud privé <e> root; BinarySortTree () {root = null; } public void insertNode (e value) {if (root == null) {root = new node <e> (valeur); retour; } Nœud <e> currentNode = root; while (true) {if (value.compareto (currentNode.value)> 0) {if (currentNode.Right == null) {currentNode.Right = new node <e> (valeur); casser; } currentNode = currentNode.Right; } else {if (currentNode.left == null) {currentNode.Left = new node <e> (valeur); casser; } currentNode = currentNode.Left; }}} Node public <e> getroot () {return root; } / ** * Transfert de précommande de l'arbre binaire (récursif) * @param nœud * / public void preorderTaverse (node <e> node) {System.out.print (node.value + ""); if (node.left! = null) preorderTaverse (node.left); if (node.right! = null) preorderTaverse (node.Right); } / ** * Traversion dans l'ordre de l'arbre binaire (récursif) * @param nœud * / public void inOrderTaverse (node <e> node) {if (node.left! = Null) inOrderTaverse (node.left); System.out.print (Node.Value + ""); if (node.right! = null) inOrderTaverse (node.Right); } / ** * Traversion post-ordre de l'arbre binaire (récursif) * @param nœud * / public void postOrderTaverse (node <e> nœud) {if (node.left! = Null) postorderTaverse (node.left); if (node.right! = null) postOrderTaverse (node.Right); System.out.print (Node.Value + ""); } / ** * Transfert de précommande de l'arbre binaire (non réécursif) * @param root * / public void preorderTraversenorecursion (node <e> root) {LinkedList <node <e>> stack = new LinkedList <node <e>> (); Node <e> currentNode = null; stack.push (root); while (! stack.isempty ()) {currentNode = stack.pop (); System.out.print (currentNode.Value + ""); if (currentNode.Right! = null) stack.push (currentNode.Right); if (currentNode.Left! = null) Stack.push (currentNode.Left); }} / ** * Traversion dans l'ordre de l'arborescence binaire (non-récursive) * @param root * / public void inOrderTaververSenoreCursion (Node <e> root) {LinkedList <node <e>> Stack = new LinkedList <node <e>> (); Node <e> currentNode = root; while (currentNode! = null ||! stack.isempty ()) {// Loop jusqu'à ce que le nœud de feuille le plus à gauche à l'arborescence de tri binaire (CurrentNode est null) while (currentNode! = null) {stack.push (currentNode); currentNode = currentNode.Left; } currentNode = stack.pop (); System.out.print (currentNode.Value + ""); currentNode = currentNode.Right; }} / ** * Traversion post-ordre de l'arbre binaire (non-réécursif) * @param root * / public void postOrderTaververSenoreCursion (Node <e> root) {LinkedList <node <e>> Stack = new LinkedList <node <e>> (); Node <e> currentNode = root; Nœud <e> reightnode = null; while (currentNode! = null ||! stack.isempty ()) {// boucle jusqu'à ce que le nœud de feuille à l'extrémité la plus à gauche de l'arborescence de tri binaire (currentNode est null) while (currentNode! = null) {stack.push (currentNode); currentNode = currentNode.Left; } currentNode = stack.pop (); // Le nœud actuel n'a pas de noeud droit ni le nœud précédent (le nœud qui a été sorti) est le nœud droit du nœud de courant, puis le nœud de courant est sorti pendant (currentNode.Right == NULL || currentNode.Right == RightNode) {System.out.print (CurrentNode.Value + ""); RightNode = currentNode; if (stack.isempty ()) {return; // Sorties racine, les extrémités de traversée} currentNode = stack.pop (); } stack.push (currentNode); // Il y a toujours le bon nœud qui ne traverse pas CurrentNode = currentNode.Right; }} / ** * L'arbre binaire de traversée de largeur de largeur, également connu sous le nom d'arbre binaire de traversée hiérarchique * @param nœud * / public void damphFirstTraverse (nœud <e> root) {queue <nœud <e>> queue = new Linkedlist <node <e>> (); Node <e> currentNode = null; queue.offer (racine); while (! queue.isempty ()) {currentNode = queue.poll (); System.out.print (currentNode.Value + ""); if (currentNode.Left! = null) queue.offer (currentNode.Left); if (currentNode.Right! = null) filed.offer (currentNode.Right); }}}② Résultat de sortie
Traversion précommande (récursif): 35 20 15 16 29 28 30 40 50 45 55
Traversion dans l'ordre (récursivité): 15 16 20 28 29 30 35 40 45 50 55
Traversion post-ordre (récursivité): 16 15 28 30 29 20 45 55 50 40 35
Traversion précommande (non réécursive): 35 20 15 16 29 28 30 40 50 45 55
Traversion dans l'ordre (non réénusive): 15 16 20 28 29 30 35 40 45 50 55
Traversion post-ordre (non réécursive): 16 15 28 30 29 20 45 55 50 40 35
Priorité d'étendue Traversion: 35 20 40 15 29 50 16 28 30 45 55
Pour plus d'informations sur les algorithmes Java, les lecteurs qui sont intéressés par ce site peuvent afficher les sujets: "Structure de données Java et tutoriel d'algorithme", "Résumé des conseils de nœud de Dom Operation Java", "Résumé du fichier Java et des conseils d'opération de répertoire" et "Résumé des conseils d'opération Java Cache"
J'espère que cet article sera utile à la programmation Java de tous.