二叉搜索树中序遍历的实现-栈与递归

1.基础了解
本文中描述的栈为：虚拟机栈、方法栈
堆上的内存中设置两个参数，root和size，root指向根节点，size记录数据量
2. 用递归实现二叉搜索树的中序遍历

public void inOrder2(NodeMyBST2 root, MyListArray<T> list){
}

为什么是void方法，为什么该不需要返回参数？ 引用传递

public MyListArray<T> inOrder(){
        MyListArray<T> list = new MyListArray<>();
        inOrder2(root, list);//把list和根节点去做递归遍历
        return list;这里就会返回中序遍历的结果
    }

public void inOrder2(NodeMyBST2 root, MyListArray<T> list){
	//list中存储中序遍历的结果，但是代码在内存中是怎么运行的呢？
        if (root == null) return;

        //左子树
        postOrder3(root.left, list);
        //跟
        list.add(root.value);
        //右子树
        postOrder3(root.right, list);
    }

先运行inOrder()方法，JVM在栈上开辟一个内存空间，inOrder()先入栈

假设我们有一颗这样的子树，如下图所示，怎么输出他的中序遍历呢？

每次递归调用inOrder2(root, list)方法，需明确该root是哪个节点(重要)，刚开始时root根节点指向为1；

开始调用递归方法inOrder2()，同时外部inOrder()方法并没有结束，暂时保存栈的方法状态，重新开辟一个新的栈方法状态来运行inOrder2()。
如果本次递归结束，方法需出栈

inOrder2()方法中的root也等于1 ，因为1是inOrder()方法传递过来的，

3. 方法开始执行

首先遍历根节点1的左子树

开始递归，重新调用inOrder2()方法入栈，开辟一个新的空间去执行root->1的左子树，

root->-100, 该方法的左子树不为null,还能继续遍历，方法没有执行完毕，继续递归，直到左子树root->-150

当root=-150继续遍历，虽然-150左子树和右子树都为null，但还需继续遍历

当root=-150左子树为null
if (root == null) return
满足递归出口条件满足，该方法退栈

同时list存入-150
list.add(root.value);
因为中序遍历的规则为：左子树->根节点->右子树，所以我们把内容存储在list中，list中的存储顺序即为中序遍历的顺序

方法继续执行，遍历root=-150的右子树

同样的，右子树root=-150的右子树null方法出栈

root=-100的左子树已执行完毕，list存入-100

继续遍历root=-100的右子树，root=-10，root = -50 ，root = null依次入栈。

root=-50的左子树为null，方法出栈，list保存root=-50

root=-50的右子树为null，方法出栈，回到root=-10继续执行，遍历root = -10的右子树

root = -10的右子树为Null，方法出栈，root = -10，root = -100左右子树都已遍历完成，方法依次出栈

此时root = 1的左子树遍历完成，将root = 1添加到list中

root = 1的右子树同理。

二叉搜索树中序遍历的实现-栈与递归

原文：https://www.cnblogs.com/wfqblogs/p/14614233.html