1、Node类中建立的递归（Easy）：

见toString和Node.class中的inOrder方法

package tree; import java.util.ArrayList; import java.util.Deque; import java.util.LinkedList; import java.util.List; /** * 排序二叉树 * E extends Comparable<E>指的是 * E这个类型要实现Comparable接口，这样方便比较大小 *@author Edward *@date 2020年7月1日---上午11:33:51 */ public class Tree <E extends Comparable<E>>{ // root存放根节点的引用 private Node root; public Node getRoot() { return root; } public void setRoot(Node root) { this.root = root; } /* * Node类用于描述二叉树中的某个节点，其中， * data用于存放数据（元素）,left和right分别 * 存放其左右子树的引用。 */ class Node{ E data; Node left; Node right; Node(E e) { data = e; } public boolean append(E e) { // 相等不用添加（排序二叉树不允许重复元素） if (data.compareTo(e)==0) { return false; } // 如果要添加的元素比根节点元素小，则添加到左子树 if (data.compareTo(e)>0) { if (left==null) { left = new Node(e); return true; }else { return left.append(e); } }else { if (right==null) { right = new Node(e); return true; }else { return right.append(e); } } } // 用递归来写根本不需要考虑整体过程 // 只需要考虑核心的分解过程 // 是JVM中的栈做了底层实现 public void inOrder(StringBuilder sb) { // 左 if (left!=null) { left.inOrder(sb); } // 中 (本身) sb.append(data+","); // 右 if (right!=null) { right.inOrder(sb); } } } /** * 向二叉树当中添加某个元素 * @param e 被添加的元素 * @return 添加成功，返回true */ public boolean add(E e) { if (root==null) { root = new Node(e); return true; } return root.append(e); } public String toString(){ StringBuilder sb = new StringBuilder(); sb.append("["); root.inOrder(sb); sb.delete(sb.lastIndexOf(","), sb.length()); return sb.append("]").toString(); }

2、传入root节点的简洁递归（Normal）

List<E>list = new ArrayList<E>(); public List<E> inorderTraversalRecur(Node root) { // base case if (root==null) { return list; } inorderTraversalRecur(root.left); list.add(root.data); inorderTraversalRecur(root.right); return list; }

3、栈迭代（Hard）:

/** * stack迭代中序遍历BST * @return 返回BST的中序遍历集合 */ public List<E> inorderTraversal() { List<E>list = new ArrayList<E>(); Deque<Node>stack = new LinkedList<Node>(); while (root!=null||!stack.isEmpty()) { // 一路向左 while (root!=null) { stack.push(root); root = root.left; } // 走到尽头，出栈 root = stack.pop(); // 放入值 list.add(root.data); // 向右找 root = root.right; } return list; }

附测试方法：

package tree; /** *@author Edward *@date 2020年7月1日---下午2:18:59 */ public class TreeTest { public static void main(String[] args) { Tree<Integer>tree = new Tree<Integer>(); tree.add(88); tree.add(66); tree.add(120); tree.add(55); System.out.println(tree.getRoot()); System.out.println(tree.inorderTraversalRecur(tree.getRoot())); // 这个简洁Recur也没问题，只会输出一个正确的list System.out.println(tree.toString()); System.out.println(tree.inorderTraversal()); // 这个迭代会把root迭代成null，放在最后测试 } }