java - 使用 Stack 修复我的 "inorder tree traversal"算法的实现

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

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