非递归实现二叉树排序

非递归的方式实现二叉树先序,中序,后序遍历,就需要借助栈来进行帮助。
尤其在做后序遍历的时候,需要两个栈来进行协同(主要就是右子树要比根结点先入栈,这样才能保证根结点在右子树之后遍历出来)。

    @Override
    public void preOrderByStack() {
        System.out.println("Start preOrderByStack");
        Deque<Node> stack = new LinkedList<>();
        Node current = root;
        while (null != current || !stack.isEmpty()) {
            while (null != current) {
                System.out.print(current.getData() + " ");
                if (null != current.getRightChild())
                    stack.push(current.getRightChild());
                current = current.getLeftChild();
            }
            if (!stack.isEmpty()) {
                current = stack.pop();
            }
        }
    }

    @Override
    public void innerOrderByStack() {
        System.out.println("Start innerOrderByStack");
        Deque<Node> stack = new LinkedList<>();
        Node current = root;
        while (null != current || !stack.isEmpty()) {
            while (null != current) {
                stack.push(current);
                current = current.getLeftChild();
            }
            if (!stack.isEmpty()) {
                current = stack.pop();
                System.out.print(current.getData() + " ");
                current = current.getRightChild();
            }
        }
    }

    @Override
    public void postOrderByStack() {
        System.out.println("Start postOrderByStack");
        Deque<Node> stack1 = new LinkedList<>();
        Deque<Node> stack2 = new LinkedList<>();
        Node current = root;
        while (null != current || !stack1.isEmpty()) {
            while (null != current) {
                stack1.push(current);
                stack2.push(current);
                current = current.getRightChild();
            }

            current = stack1.pop();
            current = current.getLeftChild();
        }
        while (!stack2.isEmpty()){
            System.out.print(stack2.pop().getData() + " ");
        }
    }

    @Override
    public void levelOrderByStack() {
        System.out.println("Start levelOrderByStack");
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (queue.size() != 0) {
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                Node temp = queue.poll();
                System.out.print(temp.getData() + " ");
                if (null != temp.getLeftChild()) {
                    queue.add(temp.getLeftChild());
                }
                if (null != temp.getRightChild()) {
                    queue.add(temp.getRightChild());
                }
            }
        }
    }
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容