二叉树的四种遍历算法实现（Java实现）
2018-07-08 本文已影响2人
在北方玩弹子球
二叉树的遍历
-
我用下图的树为例，做树的遍历：
image
二叉树结构
- 树节点的定义：
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
super();
this.val = val;
this.left = left;
this.right = right;
}
}
树的结构的代码实现：
public static void main(String[] args) {
TreeNode e = new TreeNode(1);
TreeNode g = new TreeNode(2);
TreeNode h = new TreeNode(3);
TreeNode i = new TreeNode(4);
TreeNode d = new TreeNode(5,null,g);
TreeNode f = new TreeNode(6,h,i);
TreeNode b = new TreeNode(7,d,e);
TreeNode c = new TreeNode(8,f,null);
TreeNode root = new TreeNode(9,b,c);
}
中序遍历
- 先处理左子树，然后处理当前节点，再处理右子树。
- 对于一颗二叉查找树，所有的信息都是有序排列的，中序遍历可以是信息有序输出，且运行时间为O（n）。
- 递归实现中序遍历：
public static void printTree(TreeNode t){
if(t!=null){
printTree(t.left);
System.out.print(t.val+" ");
printTree(t.right);
}
}
- 输出结果：
5 2 7 1 9 3 6 4 8
后序遍历
- 先处理左右子树，然后再处理当前节点，运行时间为O（n）。
- 递归实现后序遍历：
public static void printTree(TreeNode t){
if(t!=null){
printTree(t.left);
printTree(t.right);
System.out.print(t.val+" ");
}
}
- 输出结果：
2 5 1 7 3 4 6 8 9
先序遍历
- 先处理当前节点，在处理左右子树。
- 递归实现先序遍历：
public static void printTree(TreeNode t){
if(t!=null){
System.out.print(t.val+" ");
printTree(t.left);
printTree(t.right);
}
}
- 输出结果：
9 7 5 2 1 8 6 3 4
- 有没有觉得树的先序，中序，后序遍历都非常简单，递归三行代码就搞定了。好吧，下边厉害的要来了
层序遍历
- 层序遍历:所有深度为D的节点要在深度为D+1的节点之前进行处理，层序遍历与其他类型的遍历不同的地方在于它不是递归地执行的，它用到队列，而不使用递归所默示的栈。
- 算法思想：
- 定义节点 TreeNode lastNode指向当前行最有节点，TreeNode nlastNode指向下一行最右节点。
- 利用队列，首先将根节点入队,再循环里出队,并将其子节点入队,定义TreeNode tmpNode节点指向当前出队列的节点，当tmpNode==lastNode时，代表当前行遍历结束，输出换行，再令lastNode=nlastNode，nlastNode在子节点入队列时指向下一行最右节点。循环直到对列为空就行。
- 层序遍历代码：
package Tree;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/*
* 层序遍历
*
*/
public class TreePrinter1 {
public static int[][] printTree(TreeNode root) {
List< List<Integer> > list = new ArrayList< List<Integer> >();
list.add(new ArrayList<Integer>());
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
TreeNode lastNode = root; // 当前行最右节点
TreeNode nlastNode = root; // 下一行最右节点
TreeNode tmpNode = null;
int hight = 0; // 树的高度
while(!queue.isEmpty()){
tmpNode = queue.poll();
if(tmpNode!=null){
list.get(hight).add(tmpNode.val);
}
if(tmpNode.left!=null){
queue.add(tmpNode.left);
nlastNode = tmpNode.left;
}
if(tmpNode.right!=null){
queue.add(tmpNode.right);
nlastNode = tmpNode.right;
}
if(tmpNode == lastNode){
lastNode = nlastNode;
hight++;
list.add(new ArrayList<Integer>());
}
}
int[][] data = new int[list.size()][];
for(int i=0;i<list.size();i++){
for(int j=0;j<list.get(i).size();j++){
data[i][j] = list.get(i).get(j);
}
}
return data;
}
public static void main(String[] args) {
TreeNode e = new TreeNode(1);
TreeNode g = new TreeNode(2);
TreeNode h = new TreeNode(3);
TreeNode i = new TreeNode(4);
TreeNode d = new TreeNode(5,null,g);
TreeNode f = new TreeNode(6,h,i);
TreeNode b = new TreeNode(7,d,e);
TreeNode c = new TreeNode(8,f,null);
TreeNode root = new TreeNode(9,b,c);
int[][] data =TreePrinter.printTree(root);
for(int s=0;s<data.length;s++){
for(int j=0;j<data[s].length;j++){
System.out.print(data[s][j]+" ");
}
System.out.println();
}
}
}
- 输出结果：
9
7 8
5 1 6
2 3 4
在我的与专栏同名公众号【轮子工厂】后台回复关键字：
1.回复【图书】：获取15本新手自学编程，零基础入门经典学习教材；
2.回复【我要造轮子】：获取100多本我根据知乎上面关于计算机问题的高赞回答里面的介绍整理出来的书籍；
3.回复【开发工具】：获取几大主流编程语言的开发工具～
4.回复【ps教程】：获取ps视频免费教程；
