Hello算法7：二叉树
https://www.hello-algo.com/chapter_tree/binary_tree/
基本介绍
二叉树是一种非线性数据结构，代表祖先和后辈的关系，体现了分治思想。
二叉树的基本单元节点，包含值，左节点和右节点的引用
class TreeNode:"""二叉树节点类"""def __init__(self, val: int):self.val: int = val # 节点值self.left: Optional[TreeNode] = None # 左子节点引用self.right: Optional[TreeNode] = None # 右子节点引用
常见定义
- 根节点-root node-位于顶部的节点，没有父节点
- 叶节点-leaf node-位于底部的节点，没有子节点
- 边-dege-连接两个节点的线段，也就是指针
- 节点所在的层-level-，根节点的层是1，从顶至底递增
- 节点的度-degree-节点的子节点的数量。有0,1,2个子节点
- 二叉树的高度：从根节点到最远叶节点所经过的边的数量
- 节点的深度：从根节点到该节点，所经过的边的数量
- 节点的高度：从最远叶节点到该节点，所经过的边的数量
初始化二叉树
# 初始化二叉树
# 初始化节点
n1 = TreeNode(val=1)
n2 = TreeNode(val=2)
n3 = TreeNode(val=3)
n4 = TreeNode(val=4)
n5 = TreeNode(val=5)
# 构建引用，即指针
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
插入或删除节点
# 插入与删除节点
p = TreeNode(0)
# 在 n1 -> n2 中间插入节点 P
n1.left = p
p.left = n2
# 删除节点 P
n1.left = n2
常见二叉树
-
完美二叉树 perfect
所有节点的度都是2，也就是所有节点都有2个子节点的二叉树。完美反映细胞分裂。
-
完全二叉树 complet
只有最底层节点未填满，且节点靠左填充
-
完满二叉树 full
除了叶节点之外，所有节点都有2个子节点
-
平衡二叉树 balanced
任意节点的左子树和右子树的高度差，绝对值不超过1
层序遍历
从顶部到底部，逐层，从左到右进行遍历
# 层序遍历
def level_order(root: TreeNode | None) -> list[int]:queue = 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
前序遍历
def pre_order(root: TreeNode | None):if root is None:returnres.append(root.val)pre_order(root=root.left)pre_order(root=root.right)
二叉树数组表示
先分析一种简单的情况，完美二叉树，左节点是2i+1，右节点是2i+2，这时候可以很方便的用数组表示；
再扩展到任意二叉树，用none表示和填充数组即可；
完全二叉树，none只在最底层并且靠右，很适合用数组表示；
代码如下：
略
数组表示的优点：
- 数组存储在连续的内存空间，对缓存友好
- 不需要指针，节省空间
- 允许随机访问节点
数组表示的缺点：
由于需要连续内存空间，不适合存储过大的树
增删节点需要通过数组的插入和删除来实现，效率较低
当二叉树中存在大量None时，空间利用率较低
二叉搜索树
定义：
- 对于根节点，左子树中所有节点的值<根节点的值<右子树中所有节点的值
- 任意子树，同样满足上一个条件
搜索操作：
def search(self, num: int) -> TreeNode | None:"""查找节点"""cur = self._root# 循环查找，越过叶节点后跳出while cur is not None:# 目标节点在 cur 的右子树中if cur.val < num:cur = cur.right# 目标节点在 cur 的左子树中elif cur.val > num:cur = cur.left# 找到目标节点，跳出循环else:breakreturn cur
插入操作：
为了保证插入元素后依然满足二叉搜索树的性质，插入步骤如下
- 查找插入位置，类似于搜索操作
- 在该位置插入节点
def insert(self, num: int):"""插入节点"""# 若树为空，则初始化根节点,也就是直接插在根节点if self._root is None:self._root = TreeNode(num)return# 循环插找cur, pre = self._root, Nonewhile cur is not None:# 找到重复值，直接returnif cur.val == num:returnpre = curif cur.val < num:cur = cur.rightelse:cur = cur.left# 插入节点node = TreeNode(num)if pre.val < num:pre.right = nodeelse:pre.left = node
删除操作：
查找到要删除的节点后，删除分为三种情况
是叶节点，直接删除即可
有1个子节点，用子节点替换该节点
