二叉树——中序遍历（递归/非递归）

中序遍历，即遍历顺序为：左节点、根节点、右节点。

二叉树节点：

public class Node {
    public Node left;
    public Node right;
    public int val;

    public Node(int data){
        this.val = data;
    }
}
           

1. 递归方式

思想同二叉树——先序遍历（递归/非递归）

2. 非递归方式

借助数据栈。步骤：

当根节点非空时，申请一个数据栈；

在【栈非空 或 head非空】时，重复执行下述操作：

1). 如果head非空，把它压入栈中，并让head指向它的左孩子。

2). 如果head为空，弹出栈顶节点，用head保存该节点，并打印该节点的值，并让head指向它的右孩子。

在压栈操作后，head指向左孩子，在出栈操作后，head指向右孩子，所以head已经不代表根节点，而是作为一个临时指针节点，

从而把左孩子依次压入栈，直到左孩子为空，然后出栈，在出栈的时候用head保存弹出的节点，打印其数值，并指向该节点的右孩子，如果其右孩子不为空，则符合while循环条件，重复执行压栈操作~

代码：

import java.util.Stack;

/*中序遍历：递归方式和非递归方式，打印二叉树节点的值
 * 参数：根节点
 * 输出：void
 */
public class InOrder {
    //中序遍历，递归方式
    public static void inOrderRecursion(Node head){
        if(head == null){
            System.out.println("二叉树为空");
            return;
        }
        if(head.left != null){
            inOrderRecursion(head.left);
        }
        System.out.print(head.val+", ");
        if(head.right != null){
            inOrderRecursion(head.right);
        }
    }

-------------------------------------

    //中序遍历，非递归方式
    public static void inOrder(Node head){
        if(head == null){
            System.out.println("二叉树为空");
            return;
        }
        System.out.println("中序遍历，非递归方式");
        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.print(head.val+", ");
                head = head.right;
            }
        }
    }

------------------测试-------------------

    public static void main(String[] args) {
        //创建二叉树节点
            Node head = new Node();
            Node n1 = new Node();
            Node n2 = new Node();
            Node n3 = new Node();
            Node n4 = new Node();
            Node n5 = new Node();
            Node n6 = new Node();
        //生成二叉树
            head.left = n1;
            head.right = n2;
            n1.left = n3;
            n1.right = n4;
            n2.left = n5;
            n2.right = n6;
        //递归方式中序遍历二叉树
            inOrderRecursion(head);
            System.out.println();
            System.out.println();
        //递归方式中序遍历二叉树
            inOrder(head);
        }
}
           

本例创建了一个包含有7个节点的完全二叉树：

运行结果：

过程示意图：