数据结构-----树的说明和应用

定义

树是一种由结点和边组成的非线性数据结构，具有分层次的结构，每个结点都有零个或多个子结点。

术语

结点（Node）：树的基本元素，包含数据和指向子结点的链接。
根结点（Root）：树的顶端结点，没有父结点。
子结点（Child Node）：一个结点的下一级结点。
父结点（Parent Node）：一个结点的上一级结点。
叶结点（Leaf Node）：没有子结点的结点。
内部结点（Internal Node）：有至少一个子结点的结点。
边（Edge）：连接父结点和子结点的链接。
路径（Path）：从一个结点到另一个结点的边的序列。
深度（Depth）：从根结点到某个结点的路径长度。
高度（Height）：从某个结点到叶结点的最长路径长度。
子树（Subtree）：由某个结点及其所有后代结点组成的树。

树的分类

二叉树（Binary Tree）：每个结点最多有两个子结点。

完全二叉树（Complete Binary Tree）：除最后一层外，其他层的结点都是满的，且最后一层的结点从左到右依次排列。

满二叉树（Full Binary Tree）：每个结点要么没有子结点，要么有两个子结点。

// 只有一个结点（没有子结点）
    1

// 三层满二叉树（每个结点有两个子结点）
        1
       / \
      2   3
     / \ / \
    4  5 6  7

平衡二叉树（Balanced Binary Tree）：任何结点的左右子树的高度差不超过1。平衡二叉树的结构确保了较好的搜索、插入和删除性能，使这些操作的时间复杂度保持在 𝑂(log⁡𝑛) 水平。

// 例1
	4
   / \
  2   6
 / \ / \
1  3 5  7
// 例2
	10
   /  \
  5    15
 / \     \
3   7    20
 \
  4

二叉搜索树（Binary Search Tree, BST）：对每个结点，其左子树所有结点的值均小于该结点的值，右子树所有结点的值均大于该结点的值。每二叉搜索树的这种特性使得查找、插入和删除操作的平均时间复杂度为 𝑂(log⁡𝑛)

// 插入顺序：5, 3, 7, 2, 4, 6, 8
        5
       / \
      3   7
     / \ / \
    2  4 6  8
// 插入顺序：10, 5, 15, 3, 7, 12, 18, 1, 4, 6, 8, 11, 13, 17, 19
            10
          /    \
        5       15
      /  \     /   \
     3    7   12   18
    / \  / \  / \  / \
   1  4 6  8 11 13 17 19

N叉树（N-ary Tree）：每个结点最多有N个子结点。

特殊树：

B树（B-Tree）：用于数据库和文件系统的自平衡树。

假设我们有一个阶数为3的B树（每个节点最多可以有2个关键字，3个子节点）。
插入顺序：10, 20, 5, 6, 12, 30, 7, 17

       [10, 20]
      /    |    \
[5, 6, 7]  [12]  [17, 30]

在这个B树中：

根节点包含关键字10和20，有三个子节点。
左子节点包含关键字5、6和7，没有子节点（叶子节点）。
中子节点包含关键字12，没有子节点（叶子节点）。
右子节点包含关键字17和30，没有子节点（叶子节点）。
插入更多的关键字
插入关键字21后，B树的结构会发生变化，需要进行分裂和调整。

        [10, 20]
      /     |     \
[5, 6, 7]  [12]  [17, 21, 30]

当插入关键字4后，左子节点会分裂：

              [10, 20]
           /     |     \
    [5, 6]      [12]  [17, 21, 30]
   /    \
[4]    [7]

通过这种结构，B树确保了所有叶子节点都在同一层，并且每个节点的子节点数在给定范围内（这里为2到3）。这使得B树在处理大量数据时仍然保持高效的操作性能。

B+树（B+ Tree）：B树的变种，所有值都存储在叶结点，内部结点只存储键。

B+树是B树的一种变种，所有值都存储在叶子节点中，而内部节点只存储键用于索引。B+树在数据库和文件系统中有广泛应用，因为它能有效地进行范围查询。
假设我们有一个阶数为3的B+树（每个节点最多可以有2个关键字，3个子节点）。
插入顺序：10, 20, 5, 6, 12, 30, 7, 17

    [10, 20]
   /    |    \
[5, 6, 7]  [12, 17]  [20, 30]

在这个B+树中：

根节点包含关键字10和20，有三个子节点。
左子节点包含关键字5、6和7，指向包含这些值的叶子节点。
中子节点包含关键字12和17，指向包含这些值的叶子节点。
右子节点包含关键字20和30，指向包含这些值的叶子节点。

