在前序遍历中，每个结点都是在它的子树遍历之前进行处理，这是最容易理解的便利方法，然而，尽管每个结点在其子树之前进行了处理，但在向下移动的过程仍然需要保留一些信息，以上图为例，首先访问结点1，随后遍历其左子树，最后遍历其右子树，因此当左子树遍历完后，必须要返回到其右子树来继续遍历；为了能够在左子树遍历完成后移动到右子树，必须保留根节点的信息，能够实现该信息存储的抽象数据类型显而易见是栈，由于它是LIFO的结构，所以它可以以逆序来汇过去该信息并返回到右子树；
前序遍历可以如下定义：
访问根节点；
按前序遍历方式遍历左子树；
按前序遍历方式遍历右子树；
利用前序遍历方法上图所示的树的输出序列为：1 2 4 5 3 6 7
void preOrder(BinaryTreeNode root) { if (null != root) { System.out.println(root.getData()); preOrder(root.getLeft()); preOrder(root.getRight()); } } 中序遍历在中序遍历中，根节点的访问在两棵子树的遍历中间完成，中序遍历如下定义：
按中序遍历方式遍历左子树；
访问根节点；
按中序遍历方式遍历右子树；
基于中序遍历，上图所示树的中序遍历输出顺序为：4 2 5 1 6 3 7
void inOrder(BinaryTreeNode root) { if (null != root) { inOrder(root.getLeft()); System.out.println(root.getData()); inOrder(root.getRight()); } } 后序遍历在后续遍历中，根节点的访问是在其两棵子树都遍历完成后进行的，后续遍历如下定义：
按后序遍历左子树；
按后序遍历右子树；
访问根节点；
对上图所示的二叉树，后续遍历产生的输出序列为：4 5 2 6 7 3 1
void postOrder(BinaryTreeNode root) { if (null != root) { postOrder(root.getLeft()); postOrder(root.getRight()); System.out.println(root.getData()); } } 层次遍历层次遍历的定义如下：
访问根节点；
在访问第l层时，将l+1层的节点按顺序保存在队列中；
进入下一层并访问该层的所有结点；
重复上述操作直至所有层都访问完；
对于上图所示的二叉树，层次遍历产生的输出序列为：1 2 3 4 5 6 7
void levelOrder(BinaryTreeNode root) { BinaryTreeNode temp; LoopQueue Q = new LoopQueue(); if (null == root) { return; } Q.enqueue(root); while (!Q.isEmpty()) { temp = Q.dequeue(); // 处理当前节点 System.out.println(temp.getData()); if (temp.getLeft()) { Q.enqueue(temp.getLeft()); } if (temp.getRight()) { Q.enqueue(temp.getRight()); } } // 删除队列中的所有数据 Q.deletequeue(); } 二叉搜索树在二叉搜索树中，所有左子树结点的元素小于根节点的数据，所有右子树结点的元素大于根节点数据，注意，树中的每个结点都应满足这个性质；
其中包含了常用的一些方法，包括几种遍历方法还有查询、删除等，仅供参考：
public class BST<E extends Comparable<E>> { private class Node{ public E e; public Node left, right; public Node(E e){ this.e = e; left = null; right = null; } } private Node root; private int size; public BST(){ root = null; size = 0; } public int size(){ return size; } public boolean isEmpty(){ return size == 0; } // 向二分搜索树中添加新的元素e public void add(E e){ root = add(root, e); } // 向以node为根的二分搜索树中插入元素e，递归算法 // 返回插入新节点后二分搜索树的根 private Node add(Node node, E e){ if(node == null){ size ++; return new Node(e); } if(e.compareTo(node.e) < 0) node.left = add(node.left, e); else if(e.compareTo(node.e) > 0) node.right = add(node.right, e); return node; } // 看二分搜索树中是否包含元素e public boolean contains(E e){ return contains(root, e); } // 看以node为根的二分搜索树中是否包含元素e, 递归算法 private boolean contains(Node node, E e){ if(node == null) return false; if(e.compareTo(node.e) == 0) return true; else if(e.compareTo(node.e) < 0) return contains(node.left, e); else // e.compareTo(node.e) > 0 return contains(node.right, e); } // 二分搜索树的前序遍历 public void preOrder(){ preOrder(root); } // 前序遍历以node为根的二分搜索树, 递归算法 private void preOrder(Node node){ if(node == null) return; System.out.println(node.e); preOrder(node.left); preOrder(node.right); } // 二分搜索树的非递归前序遍历 public void preOrderNR(){ Stack<Node> stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()){ Node cur = stack.pop(); System.out.println(cur.e); if(cur.right != null) stack.push(cur.right); if(cur.left != null) stack.push(cur.left); } } // 二分搜索树的中序遍历 public void inOrder(){ inOrder(root); } // 中序遍历以node为根的二分搜索树, 递归算法 private void inOrder(Node node){ if(node == null) return; inOrder(node.left); System.out.println(node.e); inOrder(node.right); } // 二分搜索树的后序遍历 public void postOrder(){ postOrder(root); } // 后序遍历以node为根的二分搜索树, 递归算法 private void postOrder(Node node){ if(node == null) return; postOrder(node.left); postOrder(node.right); System.out.println(node.e); } // 二分搜索树的层序遍历 public void levelOrder(){ Queue<Node> q = new LinkedList<>(); q.add(root); while(!q.isEmpty()){ Node cur = q.remove(); System.out.println(cur.e); if(cur.left != null) q.add(cur.left); if(cur.right != null) q.add(cur.right); } } // 寻找二分搜索树的最小元素 public E minimum(){ if(size == 0) throw new IllegalArgumentException("BST is empty!"); return minimum(root).e; } // 返回以node为根的二分搜索树的最小值所在的节点 private Node minimum(Node node){ if(node.left == null) return node; return minimum(node.left); } // 寻找二分搜索树的最大元素 public E maximum(){ if(size == 0) throw new IllegalArgumentException("BST is empty"); return maximum(root).e; } // 返回以node为根的二分搜索树的最大值所在的节点 private Node maximum(Node node){ if(node.right == null) return node; return maximum(node.right); } // 从二分搜索树中删除最小值所在节点, 返回最小值 public E removeMin(){ E ret = minimum(); root = removeMin(root); return ret; } // 删除掉以node为根的二分搜索树中的最小节点 // 返回删除节点后新的二分搜索树的根 private Node removeMin(Node node){ if(node.left == null){ Node rightNode = node.right; node.right = null; size --; return rightNode; } node.left = removeMin(node.left); return node; } // 从二分搜索树中删除最大值所在节点 public E removeMax(){ E ret = maximum(); root = removeMax(root); return ret; } // 删除掉以node为根的二分搜索树中的最大节点 // 返回删除节点后新的二分搜索树的根 private Node removeMax(Node node){ if(node.right == null){ Node leftNode = node.left; node.left = null; size --; return leftNode; } node.right = removeMax(node.right); return node; } // 从二分搜索树中删除元素为e的节点 public void remove(E e){ root = remove(root, e); } // 删除掉以node为根的二分搜索树中值为e的节点, 递归算法 // 返回删除节点后新的二分搜索树的根 private Node remove(Node node, E e){ if( node == null ) return null; if( e.compareTo(node.e) < 0 ){ node.left = remove(node.left , e); return node; } else if(e.compareTo(node.e) > 0 ){ node.right = remove(node.right, e); return node; } else{ // e.compareTo(node.e) == 0 // 待删除节点左子树为空的情况 if(node.left == null){ Node rightNode = node.right; node.right = null; size --; return rightNode; } // 待删除节点右子树为空的情况 if(node.right == null){ Node leftNode = node.left; node.left = null; size --; return leftNode; } // 待删除节点左右子树均不为空的情况 // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点 // 用这个节点顶替待删除节点的位置 Node successor = minimum(node.right); successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; } } @Override public String toString(){ StringBuilder res = new StringBuilder(); generateBSTString(root, 0, res); return res.toString(); } // 生成以node为根节点，深度为depth的描述二叉树的字符串 private void generateBSTString(Node node, int depth, StringBuilder res){ if(node == null){ res.append(generateDepthString(depth) + "null\n"); return; } res.append(generateDepthString(depth) + node.e +"\n"); generateBSTString(node.left, depth + 1, res); generateBSTString(node.right, depth + 1, res); } private String generateDepthString(int depth){ StringBuilder res = new StringBuilder(); for(int i = 0 ; i < depth ; i ++) res.append("--"); return res.toString(); } } LeetCode相关题目整理 94.二叉树的中序遍历