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

Stack Overflow用户

提问于 2020-09-01 17:11:08

回答 2查看 103关注 0票数 1

我使用java实现了BinaryTree，并尝试实现了InOrder遍历。我在副本上干运行代码，在这种情况下，它工作得很好，但当我在我的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);
        }
}

java

data-structures

binary-tree

inorder

腾讯云域名特惠，新用户首年1元起

腾讯云域名专场特惠：个人新用户.cn仅8.8元/年，企业新用户.com仅1.06元/年...

回答 2

Stack Overflow用户

回答已采纳

发布于 2020-09-01 17:51:33

您的代码以等于one的Node root开头。one左边是two，two左边是four。在接受else条件之前，遍历会将two然后four推送到堆栈。然后对four执行pop操作，由于four在右侧没有任何内容，因此while循环重新开始。但是现在堆栈的顶部是two。two左边仍然是four，所以你把four压到堆栈上，这样无限循环就开始了。

您需要一种方法来指示已经被访问过的节点。如果确实必须使用堆栈，则应该向Node类添加一个新属性，如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);
}

票数 1

Stack Overflow用户

发布于 2020-09-02 04:41:02

为了解决上述问题，我们可以在这里使用队列和堆栈进行实现。

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