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

二叉树的四种遍历算法实现,没你想得那么难对于一颗二叉查找树,所有的信息都是有序排列的,中序遍历可以是信息有序输出,且运行时间为O{if{printTree;System.out.pri

欢迎大家来到IT世界,在知识的湖畔探索吧!

二叉树的遍历

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

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

二叉树结构

树节点的定义

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);}

欢迎大家来到IT世界,在知识的湖畔探索吧!

中序遍历

  • 先处理左子树,然后处理当前节点,再处理右子树。
  • 对于一颗二叉查找树,所有的信息都是有序排列的,中序遍历可以是信息有序输出,且运行时间为O(n)。
  • 递归实现中序遍历:
欢迎大家来到IT世界,在知识的湖畔探索吧!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

先序遍历

  • 先处理当前节点,在处理左右子树。
  • 递归实现先序遍历:
欢迎大家来到IT世界,在知识的湖畔探索吧!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的节点之前进行处理,层序遍历与其他类型的遍历不同的地方在于它不是递归地执行的,它用到队列,而不使用递归所默示的栈。
  • 算法思想:
  1. 定义节点 TreeNode lastNode指向当前行最有节点,TreeNode nlastNode指向下一行最右节点。
  2. 利用队列,首先将根节点入队,再循环里出队,并将其子节点入队,定义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

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/34283.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们YX

mu99908888

在线咨询: 微信交谈

邮件:itzsgw@126.com

工作时间:时刻准备着!

关注微信