叶子节点链接

叶子节点通常通过链表相连，以便于范围查询。

    [10, 20]
    /    |    \
/[5, 6, 7]/->[12, 17]/->[20, 30]/

插入更多的关键字

插入关键字21后，B+树的结构会发生变化，需要进行分裂和调整。

    [10, 20]
   /    |    \
[5, 6, 7]  [12, 17]  [20, 21, 30]

当插入关键字4后，左子节点会分裂：

           [10, 20]
         /      |      \
[4, 5, 6]     [12, 17]     [20, 21, 30]
    \          \            /
     [7]        [12, 17]    [20, 21, 30]

红黑树（Red-Black Tree）：一种平衡二叉搜索树，确保基本操作的时间复杂度为O(log n)。

红黑树每个节点都包含一个额外的颜色属性，可以是红色或黑色。红黑树通过以下规则保持平衡：

每个节点是红色或黑色。
根节点是黑色。
所有叶子节点（NIL节点）是黑色。
如果一个节点是红色，则它的两个子节点都是黑色（不能有两个连续的红色节点）。
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
插入顺序：10, 20, 30, 15, 25, 5, 1

        10(黑)
       /     \
    5(红)     20(黑)
   /        /     \
1(黑)     15(红)  25(黑)
                  \
                  30(红)

在这个红黑树中：

根节点10是黑色的。
结点20是黑色的，左子节点15是红色的，右子节点25是黑色的。
结点25的右子节点30是红色的。
结点5是红色的，左子节点1是黑色的。

插入规则和调整

插入10：树为空，10作为根节点，颜色为黑色。
插入20：20作为10的右子节点，颜色为红色。
插入30：30作为20的右子节点，颜色为红色。违反规则4，需要调整。
- 将20和10的颜色交换，然后进行左旋。
插入15：15作为20的左子节点，颜色为红色。
插入25：25作为20的右子节点，颜色为红色。需要调整。
- 进行颜色调整并右旋。
插入5：5作为10的左子节点，颜色为红色。
插入1：1作为5的左子节点，颜色为黑色（插入调整为红色，但因规则调整为黑色）。
最终形成的红黑树符合所有红黑树的规则，保持平衡。红黑树的插入和删除操作通过颜色变化和旋转来保持树的平衡，使得其基本操作的时间复杂度为 𝑂(log⁡𝑛)O(logn)。

AVL树：一种平衡二叉搜索树，严格保持平衡，左右子树的高度差不超过1。

每个节点的左右子树的高度差（平衡因子）不超过1。AVL树通过旋转操作来保持平衡。
插入顺序：10, 20, 30, 40, 50, 25
插入10, 20, 30

这导致了不平衡，需要进行左旋转：

  20
 /  \
10    30

插入40

插入50

这导致了不平衡，需要进行左旋转：

插入25

这导致了不平衡，需要进行右左旋转：

     30
    /  \
  20    40
  / \     \
10  25    50

最终形成的AVL树符合AVL树的平衡规则，每个节点的左右子树高度差不超过1。

AVL树的旋转操作

右旋转（Right Rotation）
左旋转（Left Rotation）
左右旋转（Left-Right Rotation）
右左旋转（Right-Left Rotation）
这些旋转操作通过调整树的结构来保持平衡。每次插入或删除操作后，AVL树都会检查平衡因子并进行相应的旋转，以确保树的平衡。AVL树的基本操作的时间复杂度为 𝑂(log⁡𝑛)O(logn)。

Trie（前缀树）：用于快速检索字符串集合中的元素。

每个节点代表一个字符，路径从根节点到某个节点的字符串表示该节点的前缀。
插入单词： “hello”, “hi”, “her”, “hero”, “heat”

          root
         /  |  \
        h   h   h
       /   / \   \
      e   i   e   e
     /   |   / \   \
    l    i  r   a   r
   / \       |   |   \
  l   r      o   t    o
 /          /
o          r

在这个Trie中：

根节点是空的（root）。
第一层的节点表示单词的第一个字符：“h”。
第二层的节点表示单词的第二个字符：“e”、“i”。
第三层及以下的节点依次表示单词的后续字符。
每个单词通过从根节点到叶子节点的路径表示：
“hello” 路径为：root -> h -> e -> l -> l -> o
“hi” 路径为：root -> h -> i
“her” 路径为：root -> h -> e -> r
“hero” 路径为：root -> h -> e -> r -> o
“heat” 路径为：root -> h -> e -> a -> t

Trie的应用

Trie广泛用于以下场景：

