这个二叉树的有序遍历有什么问题？

Question

我使用 java 实现了 BinaryTree，并尝试实现 InOrder Traversal。我干掉运行副本上的代码，在那种情况下它运行良好，但是当我运行在我的 IDE 上使用它时，我得到了无限循环。但为什么？请帮忙。

 class BinaryTree{
    
    class Node{
    
            private int data;
            private Node left, right;
            public Node(int data)
            {
                this.data = data;
                left=null;
                right=null;}
}
    public void inOrderTraversal(Node root)
            {
                Stack<Node> stack = new Stack<>();
                Node temp = root;
                stack.push(root);
                while(!stack.isEmpty())
                {
                    temp = stack.peek();
                    if(temp.left!=null)
                    {
                        stack.push(temp.left);
                    }
                    else
                    {
                        temp = stack.pop();
                        System.out.print(temp.data+" ");
                        if(temp.right!=null)
                        {
                            stack.push(temp.right);
                        }
                    }
                }
            }
    
    public static void main(String[] args) {
    
            Node one = new Node(1);
            Node two = new Node (2);
            Node three = new Node(3);
            Node four = new Node(4);
            Node five = new Node(5);
            Node six = new Node(6);
            one.left = two;
            one.right = three;
            two.left = four;
            two.right = five;
            three.left = six
    
            BinaryTrees bn = new BinaryTrees();
            bn.inOrderTraversal(one);
        }
}

Answer 1

您的代码以 Node root 开头，等于 one。 one左边是two，two左边是four。在采用 else 条件之前，您的遍历将 two 然后 four 推入堆栈。然后你 pop four，因为 four 右边没有任何东西，你的 while 循环重新开始。但是现在栈顶是 two。 two 的左边仍然是 four，所以你将 four 压入堆栈，这样你的无限循环就开始了。

您需要一种方法来指示已经访问过的节点。如果你真的必须使用堆栈，你应该向你的节点添加一个新属性 class 例如 private boolean visited 并将其初始化为 false。在每个 temp = stack.pop() 之后，您需要设置 temp.visited = True，并且只将未访问过的节点压入堆栈。比如这样：

class Node {
    private int data;
    private Node left, right;
    private boolean visited;
    public Node(int data) {
        this.data = data;
        left = null;
        right = null;
        visited = false;
    }
}

public void inOrderTraversal(Node root) {
    Stack<Node> stack = new Stack<>();
    Node temp = root;
    stack.push(root);
    while(!stack.isEmpty()) {
        temp = stack.peek();
        if(temp.left != null && !temp.left.visited) {
            stack.push(temp.left);
        } 
        else {
            temp = stack.pop();
            temp.visited = true;
            System.out.print(temp.data + " ");
            
            if(temp.right != null && !temp.right.visited) {
                stack.push(temp.right);
            }
        }
    }
}

一个更简单的解决方案是使用递归：

public void inOrderTraveralRecursive(Node node) {
    if (node == null) {
        return;
    }
    inOrderTraveralRecursive(node.left);
    System.out.print(node.data + " ");
    inOrderTraveralRecursive(node.right);
}

Answer 2

要解决 above-mentioned 问题，我们可以在此处使用队列和堆栈来实现。

public void inOrderTraversal(Node root) {
        Stack<Node> stack = new Stack<>();
        Queue<Node> out = new LinkedList<>();
        Node temp = root;
        stack.push(root);
        while (!stack.isEmpty()) {
            temp = stack.peek();
            if (temp.left != null && !temp.left.visited) {
                stack.push(temp.left);
            } else {
                temp = stack.pop();
                temp.visited = true;
                out.offer(temp);

                if (temp.right != null && !temp.right.visited) {
                    stack.push(temp.right);
                }
            }
        }
        while(!out.isEmpty())
        {
            Node tempo = out.poll();
            System.out.print(tempo.data+" ");
            tempo.visited=false;
        }
    }

这是正确的解决方案。

这个二叉树的有序遍历有什么问题？

What is the problem with this InOrder Traversal of Binary Tree?

java

binary-tree

inorder

data-structures