树与二叉树

1. 树的定义和基本术语

很经典的一个树这种数据结构的应用就是Windows文件系统的文件目录

树结构：每个节点是一对多的关系，b和c不满足一对多的性质，b中F对接了B和C，c中B和E也是不满足该性质

1.1 树的概念

• 树：由n个节点组成的有限集合，其中n≥0。当n=0时，称为空树。
  • 非空树有一个特定的节点称为根。
  • 除根外的其余节点被分成m个互不相交的有限集合T1, T2, ..., Tm，每个集合本身是一棵树，称为根的子树。

1.2 树的基本术语

• 节点的度：节点拥有的子树个数。
• 树的度：树中各节点度的最大值。

• 叶子节点：度为0的节点。
• 分支节点：度不为0的节点，也称为非终端节点或中间节点。
• 孩子节点：一个节点的直接后继。
• 双亲：一个节点的直接前驱。
• 兄弟：具有同一个双亲的节点互称为兄弟。
• 路径：若节点序列n1, n2, ..., nk满足ni是ni+1的双亲，则称n1, n2, ..., nk为路径，路径长度为k-1。

• 祖先和子孙：如果存在一条路径从节点x到节点y，则x是y的祖先，y是x的子孙。
• 节点所在层数：根节点的层数为1，其余节点若在某层k，则其孩子在k+1层。
• 树的深度：树中所有节点的最大层数。

以文件系统的一个路径为例‘C:\Program Files (x86)\Tencent’，假设Tencent下没有文件了

C盘代表根节点（第一层）；Program Files (x86)代表子节点（第二层）；Tencent则代表叶子结点（第三层）。所以这棵树的深度为3

层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们 编以从1开始的连续自然数。

1.3 树的分类

• 有序树：子树从左到右有次序的树。

• 无序树：子树从左到右无次序的树。

• 森林：n个互不相交的树的集合。

把树的根结点删去就成了森林；

给n棵独立的树加上一个结点，并把这n棵树作为该结点的子树， 则森林就变成了一颗树。

1.4 树的表示方法

• 直观表示（图示）

• 凹入表示法

凹入表示法主要用于树的屏幕或打印输出，其基本思想是兄弟间等长，一个节点要不小于其子节点的长度。对于非叶子节点，其长度等于其左右子树的长度之和。这种表示法通过缩进来表示节点的层级关系，使得树的结构更加直观。

• 文氏图表示法

文氏图表示法使用集合以及集合包含关系描述树结构。在这种表示法中，每个节点被表示为一个圆圈，而节点的子节点则被包含在圆圈内的另一个圆圈中。这种表示法强调了节点之间的包含关系，适合于表达层次结构。

• 广义表表示法

广义表表示法使用递归的方式表示树，其中每个节点可以是一个原子或者是另一个广义表。广义表通常以(值, 子表1, 子表2, ...)的形式表示，非常适合于完全二叉树的表示。

1.5 构建一颗普通树的伪代码(python)

# 树的节点定义
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

# 创建树的根节点
root = TreeNode('A')

# 添加子节点
root.children.append(TreeNode('B'))
root.children.append(TreeNode('C'))

# 遍历树（以某种方式，例如前序遍历）
def traverse(node):
    if node is not None:
        print(node.value)  # 访问节点
        for child in node.children:
            traverse(child)

traverse(root)  # 输出: A B C

1. 二叉树

二叉树的五种形态

2.1 二叉树的定义

• 二叉树：由n个节点组成的有限集合，其中n≥0。当n=0时，称为空二叉树。
  • 当n>0时，由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。

二叉树并不是度小于等于2的有序树：

1. 二叉树：是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常被称为左孩子和右孩子。二叉树的特点是每个节点的子节点数量不超过2个。
2. 有序树：是一种树形结构，其中节点的子树之间存在某种特定的顺序关系。在有序树中，子树的顺序是固定的，例如，左子树的所有节点在某种意义上都“小于”其父节点，而右子树的所有节点都“大于”其父节点。
3. 度小于等于2的树：指的是树中每个节点的子节点数量不超过2个。这可以是二叉树，也可以是其他类型的树，只要满足每个节点的子节点数量不超过2个即可。
4. 二叉树与有序树的关系：二叉树可以是有序树的一种，但并非所有二叉树都是有序树。有序树的概念更广泛，可以包含二叉树，也可以包含其他类型的有序树。例如，二叉搜索树是一种有序树，它同时也是二叉树，其中左子树上的所有节点的值都小于根节点的值，右子树上的所有节点的值都大于根节点的值。