自动补全：输入法和搜索引擎中的自动补全功能。
拼写检查：快速查找和纠正单词的拼写错误。
前缀查询：查找具有共同前缀的所有单词。
IP路由（最长前缀匹配）：在网络路由中的应用。
Trie通过共享前缀实现了高效的存储和检索，在处理大量字符串时具有显著的优势。

树的表示方法

链式存储（Linked Representation）：每个结点包含数据和指向子结点的指针。
顺序存储（Sequential Representation）：用数组来表示树，特别适用于完全二叉树。

树的遍历

示例一个树

      A
     / \
    B   C
   / \   \
  D   E   F
 / \
G   H

深度优先遍历（DFS, Depth-First Search）：

前序遍历（Preorder Traversal）：先访问根结点，再遍历左子树，最后遍历右子树。
中序遍历（Inorder Traversal）：先遍历左子树，再访问根结点，最后遍历右子树。
后序遍历（Postorder Traversal）：先遍历左子树，再遍历右子树，最后访问根结点。

搜索顺序

沿着树的深度遍历树的节点。遍历一条分支直到最后一个节点，然后回溯并遍历其他分支。

A -> B -> D -> G -> H -> E -> C -> F

DFS 图示

    A
   / 
  B  
 / 
D  
/ \
G  H
\
 E
 \
  C
   \
    F

广度优先遍历（BFS, Breadth-First Search）：

层序遍历（Level-order Traversal）：按层次逐层遍历。

搜索顺序

从根节点开始，沿着树的宽度遍历树的节点。

A -> B -> C -> D -> E -> F -> G -> H

BFS 图示

    A
   / \
  B   C
 / \   \
D   E   F
/ \
G   H

树的操作

插入（Insertion）：在树中添加新结点。
删除（Deletion）：从树中删除指定结点。
查找（Search）：在树中查找特定结点。
合并（Merge）：将两棵树合并成一棵树。
分裂（Split）：将一棵树分裂成两棵树。

树的应用

文件系统：文件和目录的组织结构。
表达式树：表示和计算算术表达式。
决策树：用于机器学习中的分类和回归问题。
XML/HTML解析：DOM树结构，用于解析和操作XML/HTML文档。
路由算法：网络中的路径选择。
数据索引：如数据库索引（B树、B+树）。
字符串处理：如Trie用于快速字符串检索。

树的复杂度分析

时间复杂度：讨论树的各种操作（如插入、删除、查找）的时间复杂度。
空间复杂度：树的存储空间需求分析。

树的实现

编程语言示例：使用常见编程语言（如Python、Java、C++）实现各种树结构和操作。
案例分析：具体应用中的树结构实现，如实现一个简单的文件系统或表达式计算器。
以python实现一个表达式计算器为例

数据结构

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

表达式树的构建和计算

class ExpressionTree:
    def __init__(self):
        self.root = None

    def build_tree(self, expression):
        stack = []
        for char in expression:
            if char.isdigit():
                node = TreeNode(char)
                stack.append(node)
            else:
                node = TreeNode(char)
                node.right = stack.pop()
                node.left = stack.pop()
                stack.append(node)
        self.root = stack.pop()

    def evaluate(self, node):
        if node.left is None and node.right is None:
            return int(node.value)
        left_value = self.evaluate(node.left)
        right_value = self.evaluate(node.right)
        if node.value == '+':
            return left_value + right_value
        elif node.value == '-':
            return left_value - right_value
        elif node.value == '*':
            return left_value * right_value
        elif node.value == '/':
            return left_value / right_value

    def calculate(self):
        if self.root is None:
            raise ValueError("The expression tree is empty")
        return self.evaluate(self.root)

    def print_tree(self, node, level=0):
        if node is not None:
            self.print_tree(node.right, level + 1)
            print(' ' * 4 * level + '->', node.value)
            self.print_tree(node.left, level + 1)

# 示例表达式
expression = "34+5*"
tree = ExpressionTree()
tree.build_tree(expression)

print("表达式树:")
tree.print_tree(tree.root)

result = tree.calculate()
print("计算结果:", result)

详细解释

TreeNode 类：用于表示树中的每个节点。每个节点要么是一个操作数（数字），要么是一个操作符（+、-、*、/）。
ExpressionTree 类：用于表示整个表达式树。
- build_tree 方法：从后缀表达式构建表达式树。使用栈将操作数推入栈中，遇到操作符时，弹出两个操作数作为左右子节点。
- evaluate 方法：递归地计算表达式树的值。
- calculate 方法：计算表达式树的值，从根节点开始。
- print_tree 方法：打印表达式树的结构。