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

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

按照您的代码，该getLeft()部分的 while 循环一直沿着树的左侧向下，然后退出。 v现在是 node 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;
        }
    }
}

Answer 3

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

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