也就是对于A->B，既可以说是两棵不同的二叉树，也可以说是只表示一棵度为1的有序树

2.2 二叉树的性质

• 性质1：对任意一棵二叉树，如果叶子节点（度为0）个数为𝑛0 ，度为2的节点个数为𝑛2 ，则有𝑛0=𝑛2+1。

• 性质2：在一棵非空二叉树的第i层上至多有2𝑖−1个节点（i≥1）。
• 性质3：深度为k的二叉树至多有2𝑘−1个节点(k≥1)。
• 满二叉树：深度为k的且有2𝑘−1个节点的二叉树。所有分支节点都存在左子树和右子树，并且所有叶子节点都在同一层上。

• 完全二叉树：如果一棵深度为k，有n个节点的二叉树中各节点能够与深度为k的顺序编号的满二叉树从1到n标号的节点相对应的二叉树称为完全二叉树。

2.3 二叉树的存储结构

• 顺序存储结构：把完全二叉树的节点按从上至下和从左至右的次序存储在一维数组中。
• 仿真指针的孩子表示法存储结构：使用结构体存储节点的数据和左右孩子的索引。
• 仿真指针的孩子双亲表示法存储结构：在孩子表示法的基础上增加一个字段存储父节点的索引。
• 链式存储结构：通过指针记录节点的左右孩子节点的位置（内存地址）。

2.4构建一颗二叉树的伪代码

# 定义二叉树节点
class BinaryTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 创建二叉树的根节点
root = BinaryTreeNode('A')
root.left = BinaryTreeNode('B')
root.right = BinaryTreeNode('C')
root.left.left = BinaryTreeNode('D')
root.left.right = BinaryTreeNode('E')

# 前序遍历
def pre_order_traversal(node):
    if node is not None:
        print(node.value)  # 访问根节点
        pre_order_traversal(node.left)  # 遍历左子树
        pre_order_traversal(node.right)  # 遍历右子树

pre_order_traversal(root)  # 输出: A B D E C

3. 遍历二叉树

3.1 二叉树遍历的定义

二叉树遍历是指按照一定次序访问树中所有节点，并且每个节点仅被访问一次的过程。遍历是二叉树最基本的运算，是二叉树中其他运算的基础。

3.2 遍历方式

• 前序遍历（根左右）：先访问根节点，然后遍历左子树，最后遍历右子树。
• 中序遍历（左根右）：先遍历左子树，然后访问根节点，最后遍历右子树。
• 后序遍历（左右根）：先遍历左子树，然后遍历右子树，最后访问根节点。
• 层序遍历：从上到下，同一层从左到右依次访问，实际上是用队列实现的广度优先遍历。

3.3 遍历树的伪代码

# 定义二叉树节点
class BinaryTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 前序遍历
def pre_order_traversal(node):
    if node is not None:
        print(node.value)  # 访问根节点
        pre_order_traversal(node.left)  # 遍历左子树
        pre_order_traversal(node.right)  # 遍历右子树

# 中序遍历
def in_order_traversal(node):
    if node is not None:
        in_order_traversal(node.left)  # 遍历左子树
        print(node.value)  # 访问根节点
        in_order_traversal(node.right)  # 遍历右子树

# 后序遍历
def post_order_traversal(node):
    if node is not None:
        post_order_traversal(node.left)  # 遍历左子树
        post_order_traversal(node.right)  # 遍历右子树
        print(node.value)  # 访问根节点

# 层序遍历
from collections import deque

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

# 创建二叉树的根节点
root = BinaryTreeNode('A')
root.left = BinaryTreeNode('B')
root.right = BinaryTreeNode('C')
root.left.left = BinaryTreeNode('D')
root.left.right = BinaryTreeNode('E')

