本篇内容主要讲解“Java实现二叉树的遍历方法是什么”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“Java实现二叉树的遍历方法是什么”吧!
遍历二叉树
遍历或称周游，traversal。系统地访问数据结构中的节点，每个节点都正好被访问到一次。
深度优先遍历二叉树
三种深度优先遍历的递归定义：
-
前序法（tLR次序，preorder traversal）：访问根结点，按前序遍历左子树；按前序遍历右子树。
-
中序法（LtR次序，inorder traversal）：按中序遍历左子树；访问根结点；按中序遍历右子树。
-
后序法（LRt次序，postorder traversal）：按后序遍历左子树；按后序遍历右子树；访问根结点。
递归的前序、中序、后序
public static List<Integer> preOrderTraverseByRecursionBinaryTreeNode root, List<Integer> list) {
if root != null) {
list.addroot.getKey));//前序法访问节点
preOrderTraverseByRecursionroot.getLeft), list);
//list.addroot.getKey));//中序法访问节点
preOrderTraverseByRecursionroot.getRight), list);
//list.addroot.getKey));//后序法访问节点
}
return list;
}
非递归遍历
递归算法非常简洁，推荐使用，当前的编译系统优化效率很不错了。特殊情况用栈模拟递归，深度优先遍历的回溯特点和栈的工作原理一致，有些应用环境资源限制不适合递归。
非递归的前序遍历
实现
/**
* 先序遍历（非递归）
* 通过栈来避免递归（有节点入栈）
*
* @param root
*/
public static List<Integer> preOrderTraverseByNonRecursionBinaryTreeNode root) {
List<Integer> list = new ArrayList<>);// 用于存放遍历后的结果
Stack<BinaryTreeNode> stack = new Stack);// 用于存放右子树节点
BinaryTreeNode p = root;
//左子树和右子树都未遍历时，遍历
while p != null || stack.size) > 0) {
if p != null) { //左子树不为空时，遍历左子树
list.addp.getKey));//当前节点输出
stack.pushp.getRight));//右子树入栈，待左子树遍历完后遍历右子树
p = p.getLeft);//遍历左子树
} else { //左子树遍历完后，遍历右子树
p = stack.pop);
}
}
return list;
}
非递归的中序遍历
实现
/**
* 中序遍历（非递归）
*
* @param root
*/
public static List<Integer> inOrderTraverseByNonRecursionBinaryTreeNode root) {
List<Integer> list = new ArrayList<>);
Stack<BinaryTreeNode> stack = new Stack<>);
BinaryTreeNode current = root;
//遍历节点的左子树并将根结点入栈，直到左子树为null时，然后出栈获取节点并遍历该节点的右子树的左子树直到为null
whilecurrent != null || !stack.empty)){
ifcurrent != null){
stack.pushcurrent);
current = current.getLeft);
}else{
BinaryTreeNode top = stack.pop);
list.addtop.getKey));
current = top.getRight);
}
}
return list;
}
非递归的后序遍历
实现
/**
* 后续遍历（非递归）
*
* @param root
*/
public static List<Integer> postOrderTraverseByNonRecursionBinaryTreeNode root) {
Stack<BinaryTreeNode> stack = new Stack<>);
List<Integer> list = new ArrayList<>);
stack.pushroot);
BinaryTreeNode current;
while stack.isEmpty) == false) {
current = stack.pop);
if current != null) {
list.addcurrent.getKey));
stack.pushcurrent.getLeft));
stack.pushcurrent.getRight));
}
}
Collections.reverselist);
return list;
}
宽度优先遍历二叉树
从二叉树的第0层（根结点）开始，自上而下，追层遍历；在同一层中，按照从左到右的顺序对节点逐一访问。 特点是先遍历先访问，符合队列的特征，通过队列来实现。 实现如下：
/**
* 层序遍历（宽度优先遍历）
* 特点是先进先出，符合队列的特性
*
* @param root
* @return
*/
public static List<Integer> layerOrderTraverseBinaryTreeNode root) {
List<Integer> list = new ArrayList<>);
LinkedList<BinaryTreeNode> queue = new LinkedList<>);
BinaryTreeNode current;
queue.offerroot);
while !queue.isEmpty)){
current = queue.poll);
list.addcurrent.getKey));
ifcurrent.getLeft) != null){
queue.addLastcurrent.getLeft));
}
ifcurrent.getRight) != null){
queue.addLastcurrent.getRight));
}
}
return list;
}
根据遍历序列构造二叉树
先来个结论及说明：
-
仅一个先（中、后）序序列不能构造唯一一颗二叉树（原因：无法确定左右子树或根结点）
-
仅先（后）序序列和中序序列可以构造唯一一颗二叉树（原因：先序序列和后序序列无法构造唯一一颗二叉树）
-
用扩充先（后）序序列可以构造唯一一颗二叉树
-
用扩充中序序列不能构造唯一一颗二叉树
先序序列和中序序列创建构造二叉树
实现：
/**
* 根据先序序列和中序序列构造二叉树（递归实现）
* <p>
* 先序序列第一个元素是树的根结点，从中序序列中找出与根结点所在位置k:
* 1.确定根结点的左子树和右子树的中序序列：该位置之前的元素就是根结点左子树的中序序列，该位置之后的元素就是根结点的右子树的中序序列
* 2.确定根结点的左子树和右子树的先序序列：先序序列第一个元素往后k元素就是根结点左子树的先序序列，k+1位置之后就是根结点右子树的先序序列
* <p>
* <p>
* perOrder[i]~perOrder[j] 是子树的先序序列
* inOrder[s]~inOrder[t] 是子树的中序序列
*
* @param perOrder
* @param inOrder
* @param i
* @param j
* @param s
* @param t
* @return
*/
public static BinaryTreeNode buildTreeByPerOrderAndInOrderInteger[] perOrder, Integer[] inOrder, int i, int j, int s, int t) {
if i > j) {
return null;
}
BinaryTreeNode root = new BinaryTreeNodeperOrder[i]);
int k;
k = s;
while k <= t && inOrder[k] != perOrder[i]) {
k++;
}
if k > t) {
return null;
}
root.setLeftbuildTreeByPerOrderAndInOrderperOrder, inOrder, i + 1, j + k - s, s, k - 1));
root.setRightbuildTreeByPerOrderAndInOrderperOrder, inOrder, i + k - s + 1, j, k + 1, t));
return root;
}
后序序列和中序序列创建构造二叉树
一个节点的左子树和右子树存在三种组合方式，左子树为null，右子树为null，左右子树都不为null。 运用递归思想时，按这三种情况分析左右子树的后序序列和中序序列。实现如下：
/**
* 根据后序序列和中序序列构造二叉树（递归实现）
*
* postOrder[i]~postOrder[j]是子树的后序序列
* inOrder[s]~inOrder[t]是子树的中序序列
*
* @param postOrder
* @param inOrder
* @param i
* @param j
* @param s
* @param t
* @return
*/
public static BinaryTreeNode buildTreeByPostOrderAndInOrderInteger[] postOrder, Integer[] inOrder, int i, int j, int s, int t) {
if i > j) {
return null;
}
BinaryTreeNode root = new BinaryTreeNodepostOrder[j]);
int k;
k = s;
while k <= t && inOrder[k] != postOrder[j]) {
k++;
}
if k > t) {
return null;
}
//左子树个数
int countLeft = k - s;
//右子树个数
int countRight = t - k;
if countLeft == 0) {
//左子树为null
root.setRightbuildTreeByPostOrderAndInOrderpostOrder, inOrder, j - countRight, j - 1, t - countRight + 1, t));
} else if countRight == 0) {
//右子树为null
root.setLeftbuildTreeByPostOrderAndInOrderpostOrder, inOrder, j - countLeft, j - 1, t - countLeft, t - countRight - 1));
} else {
//左、右子树不为null
root.setLeftbuildTreeByPostOrderAndInOrderpostOrder, inOrder, i, i + countLeft - 1, s, s + countLeft - 1));
root.setRightbuildTreeByPostOrderAndInOrderpostOrder, inOrder, j - 1 - countRight + 1, j - 1, t - countRight + 1, t));
}
return root;
}