Il s'agit d'une question d'entrevue courante, comme l'obtention de la traversée hiérarchique de l'arbre binaire par la précommande et la traversée en ordre de l'arbre binaire, etc.
Précommande + ordre moyen -> Build
Supposons qu'il y ait maintenant un arbre binaire, comme suit:
Pour le moment, l'ordre de traversée est:
Précommande: GDAFEMHZ InOrdre: Adefghmz Postordre: aefdhzmg
Donnez maintenant la précommande et l'ordre (inordre), créez un arbre binaire ou donnez l'ordre (en ordre) et le post-ordre (post-ordre), créez un arbre binaire, c'est en fait le même
Définition du nœud d'arbre:
classe arbre {char val; arbre gauche; arbre droit; arbre (char val, arbre gauche, arbre droit) {this.val = val; this.left = gauche; this.right = droite;} arbre () {} arbre (char val) {this.val = val; this.left = null; this.right = null;}}}Faire des réalisations:
BuildTree d'arborescence statique publique (char [] précommande, char [] inordre) {// La précommande est la séquence de précommande // inordre est la séquence du milieu if (précommande == NULL || précommande.length == 0) {return null;} arbre root = nouveau arbre (précommande [0]); // trouver la position de root dans inordre int inOrderIndex = 0; pour (char i = 0; i <inOrder.length; i ++) {if (inOrder [i] == root.val) {inOrderIndex = i;}} // le sous-arbre gauche et le sous-arbre droit partie de la précommande char [] précommande = arrays.copyofrange (précommande, 1, 1 + inordre); char [] preorderright = arrays.copy. 1 + inOrderIndex, précommande.length); // le sous-arbre gauche et le sous-arbre droit partie d'Ordre Char [] inOrderLeft = Arrays.CopyofRange (InOrder, 0, inOrderIndex); char [] inOrderRight = Arrays.CopyofRaye (inordre, Ordrendex + 1, inordre. BuildTree (précommandetleft, inOrderLeft); Tree RightChild = BuildTree (précommanderight, inOrderRight); root.left = LeftChild; root.Right = RightChild; return root;}Il est en fait de la même manière de créer un ordre moyen + post-ordre. Je ne l'écrirai pas ici
Diverses traversées
Traversion post-ordre
public static void PostOrderPrint (root d'arbre) {// Traversal ultérieur // Racines gauche et droite gauche if (root.left! = null) {postOrderPrint (root.left); } if (root.right! = null) {postOrderPrint (root.Right); } System.out.print (root.val + ""); }Apprenez d'un exemple et l'ordre est le même que l'ordre au milieu. Je ne l'écrirai pas ici
Traversion de séquence de couche
Vous pouvez utiliser une file d'attente de file d'attente pour ajouter d'abord le nœud racine à la file d'attente. Lorsque la file d'attente n'est pas vide, prenez le nœud de nœud de l'en-tête de file d'attente et imprimez la valeur du nœud du nœud. Si les enfants gauche et droit du nœud ne sont pas vides, ajoutez les enfants gauche et droit à la file d'attente.
public static void coucheOrorderPrint (arbre root) {if (root == null) {return; } // La file d'attente de traversée de séquence de calque <Bree> qe = new LinkedList <Bree> (); qe.add (racine); while (! qe.isempty ()) {arbre node = qe.poll (); System.out.print (Node.Val + ""); if (node.left! = null) {qe.add (node.left); } if (node.right! = null) {qe.add (node.right); }}}Priorité de profondeur et d'étendue
En fait, c'est juste un dicton différent. La priorité de la profondeur est la traversée de précommande, la priorité de l'étendue est la traversée de la couche.
public static void DeepFirstprint (root d'arbre) {// La traversée de priorité profonde est équivalente à la piste de précommande // afin que vous puissiez utiliser directement la traversée de précommande if (root == null) {return; } System.out.print (root.val + ""); if (root.left! = null) {DeepFirstprint (root.left); } if (root.Right! = null) {DeepFirstprint (root.Right); }} public static void DeepFirstprintNonerec (arbre root) {// La forme non réécursive de la pignon de profondeur Traversal if (root == null) {return; } Pile <sele> st = new Stack <Bree> (); St.Add (racine); while (! St.Sempty ()) {Tree Node = St.Pop (); System.out.print (Node.Val + ""); // La pile est de retour et d'abord // ajoute d'abord l'enfant droit, puis l'enfant gauche if (node.right! = Null) {St.Add (Node.Right); } if (node.left! = null) {St.Add (node.left); }}}Fonction principale:
public static void main (String [] args) {char [] preorder = "gdafemhz" .tocharArray (); char [] inOrder = "adefghmz" .tocharArray (); Tree root = main.buildtree (précommande, inordre); // main.PostorderPrint (root); // Postorder Traversal // main.layerOrderPrint (root); // Séquence de calques Transfert // main.deepFirstprint (racine); // Priorité profonde Traversale // main.deepFirstprintNonerec (root); // La version non ré-cerzive de la profondeur-première traverse}Résumer
Ce qui précède est tout au sujet de l'établissement d'arbres binaires et de divers codes d'instance de traversée en Java. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à ce site:
" Introduction à deux méthodes de mise en miroir dans la programmation Java des arbres binaires "
" La langue java décrit la profondeur et la largeur de l'arbre binaire "
Exemple de chemin et de code de l'arbre binaire Java
S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!