关于java:用递归非递归的方式分别实现二叉树的先序中序后序遍历java实现

首先约定：先序：根，左，右　　中序：左，根，右　　后序：左，右，根

递归实现

递归实现中，总是会通过一个节点三次，所以先序中序和后序的惟一区别就是打印的机会不同

public class Node {//这是Node的构造
    public int value;
    public Node left;
    public Node right;
    public Node(int data) {
        this.value = data;
    }
}

    public void preOdferRecur(Node head) {
        if (head == null) {
            return;
        }
        System.out.print(head.value + " ");//先序遍历，打印放在第一行
        preOdferRecur(head.left);
        preOdferRecur(head.right);
    }

    public void inOdferRecur(Node head) {
        if (head == null) {
            return;
        }
        inOdferRecur(head.left);
        System.out.print(head.value + " ");//中序遍历，打印放在第二行
        inOdferRecur(head.right);
    }
    public void posOdferRecur(Node head) {
        if (head == null) {
            return;
        }
        posOdferRecur(head.left);
        posOdferRecur(head.right);
        System.out.print(head.value + " ");//后序遍历，打印放在第三行
    }　

非递归实现

非递归先序遍历

思路：申请一个栈，压入头结点，而后弹出栈节点，打印进去，再将弹出节点的右孩子压入，左孩子压入，一直反复这个过程，直到栈为空

   public void preOrderUnRecur(Node head){
        if (head!=null){
            Stack<Node> stack=new Stack<Node>();
            stack.add(head);
            while(!stack.isEmpty()){
                head=stack.pop();
                System.out.printf(head.value+" ");
                if (head.right!=null){
                    stack.push(head.right);
                }
                if (head.left!=null){
                    stack.push(head.left);
                }
            }
        }
    }

非递归中序遍历

思路：中序是左，根，右，因而思考将左边界都压入栈，直到节点为空，则从栈中拿出一个打印，以后节点右移，若以后节点不为空，则压入栈，以后节点为左

1. 申请一个栈，记为stack。初始时，令变量cur=head。
2. 先把cur节点压入栈，对以cur节点为头结点的子树来说，顺次把左边界压入栈中，即不停地令cur=cur.left，而后反复步骤2
3. 直到cur为空，此时从stack中弹出一个节点，记为node。打印node，并让cur=node.right，而后继续反复步骤2
4. 当stack为空且cur为空，这个过程进行

 `public void inOrderUnRecur(Node head){
        if(head!=null){
            Stack<Node> stack=new Stack<Node>();
            while (!stack.isEmpty()||head!=null){
                if (head!=null){
                    stack.push(head);
                    head=head.left;
                }
                else {
                    head=stack.pop();
                    System.out.println(head.value+" ");
                    head =head.right;
                }
            }
        }
    }

非递归后序遍历

思路：后序遍历是左，右，中，先序是中，左，右，将中左右变成中右左，在建设个栈将中右左压入，弹出即是后序遍历的秩序

 public void posOrderUnRecur(Node head){
        if (head!=null){
            Stack<Node> stack1=new Stack<Node>();
            Stack<Node> stack2=new Stack<Node>();
            stack1.add(head);
            while(!stack1.isEmpty()){
                head=stack1.pop();
                stack2.push(head);
                if (head.left!=null){
                    stack1.push(head.left);
                }
                if (head.right!=null){
                    stack1.push(head.right);
                }
            }
            while(!stack2.isEmpty()){
                System.out.printf(stack2.pop().value+" ");
            }
        }
    }

连贯地址：https://blog.csdn.net/weixin_…