Dans l'ordre itérateur pour arbre binaire

Comment puis-je écrire un Java itérateur (c'est à dire les besoins de la next et hasNext méthodes) qui prend la racine d'un arbre binaire et parcourt les nœuds de l'arbre binaire en dans l'ordre de la mode?

Je pense que la question est assez claire, si vous savez ce qu'est un arbre binaire, et qui ont l'expérience de l'analyse d'eux.
Je pense que c'est de la vraie question bien. Il doit probablement avoir été fermé comme trop large à la place.
C'est une vraie question. Je ne comprends vraiment pas certains des modérateurs, DONC.

InformationsquelleAutor Paul S. | 2012-10-12

39

Le premier élément d'un sous-arbre est toujours le plus à gauche. Le prochain élément après élément est le premier élément de son sous-arbre droit. Si l'élément n'a pas un droit de l'enfant, l'élément suivant l'élément du premier ancêtre. Si l'élément n'a ni enfant ni un droit ancêtre, c'est l'élément le plus à droite et c'est la dernière dans l'itération.

J'espère que mon code est lisible par l'homme et couvre tous les cas.
```
public class TreeIterator {
    private Node next;

    public TreeIterator(Node root) {
        next = root;
        if(next == null)
            return;

        while (next.left != null)
           next = next.left;
    }

    public boolean hasNext(){
        return next != null;
    }

    public Node next(){
        if(!hasNext()) throw new NoSuchElementException();
        Node r = next;

        //If you can walk right, walk right, then fully left.
        //otherwise, walk up until you come from left.
        if(next.right != null) {
            next = next.right;
            while (next.left != null)
                next = next.left;
            return r;
        }

        while(true) {
            if(next.parent == null) {
                next = null;
                return r;
            }
            if(next.parent.left == next) {
                next = next.parent;
               return r;
            }
            next = next.parent;
        }
     }
 }
```
Envisager l'arbre suivant:
```
     d
   /   \
  b     f
 / \   / \
a   c e   g
```
- Le premier élément est "complètement à gauche à partir de la racine"
- a ne dispose pas d'un droit de l'enfant, de sorte que l'élément suivant "jusqu'à ce que vous venez de gauche"
- b n'ont un droit de l'enfant, ainsi, parcourir b's sous-arbre droit
- c n'a pas le droit de l'enfant. C'est le parent est b, qui a été parcouru. Le prochain parent est d, qui n'a pas été parcouru, donc arrêter ici.
- d a un sous-arbre droit. Son élément le plus à gauche est e.
- ...
- g n'a pas le droit de sous-arborescence, afin de marcher. f a été visité, depuis que nous avons viennent de la droite. d a été visité. d n'a pas de parent, de sorte que nous ne pouvons pas nous déplacer plus loin. Nous avons parcouru à partir du nœud le plus à droite et nous nous sommes fait l'itération.
- Il y a une raison pour laquelle je n'ai pas de poste valide d'un itérateur dans ma réponse, et il était si les OP auraient à le faire eux-mêmes. Donner des réponses comme cela ne profitent à personne.
- bon point. Howerer, ce n'est pas un copier-coller chose de toute façon. Au moins une ligne doit être changé 😉 mais j'avoue que ce n'était pas délibéré. Mon objectif a été de lisibilité, de ne pas l'exactitude. Je n'ai même pas le tester 😉
- J'aime votre idée de mettre de côté. Je ne pouvais que penser à déposer le noeud courant, pas le prochain, et j'ai eu tellement de mal à trouver un moyen d'imprimer le premier élément. Je vous remercie.
- Super réponse, je vous remercie! Je ne pense que vous êtes en manque un return dans next(), juste avant la dernière accolade fermante.
- que faire si vous ne disposez pas d'un parent pointeur?
- ensuite, vous avez besoin d'une pile de quelques sortes. Depuis Java n'a pas de générateurs / coroutines (sauf Java 8 introduits), une pile explicite aurez à faire. Rappelez-vous juste la liste des parents dans une liste, puis de la pop lorsque vous voulez aller jusqu'.
- vous perdez référence à la racine de bien......
- si j'utilise une pile explicite, tu veux dire? C'est au fond de la pile. Si j'utilise parent pointeurs, il me prend o(log n) pour l'atteindre. Si j'utilise une liste, pile, il me prend o(log n) pour apercevoir le fond. Si j'utilise une liste de tableaux de la pile, il me prend o(1) pour apercevoir le fond. Et, comme toujours, vous pouvez organiser une référence explicite à quelque part d'autre. Aussi, l'itérateur n'en a pas besoin car il est plus rapide d'analyse à partir du noeud courant qu'à partir de la racine (asymptotiquement presque toujours, et toujours dans le sens amorti)
- ce code fait sens pour moi jusqu'à ce que le "else while (true)" la clause, je ne suis pas familier avec ce motif. Pourriez-vous préciser quand ce code se déclenche? Quand je l'ai créer et compiler (en tenant compte des éléments comme un parent pointeur), il n'a jamais imprime la gauche nœuds sur la gauche du sous-arbre (pour moi, il devrait afficher "a, b, d") puis tourne au ralenti.
- lorsqu'un nœud a un droit de l'enfant, le nœud suivant dans l'ordre est le plus à gauche du nœud du sous-arbre droit. Je suppose que vous n'entrez jamais dans un sous-arbre droit?
- Je recommande d'avoir Node/TreeIterator est une fonction simple qui a récupéré la référence à l'élément le plus à gauche d'un nœud donné - fait actuel code plus simple à lire et pas de répétition de code.
- Je pense que le plus naturel et de façon générale de penser, est de maintenir l'appel de la pile vous-même. Ce qui doit être stocké sur le frame de pile est tous les paramètres pour la fonction récursive et l'opportunité d'appeler ou de retour. Exemple de code: gist.github.com/qiuwei/1c52a9a679c11b99ba48fdb9416c70de
- un piège avec cette réponse est Chaque TreeNode besoin de stocker parent, sinon il faut passer par la route de stocker les parents séparément ou de l'utilisation de la pile pour former un itérateur.
InformationsquelleAutor John Dvorak
2

Pour obtenir l'entrée suivante, 'nextEntry()', pour l'itérateur, j'ai regardé des extraits de java.util.TreeMap collé ci-dessous. En clair, je dirais que vous assurez-vous que le nœud racine est pas null première else return null. Si elle n'est pas, visitez le droit nœud si elle n'est pas null. Puis visite de la gauche (si ce n'est nulle) et de la visite que la gauche à plusieurs reprises dans une boucle while, avant de se heurter null. Si originial droit nœud est nulle alors au lieu de tout cela, visitez le nœud parent si ce n'est pas null. Entrez maintenant dans une boucle while, où vous visitez le parent jusqu'à ce qu'il soit null ou le nœud que vous êtes actuellement en visite a sa droite (enfant) nœud correspondant à votre dernière position. Maintenant de retour quelle que soit l'entrée que vous êtes sittng sur. À défaut de toutes les options, renvoyez le (original) nœud racine. 'HasNext()' vérifie simplement si cette "suivant", vous êtes de retour est null ou pas.
```
public final boolean hasNext() {
     return next != null;
}

final TreeMap.Entry<K,V> nextEntry() {
    TreeMap.Entry<K,V> e = next;
    if (e == null || e.key == fenceKey)
        throw new NoSuchElementException();
    if (m.modCount != expectedModCount)
        throw new ConcurrentModificationException();
    next = successor(e);
    lastReturned = e;
    return e;
}

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}
```
- Oui, je l'ai fait. S'il vous plaît publier la vôtre, et peut-être que l'on a accepté de répondre si égal ou supérieur à mon explication. Il dit, en réalité, dans le TreeMap.java fichier emballés avec le jdk que le code est properietary. Si c'est le cas, je dirai que ~30 lignes de 2400 est l'utilisation équitable aux fins d'éducation.
- J'ai fait publier ma réponse.
- Pas sûr que la transcription permet de comprendre...
- Je suis d'accord avec la politique d'utilisation équitable, je dis que c'est facile de négliger l'attribution. En fait, je l'ai fait.
- Je vois ce que tu veux dire, il est raisonnable de supposer que l'utilisateur coller du code écrit. Je ne suis pas sûr que je pourrais écrire un arbre binaire de données de la structure de moi-même, mais j'ai utilisé les Arborescences et il a remarqué une source pertinente d'être beaucoup plus simple que ce que j'attendais. Je pense que la transcription est utile. J'aime votre a-g arbre et de le voir deux implémentations de la même chose.
InformationsquelleAutor apcris
-1

C'est assez simple, à l'ordre de la traversée vous visitez la gauche de l'enfant si il y en a un, alors le nœud racine, puis le droit de l'enfant:
```
visit_node(node)
   if node.left: visit_node(node.left)
   //visit the root node
   if node.right: visit_node(node.right)
```
Diagramme:
```
     a 
   /   \        (in-order traversal would give bac)
  b     c
```
- Mais lors de l'écriture d'un itérateur (par exemple, Java itérateur qui doit next et hasNext méthodes), comment pouvez-vous intégrer une méthode récursive comme ça?
- Vous pouvez toujours prendre les nœuds dans l'ordre et les ajouter à certains autres de la collection.
- Est efficace?
InformationsquelleAutor Hunter McMillen

Vous devez vous connecter pour publier un commentaire.