数据结构与算法-知识点(第五章树与二叉树)

张沉 4/11/2025 13003

好的！我将根据你提供的知识点大纲，结合知识库内容，为你详细梳理各个部分的核心概念、理解方法和应用技巧。以下是分章节的详细讲解：

# 1. 树的基本概念

# 识记知识点

树（Tree）
- 定义：树是n（n≥0）个节点的有限集合，当n>0时，有且仅有一个根节点（Root），其余节点分为若干互不相交的子树（Subtree）。
- 递归定义：树由根节点和若干子树构成，子树本身也是树。空树（n=0）是合法的。
子树（Subtree）
- 根的子树是树的一部分，子树之间互不相交。
结点（Node）
- 包含数据元素和指向子树的分支。
- 边（Edge）：连接父子节点的连线。
根结点（Root Node）
- 树的唯一顶级节点，没有父节点。
父结点（Parent Node）
- 某个节点的直接上级节点。
兄弟结点（Sibling Nodes）
- 同一父节点的子节点。
祖先结点（Ancestor Node）
- 从根到该节点路径上的所有节点。
后代结点（Descendant Node）
- 以该节点为根的子树中的所有节点。
子结点（Child Node）
- 某个节点的直接下级节点。
层（Level）
- 根节点为第1层，其子节点为第2层，依此类推。
深度（Depth）/高度（Height）
- 深度：节点所在的层号。
- 高度：树中最大层数（根的高度为1）。
结点的度（Degree of a Node）
- 节点拥有的子树数目。
树的度（Degree of a Tree）
- 树中所有节点的度的最大值。
路径（Path）
- 从一个节点到另一个节点的边的序列。
路径长度（Path Length）
- 路径上边的数目。
叶结点（Leaf Node）
- 度为0的节点，无子节点。
分支结点（Internal Node）
- 度不为0的节点，非根节点的分支结点称为内部节点。
有序树（Ordered Tree）
- 子树的顺序有意义，如二叉树。
森林（Forest）
- m（m≥0）棵互不相交的树的集合。

# 领会知识点

层次结构的含义
树的层次结构通过父-子关系形成层级，每个节点有唯一的路径到根。
- 前驱（Predecessor）：父节点或祖先节点。
- 后继（Successor）：子节点或后代节点。
树的递归定义
树的定义基于自身结构：树由根节点和子树构成，子树也是树。
树的表示形式
- 图形表示：用节点和边绘制树。
- 父指针表示：每个节点记录父节点的指针。
- 孩子链表表示：每个节点保存子节点的链表。
节点个数与边数的关系
树的边数 = 节点数 - 1（根节点没有父节点，其他节点均有唯一父节点）。

# 简单应用

树的表示方式示例

父指针表示法：
每个节点存储父节点的索引，如：

nodes = [  
    {"parent": -1, "data": "A"},  # 根节点  
    {"parent": 0, "data": "B"},  
    {"parent": 0, "data": "C"}  
]

孩子链表表示法：
每个节点保存子节点的列表，如：

nodes = {  
    "A": ["B", "C"],  
    "B": [],  
    "C": []  
}

# 2. 二叉树及其操作

# 识记知识点

二叉树（Binary Tree）
- 每个节点最多有两个子树：左子树（Left Subtree）和右子树（Right Subtree）。
- 左子结点（Left Child）和右子结点（Right Child）有明确区分。
满二叉树（Full Binary Tree）
- 所有层的节点数达到最大值，即第i层有(2^{i-1})个节点。
完全二叉树（Complete Binary Tree）
- 除最后一层外，其他层节点数均满，且最后一层节点从左到右连续填充。
二叉链表（Binary Linked List）
- 每个节点包含左指针（Left Pointer）和右指针（Right Pointer）。
二叉树的遍历
- 前序遍历（Preorder）：根→左→右。
- 中序遍历（Inorder）：左→根→右。
- 后序遍历（Postorder）：左→右→根。
- 层序遍历（Level Order）：按层次从上到下、从左到右访问。

# 领会知识点

二叉树的递归定义
二叉树是空树，或由根节点、左子树和右子树构成。
二叉树的性质
1. 第i层最多有(2^{i-1})个节点。
2. 深度为h的二叉树最多有(2^h - 1)个节点。
3. 对于完全二叉树，若节点数为n，则根节点的索引为1，左子节点为(2i)，右子节点为(2i+1)。
存储方式
- 顺序存储：用数组表示，完全二叉树的节点按层序排列。
  - 父节点i的左子节点为(2i)，右子节点为(2i+1)。
- 链式存储：每个节点包含数据、左指针和右指针。

# 简单应用

递归实现前序遍历

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

非递归实现中序遍历

def inorder(root):
    stack = []
    current = root
    while True:
        if current is not None:
            stack.append(current)
            current = current.left
        elif stack:
            current = stack.pop()
            print(current.data)
            current = current.right
        else:
            break

# 3. 堆及优先队列

# 识记知识点

