Java 实现的二叉树的递归、非递归遍历

1.二叉树的递归遍历

//先序：根、左子树、右子树
public void preOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        System.out.println(head.val);
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }
//中序：左子树、根、右子树
public void inOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        inOrderRecur(head.left);
        System.out.println(head.val);
        inOrderRecur(head.right);
    }
//后序：左子树、右子树、根
public void posOrderRecur(Node head) {
        if (head == null) {
            return;
        }
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.println(head.val);
    }

递归遍历的关键是，将输出语句插入到合适的位置

2.二叉树的非递归先序遍历

利用一个栈来实现先序遍历
1根节点入栈
2判断栈是否为空，如果不为空
弹出栈顶元素
打印栈顶元素
如果有右子树压栈
如果有左子树压栈
3如果栈为空，程序结束

public void preOrder(Node head) {
        if (head == null) {
            return;
        }
        Stack<Node> s = new Stack<Node>();
        s.push(head);
        while (!s.isEmpty()) {
            Node cur = s.pop();
            System.out.println(cur.val);
            if (cur.right != null) {
                s.push(cur.right);
            }
            if (cur.left != null) {
                s.push(cur.left);
            }
        }
    }

3.二叉树的非递归中序遍历

1.如果栈不为空或节点不指向空数据，则执行以下步骤
a如果节点不为空，压栈，沿着左子树走一步
b如果节点为空，则出栈，打印，沿着右子树走一步
2.如果栈为空且当前节点为空，则结束

public void inOrder(Node head) {
        if (head == null) {
            return;
        }
        Stack<Node> s = new Stack<Node>();
        while (!s.isEmpty() || head != null) {
            if (head != null) {
                s.push(head);
                head = head.left;
            } else {
                head = s.pop();
                System.out.println(head.val);
                head = head.right;
            }
        }
    }

4.二叉树的非递归后序遍历

4.1两个栈实现

1申请两个栈s1，s2，头节点入栈s1
2如果栈s1不为空，执行以下操作：弹出一个元素，入栈s2，如果该节点左孩子不空入栈s1，如果该节点右孩子不空入栈s1.
3.将栈s2中的节点一次出栈，打印。

// 两个栈实现后序遍历
    public void posOrder(Node head) {
        if (head == null) {
            return;
        }
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();
        s1.push(head);
        while (!s1.isEmpty()) {
            Node cur = s1.pop();
            s2.push(cur);
            if (cur.left != null) {
                s1.push(cur.left);
            }
            if (cur.right != null) {
                s1.push(cur.right);
            }
        }
        while (!s2.isEmpty()) {
            Node cur = s2.pop();
            System.out.println(cur.val);
        }
    }

4.2一个栈实现后序遍历

后序遍历的难点在于：如何判断上次访问的节点是位于左子树，还是右子树，如果上一个访问的节点是左子树，那么我们则需要先跳过根节点，访问右子树，再返回根节点。

public void postOrder3(Node node){  
            if(node == null)  
                return;  
            Stack<Node> s = new Stack<Node>();  
              
            Node curNode; //当前访问的结点  
            Node lastVisitNode; //上次访问的结点  
            curNode = node;  
            lastVisitNode = null;  
              
            //把currentNode移到左子树的最下边  
            while(curNode != null){  
                s.push(curNode);  
                curNode = curNode.left;  
            }  
            while(!s.empty()){  
                curNode = s.pop();  //弹出栈顶元素  
                //一个根节点被访问的前提是：无右子树或右子树已被访问过  
                if(curNode.right!= null && curNode.right !=lastVisitNode){  
                    //根节点再次入栈  
                    s.push(curNode);  
                    //进入右子树，且可肯定右子树一定不为空  
                    curNode = curNode.right;  
                    while(curNode!= null){  
                        //再走到右子树的最左边  
                        s.push(curNode);  
                        curNode = curNode.left;  
                    }  
                }else{  
                    //访问  
                    System.out.println(curNode.val);  
                    //修改最近被访问的节点  
                    lastVisitNode = curNode;  
                }  
            } 
        }