瑞_数据结构与算法_二叉树

文章目录 1 什么是二叉树2 二叉树的存储2.1 使用树节点类TreeNode存储（代码）2.2 使用数组存储 3 二叉树的遍历3.1 广度优先遍历3.2 深度优先遍历3.2.1 深度优先——前序遍历3.2.2 深度优先——中序遍历3.2.3 深度优先——后序遍历 3.3 代码实现3.3.1 递归实现——深度优先遍历3.3.2 非递归实现——深度优先遍历3.3.2.1 前序遍历3.3.2.2 中序遍历3.3.2.3 后序遍历3.3.2.4 非递归实现深度优先——统一写法★★★ 力扣题144 二叉树的前序遍历力扣题94 二叉树的中序遍历力扣题145. 二叉树的后序遍历

🙊前言：本文章为瑞_系列专栏之《数据结构与算法》的二叉树篇。由于博主是从B站黑马程序员的《数据结构与算法》学习到的相关知识，所以本系列专栏主要针对该课程进行笔记总结和拓展，文中的部分原理及图解也是来源于黑马提供的资料。本文仅供大家交流、学习及研究使用，禁止用于商业用途，违者必究！

1 什么是二叉树

  二叉树是一种树状结构：每个节点最多有两个孩子，左孩子和右孩子。

  重要的二叉树结构：

完全二叉树（complete binary tree）是一种二叉树结构，除最后一层以外，每一层都必须填满，填充时要遵从先左后右。平衡二叉树（balance binary tree）是一种二叉树结构，其中每个节点的左右子树高度相差不超过 1 。

---

2 二叉树的存储

  二叉树的存储方式一般分为：使用树节点类TreeNode存储、使用数组存储。

2.1 使用树节点类TreeNode存储（代码）

  定义树节点与左、右孩子引用（TreeNode），参考代码如下：

public class TreeNode { /** * 节点值 */ public int val; /** * 左孩子 */ public TreeNode left; /** * 右孩子 */ public TreeNode right; public TreeNode(int val) { this.val = val; } public TreeNode(TreeNode left, int val, TreeNode right) { this.left = left; this.val = val; this.right = right; } @Override public String toString() { return String.valueOf(this.val); } } 2.2 使用数组存储

  类似于使用数组实现堆，数组索引为 0 处即是根节点，索引为 1 处即是根节点的左孩子，索引为 2 处即是根节点的右孩子，没有元素则使用null表示。

  若以 0 作为树的根，索引可以通过如下方式计算：

父 = floor((子 - 1) / 2)左孩子 = 父 * 2 + 1右孩子 = 父 * 2 + 2

瑞：实际过程中按照业务需求自己选定，两种存储的表示方式都可行，没有对错，只有适合和更适合

---

3 二叉树的遍历

  遍历主要分为以下两种：

广度优先遍历（Breadth-first order）：尽可能先访问距离根最近的节点，也称为层序遍历深度优先遍历（Depth-first order）：对于二叉树，可以进一步分成三种（要深入到叶子节点） pre-order 前序遍历，对于每一棵子树，先访问该节点，然后是左子树，最后是右子树in-order 中序遍历，对于每一棵子树，先访问左子树，然后是该节点，最后是右子树post-order 后序遍历，对于每一棵子树，先访问左子树，然后是右子树，最后是该节点 3.1 广度优先遍历

  广度优先遍历（Breadth-first order）：尽可能先访问距离根最近的节点，也称为层序遍历，即“Z”字型遍历，如下图：

  用队列来层序遍历是针对 TreeNode 这种方式表示的二叉树，如下表所示：

本轮开始时队列本轮访问节点[1]1[2, 3]2[3, 4]3[4, 5, 6]4[5, 6]5[6, 7, 8]6[7, 8]7[8]8[]

  如上表所示，步骤为：

初始化，将根节点加入队列循环处理队列中每个节点，直至队列为空每次循环内处理节点后，将它的孩子节点（即下一层的节点）加入队列

  对于数组表现的二叉树，则直接遍历数组即可，自然为层序遍历的顺序

3.2 深度优先遍历

  深度优先遍历（Depth-first order）：对于二叉树，可以进一步分成三种（要深入到叶子节点）

