二叉树

二叉树（Binary Tree）是计算机科学中最基础且重要的数据结构之一，广泛应用于算法设计、数据库索引、文件系统等领域。它是一种每个节点最多有两个子节点的树形结构，这两个子节点通常被称为左子节点和右子节点。

基本概念[编辑 | 编辑源代码]

定义[编辑 | 编辑源代码]

二叉树是满足以下条件的树：

每个节点最多有两个子节点（左子节点和右子节点）。
子节点有明确的左右顺序之分（即使只有一个子节点，也必须指明是左还是右）。

数学上可以递归定义为： $T = {\begin{cases} \emptyset & 空树 \\ (r, T_{L}, T_{R}) & 根节点为 r ，左子树为 T_{L} ，右子树为 T_{R} \end{cases}$

术语[编辑 | 编辑源代码]

根节点（Root）：没有父节点的顶层节点
叶节点（Leaf）：没有子节点的节点
内部节点：至少有一个子节点的非根节点
深度：从根到该节点的唯一路径的边数
高度：从该节点到最深叶节点的最长路径的边数

二叉树类型[编辑 | 编辑源代码]

满二叉树[编辑 | 编辑源代码]

每一层的节点都达到最大数量，即第 $i$ 层有 $2^{i - 1}$ 个节点。

完全二叉树[编辑 | 编辑源代码]

除最后一层外，其他层节点都满，且最后一层节点从左向右连续排列。

二叉搜索树（BST）[编辑 | 编辑源代码]

对于任意节点：

左子树所有节点的值 < 当前节点的值
右子树所有节点的值 > 当前节点的值

基本操作[编辑 | 编辑源代码]

遍历方式[编辑 | 编辑源代码]

二叉树有四种基本遍历方式（以下示例代码使用Python实现）：

前序遍历[编辑 | 编辑源代码]

def preorder(root):
    if root:
        print(root.val)      # 访问根节点
        preorder(root.left)   # 遍历左子树
        preorder(root.right)  # 遍历右子树

中序遍历[编辑 | 编辑源代码]

def inorder(root):
    if root:
        inorder(root.left)    # 遍历左子树
        print(root.val)      # 访问根节点
        inorder(root.right)   # 遍历右子树

后序遍历[编辑 | 编辑源代码]

def postorder(root):
    if root:
        postorder(root.left)  # 遍历左子树
        postorder(root.right) # 遍历右子树
        print(root.val)      # 访问根节点

层序遍历[编辑 | 编辑源代码]

from collections import deque

def level_order(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

插入与删除[编辑 | 编辑源代码]

以二叉搜索树为例：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def delete(root, val):
    if not root:
        return None
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # 找到右子树的最小节点
        temp = root.right
        while temp.left:
            temp = temp.left
        root.val = temp.val
        root.right = delete(root.right, temp.val)
    return root