java - 用堆栈修复 “inorder tree traversal”算法的实现

部分原因是我必须实现二叉树有序遍历的非递归方法。我有点卡住了。这是我到目前为止的内容:

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

最佳答案

按照您的代码，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;
        }
    }
}

关于java - 用堆栈修复 “inorder tree traversal”算法的实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15375581/