堆（Heap）
- 堆是完全二叉树，满足堆性质：
  - 最大堆（Max-Heap）：父节点的值 ≥ 子节点的值。
  - 最小堆（Min-Heap）：父节点的值 ≤ 子节点的值。
堆顶（Heap Top）
- 根节点，是最大堆或最小堆的极值点。
优先队列（Priority Queue）
- 堆的典型应用，支持快速插入和删除最大/最小元素。

# 领会知识点

堆的存储
- 用数组存储，父节点i的左子节点为(2i)，右子节点为(2i+1)。
堆的有序性
- 满足堆性质的父子节点关系。
堆的建立过程
1. 上滤（Bubble Up）：插入新节点后，不断与父节点比较，必要时交换位置。
2. 下滤（Trickle Down）：删除堆顶后，将最后一个节点移到根，并向下调整。

# 简单应用

最大堆的插入操作

def heap_insert(heap, value):
    heap.append(value)
    i = len(heap) - 1
    while i > 0:
        parent = (i - 1) // 2
        if heap[parent] < heap[i]:
            heap[parent], heap[i] = heap[i], heap[parent]
            i = parent
        else:
            break

删除堆顶（最大堆）

def heap_remove_top(heap):
    if not heap:
        return None
    # 交换堆顶和最后一个元素
    heap[0], heap[-1] = heap[-1], heap[0]
    removed = heap.pop()
    # 下滤操作
    i = 0
    while True:
        left = 2*i + 1
        right = 2*i + 2
        largest = i
        if left < len(heap) and heap[left] > heap[largest]:
            largest = left
        if right < len(heap) and heap[right] > heap[largest]:
            largest = right
        if largest != i:
            heap[i], heap[largest] = heap[largest], heap[i]
            i = largest
        else:
            break
    return removed

# 4. 树和森林

# 识记知识点

树的表示方法
- 父节点表示法：用数组记录每个节点的父节点。
- 孩子表示法：用链表记录每个节点的子节点。
- 孩子-兄弟表示法（Child-Sibling）：每个节点有指向第一个子节点和下一个兄弟节点的指针。
森林（Forest）
- 多棵树的集合，可转换为二叉树。

# 领会知识点

树与二叉树的转换
- 树转二叉树：
  1. 将树的兄弟节点链为右子树。
  2. 每个节点的第一个子节点为左子树。
- 森林转二叉树：
  1. 将森林中的每棵树转换为二叉树。
  2. 以第一棵树的根为二叉树的根，其他树的根作为第一棵树的根的右子树。
遍历关系
- 树的先序遍历对应二叉树的前序遍历。
- 树的后序遍历对应二叉树的后序遍历。

# 简单应用

树转二叉树示例
原树结构：

    A  
  / | \  
 B  C  D

转换为二叉树：

# 5. 哈夫曼树及哈夫曼编码

# 识记知识点

哈夫曼树（Huffman Tree）
- 带权路径长度（WPL）最小的二叉树，用于构造最优前缀编码。
前缀特性（Prefix Property）
- 任意一个编码都不是另一个编码的前缀，确保解码唯一性。
叶结点的带权路径长度（WPL）
- (WPL = \sum (权重 \times 路径长度))，目标是使WPL最小。

# 领会知识点

哈夫曼编码的构造步骤
1. 将所有节点作为初始森林。
2. 选取权重最小的两棵树合并为新树，新树的根权重为两子树之和。
3. 重复步骤2，直到只剩一棵树。
编码与译码
- 左子树编码为0，右子树编码为1。
- 译码时从根开始，根据编码路径找到叶节点。

# 简单应用

构造哈夫曼树示例
权重：A(5), B(9), C(12), D(20)
步骤：
1. 合并A(5)和B(9)为新树（权重14）。
2. 合并新树（14）和C(12)为新树（26）。
3. 合并新树（26）和D(20)为最终树（46）。
  编码：
- A: 00
- B: 01
- C: 10
- D: 1
计算WPL
(WPL = 5 \times 2 + 9 \times 2 + 12 \times 2 + 20 \times 1 = 10 + 18 + 24 + 20 = 72)。

# 综合应用技巧

树与二叉树的转换
- 通过孩子-兄弟表示法实现树到二叉树的转换，便于遍历和操作。
优先队列的实现
- 使用堆结构实现O(log n)时间复杂度的插入和删除操作。
哈夫曼编码的应用
- 用于数据压缩（如ZIP文件），通过变长编码减少存储空间。

记沉

Choose mode

数据结构与算法-知识点(第五章树与二叉树)

数据结构与算法-知识点(第五章树与二叉树)

# 1. 树的基本概念

# 识记知识点

# 领会知识点

# 简单应用

# 2. 二叉树及其操作

# 识记知识点

# 领会知识点

# 简单应用

# 3. 堆及优先队列

# 识记知识点

# 领会知识点

# 简单应用

# 4. 树和森林

# 识记知识点

# 领会知识点

# 简单应用

# 5. 哈夫曼树及哈夫曼编码

# 识记知识点

# 领会知识点

# 简单应用

# 综合应用技巧