中序遍历二叉树

算法描述

中序遍历（LDR）的遍历顺序是先访问左节点，再访问根节点，最后访问右节点。简单来记就是左根右。

树的结构如下：

public class TreeNode{
    //节点结构
    int value;
    TreeNode left;
    TreeNode right;
    TreeNode(int value) {
        this.value = value;
    }
}

---

递归法

public static void midOrderRe(TreeNode biTree) {
        //中序遍历递归实现
        if(biTree == null)
            return;
        else {
            midOrderRe(biTree.left);
            midOrderRe(biTree.right);
        }
    }

---

非递归法——利用栈实现

我们可以利用栈来实现非递归的中序遍历。当结点或者栈不为空的时候我们循环执行操作——当结点不为空我们将结点入栈，并将其左子树节点作为新的节点进行操作；若其左节点为空，且栈非空则栈顶元素出栈，将结点的右子树作为新的节点，根据其是否为空进行入栈或出栈操作。（建议画图模拟算法过程）

public static void midOrder(TreeNode biTree) {
        //中序遍历非递归实现
        Stack<TreeNode> stack = new Stack();
        while(biTree != null || !stack.isEmpty()) {
            while(biTree != null) {
                stack.push(biTree);
                biTree = biTree.left;
            }
            if(!stack.isEmpty()) {
                biTree = stack.pop();
                biTree = biTree.right;
            }
        }
    }