pre-order 前序遍历，对于每一棵子树，先访问该节点，然后是左子树，最后是右子树in-order 中序遍历，对于每一棵子树，先访问左子树，然后是该节点，最后是右子树post-order 后序遍历，对于每一棵子树，先访问左子树，然后是右子树，最后是该节点

3.2.1 深度优先——前序遍历

  前序遍历规则：

先访问该节点然后是左子树最后是右子树

  按照前序遍历规则，执行顺序为：先访问根节点1（打印1），然后访问根节点1的左子树2（打印2），然后访问2的左子树4（打印4），由于4左右子树为null，所以4访问结束。退回到2，2的左子树已经遍历完了，右子树为null，即2遍历结束。退回到1，1的左子树已经遍历结束，开始遍历1的右子树3（打印3），访问3的左子树5（打印5），5的左右子树为null，退回到3，访问3的右子树6（打印6），前序遍历结束。

前序遍历的结果为：1,2,4,3,5,6 瑞：根左右

3.2.2 深度优先——中序遍历

  中序遍历规则：

先访问左子树然后是该节点最后是右子树

  按照中序遍历规则，左子树没遍历完之前是不能打印该节点的值，所以执行顺序为：先访问根节点1（不打印），然后访问根节点1的左子树2（不打印），然后访问2的左子树4（不打印），由于4左子树为null，所以此时打印4（打印4），4的右子树为null，4遍历结束。退回到2，2的左子树已经遍历完了，所以此时打印2（打印2），2的右子树为null，即2遍历结束。退回到1，1的左子树已经遍历结束，此时打印1（打印1），开始遍历1的右子树3（不打印），访问3的左子树5（不打印），5的左子树为null，所以此时打印5（打印5），5的右子树为null，5遍历结束。退回到3，3的左子树已经遍历完了，所以此时打印3（打印3），开始访问3的右子树6（不打印），6的左子树为null，所以此时打印6（打印6），6的右子树为null，中序遍历结束。

中序遍历的结果为：4,2,1,5,3,6 瑞：左根右

3.2.3 深度优先——后序遍历

  后序遍历规则：

先访问左子树然后是右子树最后是该节点

  按照后序遍历规则，左右子树没遍历完之前是不能打印该节点的值，所以执行顺序为：先访问根节点1（不打印），然后访问根节点1的左子树2（不打印），然后访问2的左子树4（不打印），由于4左子树为null、右子树为null，所以此时打印4（打印4），4遍历结束。退回到2，2的左子树已经遍历完了，2的右子树为null，所以此时打印2（打印2），即2遍历结束。退回到1，1的左子树已经遍历结束，开始遍历1的右子树3（不打印），开始遍历1的右子树3（不打印），访问3的左子树5（不打印），5的左子树为null、5的右子树为null，所以此时打印5（打印5），5遍历结束。退回到3，3的左子树已经遍历完了，开始访问3的右子树6（不打印），6的左子树为null、6的右子树为null，所以此时打印6（打印6），6遍历结束。退回到3，3的左右子树遍历结束，所以此时打印3（打印3），退回到1，1的左右子树遍历结束，所以此时打印1（打印1） ，后序遍历结束。

后序遍历的结果为：4,2,5,6,3,1 瑞：左右根

瑞：不用特别死记硬背，因为左子树的遍历一定在右子树之前，所以前中后指的就是打印左右节点前该节点的打印顺序。比如前序遍历就是在左右子树遍历前（根左右），中序遍历就是左子树打印完之后打印该节点再打印右子树（左根右），后续遍历就是左右子树打印完再打印该节点（左右根），就是根的位置在左右子树的位置就是前中后序的区别

3.3 代码实现

  以下实现均需要使用TreeNode类，在文章 2.1 使用树节点类TreeNode存储（代码）

  构建本例中的树型结构的代码如下：

/* 1 / \ 2 3 / / \ 4 5 6 */ TreeNode root = new TreeNode( new TreeNode(new TreeNode(4), 2, null), 1, new TreeNode(new TreeNode(5), 3, new TreeNode(6)) ); 3.3.1 递归实现——深度优先遍历

  使用递归实现比较简单，代码如下：

