二叉树遍历是树的最基本算法之一，是二叉树上进行其它运算之基础。
所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。
访问结点所做的操作依赖于具体的应用问题。① 前序遍历(PreorderTraversal亦称（先序遍历））
――访问根结点的操作发生在遍历其左右子树之前。
② 中序遍历(InorderTraversal)
――访问根结点的操作发生在遍历其左右子树之中（间）。
③ 后序遍历(PostorderTraversal)
――访问根结点的操作发生在遍历其左右子树之后。
④ 层次遍历(LevelTraversal)
――访问从根结点开始，逐层访问
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;
//二叉树的链式结构
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class TestTraversalTreeNode {
/**
* 线序遍历
*
* @param root 树根
* @return
*/
public static ArrayList
preorderTraversal(TreeNode root) {
ArrayList
result = new ArrayList
(); if (root == null) return result; Stack
stack = new Stack
(); stack.push(root); while (!stack.isEmpty()) { TreeNode t = stack.pop(); result.add(t.val); //先检查push右结点 if (t.right != null) { stack.push(t.right); } if (t.left != null) { stack.push(t.left); } } return result; } /** * 中序遍历 * * @param root 树根 * @return */ public static ArrayList
inorderTraversal(TreeNode root) { ArrayList
result = new ArrayList
(); if (root == null) return result; Stack
stack = new Stack
(); TreeNode p = root; //如果有左结点则一直push while (!stack.isEmpty() || p != null) { if (p != null) { stack.push(p); p = p.left; } else { TreeNode n = stack.pop(); result.add(n.val); p = n.right; } } return result; } /** * 后序遍历 * * @param root 树根 * @return */ public static ArrayList
postorderTraversal(TreeNode root) { ArrayList
result = new ArrayList
(); if (root == null) { return result; } Stack
stack = new Stack
(); stack.push(root); TreeNode prev = null;// 记录当前结点的上一个结点 while (!stack.empty()) { TreeNode curr = stack.peek(); // 查看当前结点是否是叶节点，是的话就访问 if (prev == null || prev.left == curr || prev.right == curr) { if (curr.left != null) { stack.push(curr.left); } else if (curr.right != null) { stack.push(curr.right); } else {// 当前结点是叶节点 stack.pop(); result.add(curr.val); } // 查看prev是否是的当前结点左结点 } else if (curr.left == prev) { if (curr.right != null) { stack.push(curr.right); } else { stack.pop(); result.add(curr.val); } // 查看prev是否是当前结点的右结点 } else if (curr.right == prev) { stack.pop(); result.add(curr.val); } prev = curr; } return result; } /** * 层次遍历 * * @param root 树根 * @return */ public static ArrayList
levelTraversal(TreeNode root) { ArrayList
result = new ArrayList
(); LinkedList
current = new LinkedList
(); if (root != null) { current.add(root); result.add(root.val); } while (current.size() > 0) { LinkedList
parents = current; current = new LinkedList
(); for (TreeNode parent : parents) { if (parent.left != null) { current.add(parent.left); result.add(parent.left.val); } if (parent.right != null) { current.add(parent.right); result.add(parent.right.val); } } } return result; } /** * 遍历二叉树的第k行 * * @param root 二叉树根 * @param k 第k行 * @return 第k行的遍历 */ public static String findLevelList2(TreeNode root, int k) { ArrayList
> result = new ArrayList
>(); LinkedList
current = new LinkedList
(); if (root != null) { current.add(root); } int count = 0; while (current.size() > 0) { result.add(current); if (count == k) { return listToString(current); } count++; LinkedList
parents = current; current = new LinkedList
(); for (TreeNode parent : parents) { if (parent.left != null) { current.add(parent.left); } if (parent.right != null) { current.add(parent.right); } } } return null; } /** * 链表的结点转化为字符串进行输出 * @p