pre_order_traversal(root)  # 输出: A B D E C 前序：根-左-右
in_order_traversal(root)   # 输出: D B E A C 中序：左-根-右
post_order_traversal(root) # 输出: D E B C A 后序：左-右-根
level_order_traversal(root) # 输出: A B C D E 层序：从上到下，同一层从左到右 -- 优先队列

1. 二叉树和树的转换

4.1 树转换为二叉树

在二叉树中，用左孩子表示长子，用右孩子表示兄弟，可以把树转换为二叉树。

4.2 转换步骤

1. 每个节点的长子成为该节点在二叉树中的左孩子。
2. 每个节点的兄弟成为该节点在二叉树中的右孩子。
3. 所有节点的右孩子在二叉树中是连续的。

4.3 森林转换为二叉树

1. 把森林中的各棵树分别转换成二叉树。
2. 把转换后的各棵二叉树的根节点看做是兄弟节点：继续转换。

4.4 树与二叉树转换的伪代码

# 定义树节点
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.firstChild = None  # 长子
        self.nextSibling = None  # 兄弟

# 将树转换为二叉树的函数
def tree_to_binary_tree(tree):
    if tree is None:
        return None
    root = BinaryTreeNode(tree.value)
    # 长子转换为左孩子
    root.left = tree_to_binary_tree(tree.firstChild)
    # 兄弟转换为右孩子
    right = root
    while right.right:  # 找到最右边的节点
        right = right.right
    while tree.nextSibling:  # 兄弟节点
        right.right = BinaryTreeNode(tree.nextSibling.value)
        tree = tree.nextSibling
        right = right.right
    return root

# 创建树的节点
a = TreeNode('A')
b = TreeNode('B')
c = TreeNode('C')
d = TreeNode('D')
e = TreeNode('E')
f = TreeNode('F')

# 构建树结构
a.firstChild = b
b.nextSibling = c
c.nextSibling = d
b.firstChild = e
d.firstChild = f

# 转换为二叉树
binary_tree_root = tree_to_binary_tree(a)

1. 哈夫曼树及其应用

5.1 哈夫曼树的定义

哈夫曼树是一种带权路径长度最短的二叉树。它是一种特殊的二叉树，其中每个叶子节点代表一个字符，并且每个叶子节点都有一个与之关联的权值，权值通常对应于该字符在数据中的频率。

5.2 哈夫曼树的构造方法

1. 初始化：由给定的n个权值构造n棵只有一个根节点的二叉树，形成二叉树集合F。
2. 选取与合并：在F中选取根节点权值最小的两棵二叉树，增加一个根节点，其权值为两棵树根节点权值之和，并将这两棵树作为新根节点的左、右子树，合并成一棵树。
3. 重复：重复步骤2，直到F中所有二叉树合并成一棵二叉树，即哈夫曼树。

5.3 哈夫曼树的应用

• 数据压缩：通过为频率高的字符分配较短的编码，为频率低的字符分配较长的编码，实现数据压缩。
• 字符编码：用于构造字符的前缀编码，确保没有一个字的编码是另一个字编码的前缀。

5.4 构建哈夫曼树（Python伪代码）

import heapq

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    # 定义比较操作，确保优先队列中最小的节点排在前面
    def __lt__(self, other):
        return self.freq < other.freq

# 构造 哈夫曼树
def build_huffman_tree(frequencies):
    priority_queue = [HuffmanNode(char, freq) for char, freq in frequencies.items()]
    heapq.heapify(priority_queue)
    
    while len(priority_queue) > 1:
        left = heapq.heappop(priority_queue)
        right = heapq.heappop(priority_queue)
        
        merged = HuffmanNode(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        
        heapq.heappush(priority_queue, merged)
    
    return priority_queue[0]

# 从哈夫曼树生成 编码
def generate_codes(node, prefix="", code_book={}):
    if node is not None:
        if node.char is not None:
            code_book[node.char] = prefix
        generate_codes(node.left, prefix + "0", code_book)
        generate_codes(node.right, prefix + "1", code_book)
    return code_book

# 示例使用
frequencies = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
huffman_tree_root = build_huffman_tree(frequencies)
huffman_codes = generate_codes(huffman_tree_root)
print(huffman_codes)