欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

二叉树的遍历(代码+图文详解)

程序员文章站 2022-03-26 16:40:05
二叉树的遍历(递归版和非递归版都有)代码+图解...

二叉树的遍历

  • 遍历实际上是指按照某个规则对二叉树中的每个节点进行操作,并且每个节点只操作一次(打印出二叉树的每一个节点内容或每个节点值域+1都算遍历)
  • 遍历方式有三种,分别是:
前序遍历 中序遍历 后序遍历
遍历方式 根-->左-->右 左-->根-->右 左-->右-->根
共同点 都是先遍历左子树,再遍历右子树
不同点 根节点的遍历次序不同

二叉树的遍历(代码+图文详解)

递归版遍历

  • 前序遍历
    二叉树的遍历(代码+图文详解)
 //前序递归遍历 public void preOrder(TreeNode root){ if(root != null) { System.out.print(root.val + " "); preOrder(root.left); preOrder(root.right); } } 
  • 中序遍历
    二叉树的遍历(代码+图文详解)
 //中序递归遍历 public void inOrder(TreeNode root){ if(root != null) { inOrder(root.left); System.out.print(root.val + " "); inOrder(root.right); } } 
  • 后序遍历
    二叉树的遍历(代码+图文详解)
 //后序递归遍历 public void lastOrder(TreeNode root){ if(root != null) { lastOrder(root.left); lastOrder(root.right); System.out.print(root.val + " "); } } 

非递归版遍历!!重要

一般递归转非递归有两种方式:循环和借用栈

根据递归遍历二叉树发现后递归的先退出,这样递归调用的返回的特性和栈的特性一样,所以可以利用栈来实现二叉树的非递归遍历

层序遍历的实现:

在写前序遍历之前可以先了解下层序遍历
二叉树的层序遍历实际上就是广度优先遍历,一层处理完后在处理下一层
二叉树的遍历(代码+图文详解)

 // 层序遍历 public void LevelOrder(){ if(null == root){ return; } Queue<BTNode> q = new LinkedList<>(); q.offer(root); while(!q.isEmpty()){ BTNode cur = q.poll(); System.out.print(cur.val); // 如果cur有左子树,让左子树入队列 if(null != cur.left){ q.offer(cur.left); } // 如果cur有右子树,让右子树入队列 if(null != cur.right){ q.offer(cur.right); } } System.out.println(); } 

前序遍历

前序非递归遍历第一种方式:
二叉树的遍历(代码+图文详解)

 //前序非递归遍历 public void preOrder1(TreeNode root){ if (root == null){ return; } Stack<TreeNode> s = new Stack<>(); s.push(root); //栈不为空 while(!s.empty()){ TreeNode cur = s.pop(); System.out.print(cur.val+" "); //因为栈是先进后出,所以如果想要先左后右的话就要先保存右子树再保存左子树 //判断当前节点是否有右子树,如果有右子树则让他入栈 if(null != cur.right){ s.push(cur.right); } //判断当前节点是否有左子树,如果有左子树则让他入栈 if(null != cur.left){ s.push(cur.left); } } } 

前序非递归遍历第二种方式:
二叉树的遍历(代码+图文详解)

 // 前序非递归第二种方式 public static void preOrder2(TreeNode root){ // 先判断树是否为空 if(root == null){ return; } Stack<TreeNode> s = new Stack<>(); s.push(root); if(!s.empty()){ TreeNode cur = s.pop(); if (cur != null){ System.out.println(cur.val + " "); // 顺着cur的左侧路径一路向下遍历,并保存途径的右子树 if(cur.right != null){ s.push(cur.right); } cur = cur.left; } } System.out.println(); } 

中序遍历

二叉树的遍历(代码+图文详解)

 public static void inOrder1(TreeNode root){ if(null == root){ return; } Stack<TreeNode> s = new Stack<>(); TreeNode cur = root; //中序遍历先遍历树的左子树 //所以首先要做的是从root开始找到最左节点,并保存路径上经过的节点 while(null != cur || !s.empty()){ while(null != cur){ s.push(cur); cur = cur.left; } //退出循环说明cur==null,此时栈顶元素就是二叉树最左侧节点 cur = s.pop(); System.out.print(cur.val+" "); //以cur为根的左子树和根遍历完了,还剩右子树 cur = cur.right; } System.out.println(); } 

后序遍历

二叉树的遍历(代码+图文详解)

 public static void lastOrder1(TreeNode root){ //还是先判断root是否为空 if(null == root){ return; } Stack<TreeNode> s = new Stack<>(); TreeNode cur = root; TreeNode prev = null; while(null != cur || !s.empty()){ // 找到最左结点,并且保存途径的所有结点 while(null != cur){ s.push(cur); cur = cur.left; } // cur为空说明左子树已经遍历完毕,获取右子树 // 获取右子树又需要获取到右子树的根节点,也就是当前栈顶元素 TreeNode top = s.peek(); // top的右子树为空,或右子树之前被遍历过,直接遍历根节点 if(top.right == null || prev == top.right){ System.out.print(top.val + " "); prev = s.pop(); }else { // 右子树没被遍历过 cur = top.right; } } System.out.println(); } 

本文地址:https://blog.csdn.net/qq_43360037/article/details/105913778

相关标签: Java