一、二叉树
二叉树(binary_tree)是一种非线性数据结构,代表“祖先”与“后代”之间的派生关系,体现了“一分为二”的分治逻辑。与链表相似,二叉树的基本单元是节点,每个节点包含值、左子节点引用和右子节点引用。
1 2 3 4 5 6
| class TreeNode: """二叉树""" def __init__(self, val: int): self.val: int = val self.left: TreeNode | None = None self.right: TreeNode | None = None
|
1、二叉树常用术语
- 根节点(root node):位于二叉树顶层的节点,没有父节点。
- 叶节点(leaf node):没有子节点的节点,其两个指针均指向
None
。
- 边(edge):连接两个节点的线段,即节点引用(指针)。
- 节点所在的层(level):从顶至底递增,根节点所在层为 1 。
- 节点的度(degree):节点的子节点的数量。在二叉树中,度的取值范围是 0、1、2 。
- 二叉树的高度(height):从根节点到最远叶节点所经过的边的数量。
- 节点的深度(depth):从根节点到该节点所经过的边的数量。
- 节点的高度(height):从距离该节点最远的叶节点到该节点所经过的边的数量。
2、二叉树基本操作
初始化二叉树和插入删除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| t1 = TreeNode(1) t2 = TreeNode(2) t3 = TreeNode(3) t4 = TreeNode(4) t5 = TreeNode(5)
t1.left = t2 t1.right = t3 t2.left = t4 t2.right = t5
print(t1.left.val)
t0 = TreeNode(0) tmp = t1.left t1.left = t0 t0.left = tmp
print(t1.left.val)
|
3、 常见二叉树类型
详见
4、二叉树的退化
当二叉树的每层节点都被填满时,达到“完美二叉树”;而当所有节点都偏向一侧时,二叉树退化为“链表”。
二、二叉树遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| def level_order(root: TreeNode | None) -> list[int]: queue: deque[TreeNode] = deque() queue.append(root) res = [] while queue: node = queue.popleft() res.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return res
print(f'层序遍历: {level_order(t1)}')
res = []
def pre_order(root: TreeNode | None): if not root: return res.append(root.val) pre_order(root.left) pre_order(root.right)
pre_order(t1) print(f'前序遍历: {res}')
res = [] def mid_order(root: TreeNode | None): if not root: return mid_order(root.left) res.append(root.val) mid_order(root.right)
mid_order(t1) print(f'中序遍历: {res}')
res = [] def post_order(root: TreeNode | None): if not root: return post_order(root.left) post_order(root.right) res.append(root.val)
post_order(t1) print(f'后序遍历: {res}')
|