快速学习二叉树的基本知识：性质、遍历、和应用

创作时间:

作者:

@小白创作中心

快速学习二叉树的基本知识：性质、遍历、和应用

引用

CSDN

https://blog.csdn.net/2401_84009235/article/details/145596096

二叉树是计算机科学中一种重要的树形数据结构，广泛应用于数据存储、搜索和排序等领域。本文将从基本概念、性质、遍历方法到具体实现，系统地介绍二叉树的相关知识，并通过Python代码示例帮助读者更好地理解和掌握这一数据结构。

1. 二叉树的基本概念

二叉树是一种特殊的树，每个节点最多只能有两个子节点，分别称为左子节点（Left Child）和右子节点（Right Child）。

2. 二叉树的基本性质

假设二叉树的深度为 hh，节点数为 nn，有以下性质：

节点数上限：满二叉树最多有 2h−12^h - 1 个节点。
叶子节点数：在满二叉树中，叶子节点个数等于非叶子节点个数加 1。
完全二叉树的特点：

叶子节点只可能出现在最后两层。
如果某个节点有右子节点，一定有左子节点。

3. 二叉树的遍历

遍历是二叉树的重要操作，分为深度优先遍历（DFS）和广度优先遍历（BFS）。

（1）深度优先遍历（DFS）

DFS 包括：

前序遍历（Preorder）：根 → 左子树 → 右子树
中序遍历（Inorder）：左子树 → 根 → 右子树
后序遍历（Postorder）：左子树 → 右子树 → 根

递归实现（以 Python 为例）：

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

# 前序遍历
def preorder_traversal(root):
    if not root:
        return []
    return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)

# 中序遍历
def inorder_traversal(root):
    if not root:
        return []
    return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)

# 后序遍历
def postorder_traversal(root):
    if not root:
        return []
    return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.val]

（2）广度优先遍历（BFS）

BFS 使用队列（Queue）进行层序遍历：

from collections import deque

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

4. 二叉搜索树（BST）

（1）BST 的特点

左子树所有节点小于根节点。
右子树所有节点大于根节点。
适合查找、插入和删除操作，平均时间复杂度 O(log⁡n)O(\log n)。

（2）查找操作

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

（3）插入操作

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

（4）删除操作

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

def find_min(node):
    while node.left:
        node = node.left
    return node