6

その一部は、バイナリツリーを順番にトラバースする非再帰的な方法を実装する必要があることです。私はちょっと立ち往生しています。これが私がこれまでに持っているものです：

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();
    }
}

私はそれが私の木の左側だけを印刷することに気づきました、例えば

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

与えるA B D H J

4

3 に答える 3

19

単一の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;
  }
}

基本的に、上記のコードは、ブランチの左端のノードに到達するまで、スタックの左側のブランチをプッシュします。次に、それをポップして処理し（印刷するか、他のことを行うことができます）、左のブランチとノード自体が完了しているため、スタックの右のブランチをプッシュして処理します。

于 2014-03-19T02:30:40.180 に答える
7

コードに従って、getLeft()パーツのwhileループがツリーの左端まで移動し、終了します。 vこれでノードJになりました。これには正しい子がないため、次のwhileループは実行されません。

このコード例を試してください：http ：//www.ashishsharma.me/2011/09/inorder-traversal-without-recursion.html

StackOverflowの回答：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;
        }
    }
}
于 2013-03-13T01:50:55.673 に答える
0

別のより単純なバイナリトラバーサルの実装：

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;
    }
}
于 2015-07-06T16:47:13.067 に答える