个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言我们继续学习《数据结构与算法》前面我们学习了栈和队列这里我们先对二叉树基本知识点进行大体的了解然后我们后续会在算法题中进行应用。本文摘要深入浅出讲解二叉树核心知识包括存储方式链式/顺序、遍历方法前序/中序/后序/层序和分类满二叉树/完全二叉树/BST等。重点解析三种深度优先遍历的特点前序根左右适合复制操作中序左根右天然有序后序左右根适用删除场景。文章对比了各类二叉树的时间复杂度推荐优先掌握普通二叉树和BST并介绍了Java中TreeMap红黑树、PriorityQueue堆等实现。通过生活化类比如文件夹操作帮助理解遍历逻辑为后续算法学习奠定基础。二叉树的存储方式二叉树可以链式存储也可以顺序存储。那么链式存储方式就用指针顺序存储的方式就是用数组。当然这个定义是针对C语言的毕竟java中并没有指针这个概念java中链式存储用的是引用来来连接节点。顾名思义就是顺序存储的元素在内存是连续分布的而链式存储则是通过指针把分布在各个地址的节点串联一起。链式存储如图链式存储是大家很熟悉的一种方式那么我们来看看如何顺序存储呢顺序存储如图其实就是用数组来存储二叉树用数组来存储二叉树如何遍历的呢如果父节点的数组下标是 i那么它的左孩子就是 i * 2 1右孩子就是 i * 2 2。但是用链式表示的二叉树更有利于我们理解所以一般我们都是用链式存储二叉树。但大家要了解用数组依然可以表示二叉树。二叉树的遍历方式关于二叉树的遍历方式要知道二叉树遍历的基本方式都有哪些。我们这里把二叉树的几种遍历方式列出来大家就可以一一串起来。二叉树主要有两种遍历方式深度优先遍历先往深走遇到叶子节点再往回走。广度优先遍历一层一层的去遍历。这两种遍历是图论中最基本的两种遍历方式后面在介绍图论的时候 还会介绍到。那么从深度优先遍历和广度优先遍历进一步拓展才有如下遍历方式深度优先遍历前序遍历递归法迭代法中序遍历递归法迭代法后序遍历递归法迭代法广度优先遍历层次遍历迭代法在深度优先遍历中有三个顺序前中后序遍历 我们有时候总分不清这三个顺序经常搞混我这里教大家一个技巧。这里前中后其实指的就是中间节点的遍历顺序只要大家记住 前中后序指的就是中间节点的位置就可以了。看如下中间节点的顺序就可以发现中间节点的顺序就是所谓的遍历方式前序遍历中左右中序遍历左中右后序遍历左右中前序遍历先记自己再找左边最后找右边你每到一个房间节点立刻在笔记本上记下这个房间的名字记录根然后先去左边所有的房间遍历左子树左边全部走完后再去右边所有的房间遍历右子树就像你去拜访一个家族进门先喊自己的名字再去找左边的亲戚最后找右边的亲戚口诀根 → 左 → 右生活例子复制文件夹你复制一个文件夹时总是先创建当前文件夹再复制里面的子文件夹这就是典型的前序思路中序遍历先找最左边再记自己最后找右边你每到一个房间先不急着记录先看看左边还有没有房间一直往左边走直到没有左边房间了记录当前节点然后再去右边房间右边房间同样重复先找最左边就像你走进一个图书馆你总是先走到最左边的那一排书架然后开始记录记录完一个就往右边移口诀左 → 根 → 右生活例子BST排序输出二叉搜索树用中序遍历出来的结果就是从小到大排好序的就像你按身高排队报数矮的先报后序遍历先找左边再找右边最后记自己你每到一个房间先把左边所有房间走完记录完再把右边所有房间走完记录完最后才记录当前房间就像你清理房间先把两个小房间都打扫干净最后才打扫中间的大客厅口诀左 → 右 → 根生活例子删除文件夹你要删除一个文件夹必须先删除里面的所有子文件夹和文件先删子节点最后删除自己这就是后序思路假设有这样一棵树text根 / \ A B / \ \ C D E手动模拟记住A的左是C和DB的右是E遍历访问顺序解释前序根 → A → C → D → B → E每到一节点立刻输出中序C → A → D → 根 → B → E一直往左到底才输出后序C → D → A → E → B → 根子节点处理完才输出父节点最后再说一说二叉树中深度优先和广度优先遍历实现方式我们做二叉树相关题目经常会使用递归的方式来实现深度优先遍历也就是实现前中后序遍历使用递归是比较方便的。之前我们讲栈与队列的时候就说过栈其实就是递归的一种实现结构也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。而广度优先遍历的实现一般使用队列来实现这也是队列先进先出的特点所决定的因为需要先进先出的结构才能一层一层的来遍历二叉树。这里其实我们又了解了栈与队列的一个应用场景了。具体的实现我们后面都会讲的这里大家先要清楚这些理论基础。二叉树的定义刚刚我们说过了二叉树有两种存储方式顺序存储和链式存储顺序存储就是用数组来存这个定义没啥可说的我们来看看链式存储的二叉树节点的定义方式。C代码如下struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };java代码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; } }大家会发现二叉树的定义 和链表是差不多的相对于链表 二叉树的节点里多了一个指针 有两个指针指向左右孩子。这里要提醒大家要注意二叉树节点定义的书写方式。在现场面试的时候 面试官可能要求手写代码所以数据结构的定义以及简单逻辑的代码一定要锻炼白纸写出来。因为我们在刷leetcode的时候节点的定义默认都定义好了真到面试的时候可能需要自己写节点定义二叉树的分类按逻辑结构分类种类特点典型应用满二叉树每个节点要么是叶子要么有两个子节点所有叶子在同一层堆排序的完全二叉树特例完全二叉树除最后一层外全满最后一层节点左对齐二叉堆、优先队列平衡二叉树任意节点左右子树高度差 ≤ 1AVL树、红黑树二叉搜索树(BST)左子树 根 右子树快速查找、插入、删除斜树所有节点只有左孩子左斜树或只有右孩子右斜树退化成了链表最坏情况按平衡机制分类Java中常用的自平衡树1. AVL树特点严格平衡高度差 ≤ 1优点查询极快缺点插入/删除需要频繁旋转Java中没有直接实现但可以自己写2. 红黑树特点近似平衡通过颜色标记和旋转维持平衡优点插入/删除比AVL快查询也很快Java中的实现TreeMap底层是红黑树TreeSet底层是红黑树HashMap的链表转红黑树当链表长度 ≥ 8 时java // TreeMap 底层是红黑树 TreeMapInteger, String map new TreeMap(); // TreeSet 底层也是红黑树 TreeSetInteger set new TreeSet();按实现方式分类Java集合框架中的树种类Java实现类底层结构特点红黑树TreeMap、TreeSet红黑树有序不允许null键TreeMap二叉堆PriorityQueue完全二叉树数组实现优先级队列堆顶最值字典树无标准库需自己实现多叉树变种高效字符串前缀匹配特殊用途的二叉树1.二叉堆PriorityQueue底层逻辑上完全二叉树物理上用数组存储性质父节点 ≥ 子节点大顶堆或 ≤ 子节点小顶堆java // Java中的优先队列小顶堆 PriorityQueueInteger minHeap new PriorityQueue(); // 大顶堆 PriorityQueueInteger maxHeap new PriorityQueue((a, b) - b - a);2.线段树特点每个节点代表一个区间应用区间求和、区间最值、区间修改Java中无现成实现需手写3.字典树Trie特点字符串树共享公共前缀应用自动补全、词频统计、敏感词过滤Java中无标准实现需手写4.二叉线索树特点利用空指针指向遍历前驱/后继优点节省空间便于遍历Java中很少直接用但Morris遍历用了这个思想需要重点掌握的学习优先级种类理由夯普通二叉树刷题基础所有树的基础夯二叉搜索树(BST)算法题高频理解查找/插入/删除人上人完全二叉树堆的基础PriorityQueue原理顶级平衡二叉树理解TreeMap/TreeSet原理夯红黑树面试常问但不需要手写拉完了线段树/Trie特定场景使用总结对比种类有序性平衡性查询复杂度Java中的代表普通二叉树无不一定O(n)自己定义TreeNode二叉搜索树有不一定O(n)最坏无标准实现AVL树有严格O(log n)需手写红黑树有近似O(log n)TreeMap/TreeSet二叉堆部分只有最值完全O(1)取最值PriorityQueue一句话记忆刷题用普通二叉树和BST理解有序用TreeMap实现优先级队列用PriorityQueue完全二叉树面试问平衡就答红黑树。目前刷题阶段重点关注普通二叉树和二叉搜索树即可红黑树先理解概念不需要手写实现。结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励