public class TreeTraversal { public static void main(String[] args) { /* 1 / \ 2 3 / / \ 4 5 6 */ TreeNode root = new TreeNode( new TreeNode(new TreeNode(4), 2, null), 1, new TreeNode(new TreeNode(5), 3, new TreeNode(6)) ); System.out.print("前序遍历：\t"); preOrder(root); System.out.println(); System.out.print("中序遍历：\t"); inOrder(root); System.out.println(); System.out.print("后序遍历：\t"); postOrder(root); System.out.println(); } /** * 前序遍历 * * @param node 节点 */ static void preOrder(TreeNode node) { if (node == null) { return; } System.out.print(node.val + "\t"); // 值 preOrder(node.left); // 左 preOrder(node.right); // 右 } /** * 中序遍历 * * @param node 节点 */ static void inOrder(TreeNode node) { if (node == null) { return; } inOrder(node.left); // 左 System.out.print(node.val + "\t"); // 值 inOrder(node.right); // 右 } /** * 后序遍历 * * @param node 节点 */ static void postOrder(TreeNode node) { if (node == null) { return; } postOrder(node.left); // 左 postOrder(node.right); // 右 System.out.print(node.val + "\t"); // 值 } }

以上代码运行结果： 前序遍历： 1 2 4 3 5 6 中序遍历： 4 2 1 5 3 6 后序遍历： 4 2 5 6 3 1

  复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(log⁡ n)，最坏情况下树呈现链状，为 O(n)。 3.3.2 非递归实现——深度优先遍历

  由于树型结构中没有保存父节点元素，所以需要使用栈（后进先出特性）来存储来回的路，本质上是在模拟递归，因为在递归的过程中使用了系统栈。可以使用自定义实现的栈类或者使用JDK1.8中自带的LinkedList<E>类，该类实现了Deque接口，即含有栈的相关方法。注意不建议使用Stack类，官方建议使用Deque接口及其实现类来实现的栈功能，具体原因本文不进行阐述。

3.3.2.1 前序遍历 LinkedListStack<TreeNode> stack = new LinkedListStack<>(); TreeNode curr = root; while (!stack.isEmpty() || curr != null) { if (curr != null) { stack.push(curr); System.out.println(curr); curr = curr.left; } else { TreeNode pop = stack.pop(); curr = pop.right; } } 3.3.2.2 中序遍历 LinkedListStack<TreeNode> stack = new LinkedListStack<>(); TreeNode curr = root; while (!stack.isEmpty() || curr != null) { if (curr != null) { stack.push(curr); curr = curr.left; } else { TreeNode pop = stack.pop(); System.out.println(pop); curr = pop.right; } } 3.3.2.3 后序遍历 LinkedListStack<TreeNode> stack = new LinkedListStack<>(); TreeNode curr = root; TreeNode pop = null; while (!stack.isEmpty() || curr != null) { if (curr != null) { stack.push(curr); curr = curr.left; } else { TreeNode peek = stack.peek(); if (peek.right == null || peek.right == pop) { pop = stack.pop(); System.out.println(pop); } else { curr = peek.right; } } }

  对于后序遍历，向回走时，需要处理完右子树才能 pop 出栈。如何知道右子树处理完成呢？

如果栈顶元素的 right == null 表示没啥可处理的，可以出栈如果栈顶元素的 right ≠null， 那么使用 lastPop 记录最近出栈的节点，即表示从这个节点向回走如果栈顶元素的 right == lastPop 此时应当出栈

  对于前、中两种遍历，实际以上代码从右子树向回走时，并未走完全程（stack 提前出栈了）后序遍历以上代码是走完全程了

3.3.2.4 非递归实现深度优先——统一写法★★★

