龙空技术网

二叉树的四种遍历算法实现,没你想得那么难

阿风的架构笔记 914

前言:

现在大家对“二叉树算法的应用”大约比较珍视,朋友们都需要知道一些“二叉树算法的应用”的相关资讯。那么小编同时在网上网罗了一些有关“二叉树算法的应用””的相关文章,希望大家能喜欢,同学们一起来了解一下吧!

二叉树的遍历

我用下图的树为例,做树的遍历:

二叉树结构

树节点的定义:

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

标签: #二叉树算法的应用