使用Stack修复我的"inorder树遍历"算法的实现

Question

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

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

Answer 1

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

基本上,上面的代码将左侧分支推送到堆栈上,直到它到达分支中最左边的节点.然后它弹出并处理它(你可以打印它或用它做其他事情)然后它推动堆栈上的右分支进行处理,因为左分支和节点本身已完成.

Answer 2

在您的代码之后,部件的while循环getLeft()一直向下到树的左侧,然后退出. 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;
        }
    }
}