二叉树的基本概念
二叉树是一种非线性的数据结构，由每个节点一分为二引出两个子节点（类似高中生物学到的祖先后代的结构图，但二叉树是一个节点只能有两个子节点）。
基本单元：结点。每个节点包含值和两个引用（也就是指针）分别指向左子节点和右子节点。该节点是这两个节点的父节点，称这个节点的左子节点及其后续的分支为左子树，同理还有右子树
常见术语：
- 根节点：二叉树顶层的节点，没有父节点
- 叶节点：二叉树底层的节点，没有子树，叶节点的两个指针均为None
- 边：连接两个结点的线段，也就是指针
- 节点所在层：从顶部开始数，顶层为第一层
- 节点的度：子节点的数量，可取0，1，2
- 节点的深度：根节点到该节点需要经历的边数（从上往下数）
- 节点的高度：距离该点最远的叶节点到该节点所经历的边的数量
- 二叉树的高度：从根节点到最远的叶节点所经历的边数
二叉树的基本操作
- 初始化二叉树（基于链式储存的二叉树）
# 定义二叉树类ClassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=val self.left=left self.right=right# 初始化n1=TreeNode(1)n2=TreeNode(2)n3=TreeNode(3)n4=TreeNode(4)# 构建节点之间的关系n1.left=n2 n1.right=n3 n2.left=n4# 访问某个节点的值，左子节点和右子节点n1.val n1.left n1.right- 插入和删除节点
类似于链表插入、删除节点的方法，只需要修改指针(left, right)
p=TreeNode(1)# 在n1,n2之间插入pn1.left=p p.left=n2# 删除节点p,即由p的父节点到子节点跳过pn1.left=n2常见二叉树的类型
完美二叉树/满二叉树（常见）
所有的节点都有两个子节点，除了叶节点。完全二叉树（常见）
仅允许最底层的节点不完全填满，且最底层的节点必须从左至右依次连续填充完满二叉树
除了叶叶节点外，其余所有节点都有两个子节点平衡二叉树
任意节点的左右子树的高度之差的绝对值不超过1二叉搜索树（后续有详细内容）
- 若左子树不空，则左子树上每个子节点的值都小于根节点的值
- 若右子树不空，则右子树上每个子节点的值都大于根节点的值
左右子树均为二叉搜索树
可以记作：
左子树中所有节点的值 <根节点的值 <右子树中所有节点的值
- 平衡二叉搜索树
- 是空树或者满足左右两个子树的高度差不超过1
- 并且两个子树分别也是平衡二叉树
二叉树的储存方式
链式储存
链表的储存方式：每个节点的地址是不连续的，通过左右指针索引
顺序储存
数组的储存方式（用数组储存二叉树）
二叉树的退化
二叉树最“满”的结构就是完美二叉树，而它的退化结构，每个节点只有一个子节点时，就变成链表。
- 完美二叉树可以充分发挥二叉树分治的优势
- 链表则是另一个极端，各项操作都变成线性操作，时间复杂度为O(n)
二叉树的遍历
背景：二叉树本质上是通过指针遍历逐个访问每个元素。但由于二叉树是非线性的数据结构，它的遍历顺序不是只有一条路线（更复杂），所以需要人为设计，主要有以下几个方法。
层序遍历
从顶部到底部按层遍历二叉树，并在每层按从左到右的顺序访问节点，也称广度优先遍历/广度优先搜索。
代码实现
def level_order(root:TreeNode|None) -> list[int]: # 通过一个队列储存层序遍历树的结果 queue: deque[TreeNode] = deque() queue.append(root) res = [] while queue: node: TreeNode = queue.popleft() res.append(node.val) if node.left is not None: queue.append(node.left) if node.right is not None: queue.append(node.right) return res前序、中序、后序遍历
都属于深度优先遍历，通常通过递归实现。这里前中后，其实指的是每个小叉里中间节点（root）的遍历顺序。
前序：root, root.left, root.right
中序：root.left, root, root.right
后序：root.left, root.right, root
def pre_order(root:TreeNode | None): if root is None: return res.append(root.val) pre_order(root=root.left) pre_order(root=root.right) def mid_order(root: TreeNode | None): if root is None: return mid_order(root=root.left) res.append(root.val) mid_order(root=root.right) def pot_order(root:TreeNode | None): if root is None: return pot_order(root = root.left) pot_order(root = root.right) res.append(root.val)三者递归的区别和特点：依靠root is None找到向上递归点，关键在于递归到左右子节点X_order(root=root.left), X_order(root=root.right)和赋值res.append(root.val)的顺序
复杂度
层序遍历和深度优先遍历的时间，空间复杂度均为O(n)
二叉树的数组表示
数组表示完美二叉树
将所有节点按照层序遍历的顺序存储在一个数组，每个父节点和左右两个子节点之间的索引存在固定的公式：父节点的索引是i，则其左子节点索引为2i+1，右子节点索引为2i+2
数组表示任意二叉树
还是同样的索引方式，但是对于二叉树中某些位置是None的情况，显式写出来(占位)，为了不破坏2i+1,2i+2的映射关系。
数组表示比较适合完全二叉树，None的位置都在数组末尾
数组表示的优势
- 连续储存，对缓存友好，访问和遍历速度快
- 允许随机访问节点，不必按树的指针顺序
- 不需要储存指针，节省空间
数组表示的劣势
- 增删节点效率低
- 不适用于二叉树有大量位置是None的情况，空间利用率低
- 数组储存需要连续内存空间，所以不适合储存数据量很大的二叉树
二叉搜索树 （BTS）
左子树中所有节点的值 <根节点的值 <右子树中所有节点的值
二叉搜索树的操作
- 查找节点
- 通过二分法，设目标节点值为num
如果当前节点cur.val<num，则num在cur的右子树，则cur=cur.right
若cur.val>num，则num在cur的左子树，cur=cur.left - 复杂度：O(logn)
- 插入节点
给定一个二叉搜索树，根据“左子树 < 根节点 < 右子树”的性质找到插入位置。
注意二叉搜索树要求不能有值重复的节点，否则将违反其定义。所以如果插入节点的值在树中已存在，那就不会插入，直接返回。
- 复杂度：O(logn)
def insert(self, num): if self._root is None: self._root = TreeNode(num) return cur, pre = self._root, None while cur is not None: if cur.val == num: return pre = cur if cur.val < num: cur = cur.right else: cur = cur.left if pre.val <num: pre.right = TreeNode(num) else: pre.left = TreeNode(num)- 删除节点
- 若节点为叶节点，则可以直接删除
- 若节点的度为1（有一个子节点），则删除它后，直接用其子节点（左或右）替换它的位置
- 若节点的度为2（有两个子节点，这里也包括大于等于2的情况），则需要用其右子树的最小节点或其左子树的最大节点进行替换，两种都可以
def remove(self, num: int): """删除节点""" # 若树为空，直接提前返回 if self._root is None: return # 循环查找，越过叶节点后跳出 cur, pre = self._root, None while cur is not None: # 找到待删除节点，跳出循环 if cur.val == num: break pre = cur # 待删除节点在 cur 的右子树中 if cur.val < num: cur = cur.right # 待删除节点在 cur 的左子树中 else: cur = cur.left # 若无待删除节点，则直接返回 if cur is None: return # 子节点数量 = 0 or 1 if cur.left is None or cur.right is None: # 当子节点数量 = 0 / 1 时， child = null / 该子节点 child = cur.left or cur.right # 删除节点 cur if cur != self._root: if pre.left == cur: pre.left = child else: pre.right = child else: # 若删除节点为根节点，则重新指定根节点 self._root = child # 子节点数量 = 2，这里是用右子树的最小节点，也可以改成左子树的最大节点 else: # 获取中序遍历中 cur 的下一个节点 tmp: TreeNode = cur.right while tmp.left is not None: tmp = tmp.left # 递归删除节点 tmp self.remove(tmp.val) # 用 tmp 覆盖 cur cur.val = tmp.val- 二叉搜索树的中序遍历有序
由于二叉树的大小关系，其在中序遍历时有一个性质二叉搜索树的中序遍历序列是升序的，因此获取有序数据仅需O(n)的时间，非常高效。
二叉搜索树的效率
无序数组：插入
时直接添加到末尾，O(1)，删除和查找时候需要先找到待删除和查找的位置，所以是O(n)
二叉搜索树由于有大小关系，所以具有O(logn)的复杂度
二叉搜索树的常见应用
用作系统中的多级索引，实现高效的查找、插入、删除操作。
作为某些搜索算法的底层数据结构。
用于存储数据流，以保持其有序状态。
AVL树
background：搜索二叉树经过多次插入和删除操作后会退化为链表（高度不断增加，每层节点数却减少），导致复杂度会增加至O(n)
提出AVL二叉树，通过一系列操作确保其在持续添加、删除节点后不会退化，仍保持O(logn)的复杂度。既是二叉搜索树，也是平衡二叉树（平衡二叉树：任意节点的左右子树的高度之差的绝对值不超过1）。在需要频繁增删查改的操作场景中，能始终保持高效的数据操作。
