树与堆¶
binary tree¶
从物理结构来看,树是一种基于链表的数据结构。当然也可以用数组表示,将所有节点按照层序遍历的顺序存储在一个数组中,则每个节点都对应唯一的数组索引。
class TreeNode:
"""二叉树节点类"""
def __init__(self, val: int):
self.val: int = val # 节点值
self.left: TreeNode | None = None # 左子节点引用
self.right: TreeNode | None = None # 右子节点引用
# 初始化二叉树
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
通常将高度和深度定义为经过的边的数量,但有些题目或教材可能会将其定义为经过的节点的数量。在这种情况下,高度和深度都需要加 1。
与链表类似,在二叉树中插入与删除节点可以通过修改指针来实现。插入节点可能会改变二叉树的原有逻辑结构,而删除节点通常意味着删除该节点及其所有子树。
二叉树分类¶
- 完美二叉树:所有层的节点都被完全填满,也称作满二叉树,除叶节点外其余节点的度都是2,节点总数为 \(2^{h+1} - 1\)
- 完全二叉树:除最底层外,其它层节点都被填满,且最底层节点尽量靠左填充
- 完满二叉树:除了叶节点外,其余节点都有两个子节点
- 平衡二叉树:任意节点左右子树的高度之差不超过 1
二叉树的最佳结构是完美二叉树,最差结构则是所有节点都偏向一侧,即退化为了链表
二叉树遍历¶
遍历方式是通过指针逐个访问节点,但由于非线性,遍历树要更复杂,需要借助搜索算法。
- 广度优先遍历:层序遍历
- 深度优先遍历:前序、中序、后序遍历
binary search tree¶
二叉搜索树(BST)任意节点 左子树各节点的值 < 节点值 < 右子树各节点的值
,通常用作系统中的多级索引
自平衡,意味着树会通过算法(旋转、分裂、合并)在每次插入或删除节点之后自动调整,以保持树的平衡,从而确保树的高度保持在平衡因子(-1、0、1)范围内。
- AVL树,自平衡二叉搜索树,任何节点的两个子树的高度差最多为1
- 红黑树,自平衡二叉搜索树,从根到叶子的最长路径不会超过最短路径的两倍
- B树,自平衡多路搜索树,所有的叶子节点都在同一层
heap¶
堆,是一种满足特定条件的完全二叉树,根节点称为堆顶,将底层最靠右的节点称为堆底
完全二叉树非常适合用数组来表示,所以通常采用数组来存储堆。