Les sujets:

Les partenaires publicitaires:

Réponses populaires

Questions connexes

Les partenaires publicitaires:

Comment faire inorder traversée en arbre binaire en java

Java n'a pas une classe d'arbre binaire, mais il est simple de présenter une version de la structure de données pour faire une parcours infixe. Un "traversal" d'un arbre binaire est une procédure formules pour visiter chaque noeud sur l'arbre binaire une fois. Un parcours infixe va faire dans l'ordre. Traversal est souvent mis en œuvre comme une sorte de iterator (comme une liste iterator) ou par une méthode qui va appeler une méthode de rappel pour chaque noeud. Vous pouvez, cependant, faire cela sans l'aide des rappels ou des itérateurs, au lieu de l'impression à la console chaque noeud visité.

Instructions

  1. Créer un binaire classe de base arbre de recherche. À ce stade, vous aurez seulement besoin d'une méthode constructeur de base qui initialise la valeur du noeud et une méthode d'insertion. La méthode d'insertion va traverser un arbre et de faire un nouveau nœud dans le bon endroit. ""public class BinaryTree {
    BinaryTree gauche;
    BinaryTree droit;
    int à valeur

    BinaryTree publique (int v) {
    value = V-
    }

    // Insérer une valeur dans l'arbre
    insert public void (int v) {
    si (v lt; valeur) {
    if (null == gauche)
    gauche = new BinaryTree (v) -
    autre
    left.insert (v) -
    }

    else if (v gt; valeur) {
    si (à droite == null)
    droite = new BinaryTree (v) -
    autre
    right.insert (v) -
    }
    }
    }""



  2. Créez l'instance (noeud) de l'arbre binaire qui sera le nœud racine. Comme tout autre noeud, le noeud racine doit avoir une valeur. Il est généralement préférable de choisir une valeur proche de la médiane des objets que vous stockez, comme des arbres binaires devraient être aussi équilibrée que possible. ""BinaryTree b = new BinaryTree (50) -""

  3. Insérez nœuds dans l'arbre afin de conserver l'équilibre spécifique, comme cet arbre binaire est pas auto-équilibrage. Cet exemple crée le plus petit possible arbre afin de maintenir l'efficacité.""b.Insérez (20) -
    b.Insérez (40) -
    b.Insérez (10) -
    b.Insérez (5) -
    b.Insérez (45) -

    b.Insérez (70) -
    b.Insérez (60) -
    b.Insérez (80) -
    b.Insérez (55) -
    b.Insérez (85) -""




  4. Se déplacer à travers l'arbre en utilisant un parcours infixe. L'arbre gauche est traversé en premier, suivi par le nœud racine, puis le bon arbre est traversé. Utilisation de la récursivité, le code est simplement trois lignes. Cependant, depuis la récursion prend l'espace de pile, il doit être utilisé avec précaution. Avec une petite et équilibrée arbre binaire, récursivité ne débordera pas la pile.

  5. Ajouter une nouvelle méthode pour la classe Java BinaryTree appelé inorder.
    ""public void inorder () {
    if (gauche! = null) left.inorder () -
    System.out.println (valeur) -
    si (à droite! = null) right.inorder () -
    }""

  6. Appelez la méthode inorder après vos inserts d'imprimer les noeuds dans l'ordre.""b.inorder () -"

Conseils & Avertissements

  • Les méthodes comme un "supprimer noeud" méthode ne sont pas pris en charge par cet exemple la classe.
  • Dans cet exemple de inorder traversée, la pile ne fera que croître à la hauteur de l'arbre, de sorte que la pile ne débordera pas. Si votre arbre binaire est très grande, la fonction de traversée devrait être mis en œuvre de manière itérative.
  • Comme avec tout autre langage de programmation, arbres binaires asymétriques en Java peuvent devenir très grand et sont inefficaces.

Questions connexes

» » » » Comment faire inorder traversée en arbre binaire en java