二叉树的遍历(代码+图文详解)
程序员文章站
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