  下面是一种统一的写法，依据后序遍历修改，可根据前中后需求自定义修改

import java.util.LinkedList; /** * 非递归实现 深度优先遍历 三种遍历通用写法 * * @author LiaoYuXing-Ray * @version 1.0 * @createDate 2024/1/22 15:09 **/ public class RayTest { public static void preorderTraversal(TreeNode root) { LinkedList<TreeNode> stack = new LinkedList<>(); // 栈 TreeNode curr = root; // 代表当前节点 TreeNode pop = null; // 最近一次弹栈的元素 while (curr != null || !stack.isEmpty()) { if (curr != null) { colorPrintln("前: " + curr.val, 31); stack.push(curr); // 压入栈，为了记住回来的路 curr = curr.left; } else { TreeNode peek = stack.peek(); // 右子树可以不处理, 对中序来说, 要在右子树处理之前打印 if (peek.right == null) { colorPrintln("中: " + peek.val, 35); pop = stack.pop(); colorPrintln("后: " + pop.val, 34); } // 右子树处理完成, 对中序来说, 无需打印 else if (peek.right == pop) { pop = stack.pop(); colorPrintln("后: " + pop.val, 34); } // 右子树待处理, 对中序来说, 要在右子树处理之前打印 else { colorPrintln("中: " + peek.val, 35); curr = peek.right; } } } } public static void main(String[] args) { TreeNode root = new TreeNode( new TreeNode(new TreeNode(4), 2, null), 1, new TreeNode(new TreeNode(5), 3, new TreeNode(6)) ); preorderTraversal(root); } /* 31 红 32 黄 33 橙 34 蓝 35 紫 36 绿 */ public static void colorPrintln(String origin, int color) { System.out.printf("\033[%dm%s\033[0m%n", color, origin); } }

  复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。空间复杂度：O(n)，为迭代过程中显式栈的开销，平均情况下为 O(log n)，最坏情况下树呈现链状，为 O(n)

---

力扣题144 二叉树的前序遍历

Leetcode144. 二叉树的前序遍历

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<Integer> preorderTraversal(TreeNode root) { /* * 栈 */ LinkedList<TreeNode> stack = new LinkedList<>(); /* * 代表当前节点 */ TreeNode current = root; /* * 最近一次弹栈的元素 */ TreeNode pop = null; List<Integer> result = new ArrayList<>(); while (!stack.isEmpty() || current != null) { if (current != null) { stack.push(current); // 待处理左子树 result.add(current.val); current = current.left; } else { TreeNode peek = stack.peek(); // 没有右子树 if (peek.right == null) { // 获取最近一次弹栈的元素 pop = stack.pop(); } // 右子树处理完成 else if (peek.right == pop) { // 获取最近一次弹栈的元素 pop = stack.pop(); } // 待处理右子树 else { current = peek.right; } } } return result; } } 力扣题94 二叉树的中序遍历

Leetcode94. 二叉树的中序遍历

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<Integer> inorderTraversal(TreeNode root) { /* * 栈 */ LinkedList<TreeNode> stack = new LinkedList<>(); /* * 代表当前节点 */ TreeNode current = root; /* * 最近一次弹栈的元素 */ TreeNode pop = null; List<Integer> result = new ArrayList<>(); while (!stack.isEmpty() || current != null) { if (current != null) { stack.push(current); // 待处理左子树 current = current.left; } else { TreeNode peek = stack.peek(); // 没有右子树 if (peek.right == null) { result.add(peek.val); // 获取最近一次弹栈的元素 pop = stack.pop(); } // 右子树处理完成 else if (peek.right == pop) { // 获取最近一次弹栈的元素 pop = stack.pop(); } // 待处理右子树 else { result.add(peek.val); current = peek.right; } } } return result; } } 力扣题145. 二叉树的后序遍历

Leetcode145. 二叉树的后序遍历

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<Integer> postorderTraversal(TreeNode root) { /* * 栈 */ LinkedList<TreeNode> stack = new LinkedList<>(); /* * 代表当前节点 */ TreeNode current = root; /* * 最近一次弹栈的元素 */ TreeNode pop = null; List<Integer> result = new ArrayList<>(); while (!stack.isEmpty() || current != null) { if (current != null) { stack.push(current); // 待处理左子树 current = current.left; } else { TreeNode peek = stack.peek(); // 没有右子树 if (peek.right == null) { // 获取最近一次弹栈的元素 pop = stack.pop(); result.add(pop.val); } // 右子树处理完成 else if (peek.right == pop) { // 获取最近一次弹栈的元素 pop = stack.pop(); result.add(pop.val); } // 待处理右子树 else { current = peek.right; } } } return result; } }

---

本文是博主的粗浅理解，可能存在一些错误或不完善之处，如有遗漏或错误欢迎各位补充，谢谢

  如果觉得这篇文章对您有所帮助的话，请动动小手点波关注💗，你的点赞👍收藏⭐️转发🔗评论📝都是对博主最好的支持~