java 使用堆栈修复我的“中序树遍历”算法的实现

Fixing my implementation of "inorder tree traversal" algorithm with a Stack

提问by tenkii

Part of it is that I have to implement a non-recursive method of a inorder traversal of a binary tree. I am kind of stuck. Here is what I have so far:

部分原因是我必须实现一个二叉树的中序遍历的非递归方法。我有点卡住了。这是我到目前为止所拥有的：

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

I noticed that it only prints out the left side of my tree, e.g.

我注意到它只打印出我的树的左侧，例如

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

Gives A B D H J

给 A B D H J

回答by Giovanni Botta

You can greatly simplify the above with a single while loop:

您可以使用一个 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;
  }
}

Basically the code above pushes left branches on the stack until it reaches the leftmost node in the branch. Then it pops it and processes it (you can print it or do something else with it) and then it pushes the right branch on the stack to process since the left branch and the node itself are done.

基本上上面的代码将左分支推入堆栈，直到它到达分支中的最左边的节点。然后它弹出它并处理它（你可以打印它或用它做其他事情）然后它把右边的分支推到堆栈上进行处理，因为左边的分支和节点本身已经完成。

回答by justderb

Following your code, the while loop for the getLeft()part goes all the way down the left of the tree, then exits. vis now node J, which has no right child so the next while loop doesn't run.

按照您的代码，该部件的 while 循环getLeft()一直沿着树的左侧向下运行，然后退出。 v现在是 node J，它没有右孩子，所以下一个 while 循环不会运行。

Try this code example: http://www.ashishsharma.me/2011/09/inorder-traversal-without-recursion.html

试试这个代码示例：http: //www.ashishsharma.me/2011/09/inorder-traversal-without-recursion.html

StackOverflow answer: https://stackoverflow.com/a/12718147/1178781

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

回答by Deba Pal

Another simpler binary traversal implementation :

另一个更简单的二进制遍历实现：

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