首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >这个二叉树的InOrder遍历有什么问题?

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

Stack Overflow用户
提问于 2020-09-02 01:11:08
回答 2查看 103关注 0票数 1

我使用java实现了BinaryTree,并尝试实现了InOrder遍历。我在副本上干运行代码,在这种情况下,它工作得很好,但当我在我的IDE上运行它时,我得到了无限循环。但是为什么呢?请帮帮忙。

代码语言:javascript
代码运行次数:0
运行
复制
 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);
        }
}
EN

回答 2

Stack Overflow用户

回答已采纳

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

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

您需要一种方法来指示已经被访问过的节点。如果确实必须使用堆栈,则应该向Node类添加一个新属性,如private boolean visited,并将其初始化为false。在每个temp = stack.pop()之后,您需要设置temp.visited = True,并且只推送到尚未访问的堆栈节点上。如下所示:

代码语言:javascript
代码运行次数:0
运行
复制
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);
            }
        }
    }
}

更简单的解决方案是使用递归:

代码语言:javascript
代码运行次数:0
运行
复制
public void inOrderTraveralRecursive(Node node) {
    if (node == null) {
        return;
    }
    inOrderTraveralRecursive(node.left);
    System.out.print(node.data + " ");
    inOrderTraveralRecursive(node.right);
}
票数 1
EN

Stack Overflow用户

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

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

代码语言:javascript
代码运行次数:0
运行
复制
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;
        }
    }

这是正确的解决方案。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/63692420

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档