La fixation de ma mise en œuvre de la “aussitôt l'arbre transversal” algorithme avec une Pile

Partie, c'est que j'ai à mettre en œuvre une non-méthode récursive d'un afinde de la traversée d'un arbre binaire. Je suis un peu coincé. Voici ce que j'ai à ce jour:

public void inorder(BinaryTree v) {
    Stack<BinaryTree> stack = new Stack<BinaryTree>();
    stack.push(v);
    System.out.println(v.getValue());

    while(!stack.isEmpty()) {
        while(v.getLeft() != null) {
            v = v.getLeft();
            stack.push(v);
            System.out.println(v.getValue());
        }

        while(v.getRight() != null) {
            v = v.getRight();
            stack.push(v);
            System.out.println(v.getValue());
        }
                stack.pop();
    }
}

J'ai remarqué qu'il n'imprime que le côté gauche de mon arbre, par exemple,

          A
        /   \
       B     C
     /   \  /  \
    D     E F   G
   /  \
  H     I
 / \
J   K

Donne A B D H J

OriginalL'auteur tenkii | 2013-03-13

À la suite de votre code, la boucle while pour le getLeft() partie va tout le chemin vers le bas de la gauche de l'arbre, puis se ferme. v est maintenant nœud J, qui n'a pas le droit de l'enfant de sorte que le prochain tandis que la boucle ne s'exécute pas.

Essayez cet exemple de code: http://www.ashishsharma.me/2011/09/inorder-traversal-without-recursion.html

StackOverflow réponse: https://stackoverflow.com/a/12718147/1178781

//Inorder traversal:
//Keep the nodes in the path that are waiting to be visited
Stack s = new Stack(); 
//The first node to be visited is the leftmost
Node node = root;
while (node != null) {
    s.push(node);
    node = node.left;
}
//Traverse the tree
while (s.size() > 0) {
    //Visit the top node
    node = (Node)s.pop();
    System.out.println((String)node.data);
    //Find the next node
    if (node.right != null) {
        node = node.right;
        //The next node to be visited is the leftmost
        while (node != null) {
            s.push(node);
            node = node.left;
        }
    }
}

Merci beaucoup, les commentaires m'ont aidé à comprendre comment cela fonctionne même plus 🙂

OriginalL'auteur justderb

18

Vous permet de simplifier considérablement la ci-dessus avec une simple boucle while:
```
Stack<Node> stack = new Stack<>();
Node current = root;
while(current != null || !stack.isEmpty()){
  if(current != null){
    stack.push(current);
    current = current.left;
  } else if(!stack.isEmpty()) {
    current = stack.pop();
    process(current);
    current = current.right;
  }
}
```
Fondamentalement le code ci-dessus pousse à gauche branches sur la pile jusqu'à ce qu'il atteigne le plus à gauche du nœud dans la branche. Puis il saute et le processus (vous pouvez l'imprimer ou faire autre chose avec elle) et puis il pousse la branche de droite sur la pile pour le processus depuis la branche gauche et le nœud lui-même est fait.

OriginalL'auteur Giovanni Botta
1

J'ai une solution qui utilise une boucle while. Il est semblable à Giovanni solution, mais à mon avis, il semble plus propre et plus lisible. Plus précisément, la conception est similaire à la solution récursive, En vue de la Traversée qui le rend plus facile à comprendre.
```
public void InOrderTraversal(Node root) {

    if (root == null) return;

    Deque<Node> stack = new ArrayDeque<>();

    stack.push(root);

    while (!stack.isEmpty()) {

        Node curr = stack.peek();

        if (curr.left != null) {

            stack.push(curr.left);
            continue;
        }


        Node node_to_print = stack.pop();
        System.out.println(node_to_print.data);


        if (curr.right != null) {

            stack.push(curr.right);

        }

    }

    return;
}
```
Remarque : j'ai utilisé l'interface Deque pour mettre en œuvre ma pile. Selon l'API, ce doit être la méthode préférée : http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

Malheureusement, je ne pense pas que cela fonctionne. Le cas simple d'un nœud racine à un nœud de gauche ne sera jamais sortir de la boucle, il va continuer d'essayer de traiter le nœud racine après il est fait avec le nœud de gauche.

OriginalL'auteur Haider

Une autre plus simple, binaire traversée de mise en œuvre :

import java.util.Stack;
public class BinaryTree {
public static void main(String args[])
{
Node root = Node.createDummyTree();
Node tnode; //= root;
Stack<Node> stack = new Stack<Node>();
if (root != null)
{
stack.push(root);
}
while (!stack.isEmpty())
{
tnode = stack.pop();
if (tnode != null)
{
System.out.println(tnode.value);
if(tnode.rightNode != null)
{
stack.push(tnode.rightNode);
}
if (tnode.leftNode != null)
{
stack.push(tnode.leftNode);
}
}
}
}
}
class Node {
public Node leftNode;
public Node rightNode;
public String value;
Node(String value)
{
this.value = value;
}
/**
*  Construct a dummy binary Tree
*               A
*          /        \
*         B           C
*       /  \       /  \
*      D     E     F     G
*     /\   /\   /\   /\
*    H   I J   K  L  M  N  O
* @return
*/
public static Node createDummyTree(){
Node root = new Node("A");
root.leftNode = new Node("B");
root.rightNode = new Node("C");
Node tnode = root.leftNode;
tnode.leftNode = new Node("D");
tnode.rightNode = new Node("E");
Node tempNode = tnode.rightNode;  //remember "E"  
tnode = tnode.leftNode;
tnode.leftNode = new Node ("H");
tnode.rightNode = new Node ("I");
tnode = tempNode;
tnode.leftNode = new Node ("J");
tnode.rightNode = new Node ("K");
tnode = root.rightNode;
tnode.leftNode = new Node("F");
tnode.rightNode = new Node("G");
tempNode = tnode.rightNode;  //rememebr "G"
tnode = tnode.leftNode;
tnode.leftNode = new Node("L");
tnode.rightNode = new Node("M");
tnode = tempNode;
tnode.leftNode = new Node("N");
tnode.rightNode = new Node("O");
return root;
}
}

OriginalL'auteur Deba Pal

Vous devez vous connecter pour publier un commentaire.