Trees

树的定义与特性

树的基本定义

树是节点的集合，可以是：
- 一个空的节点集合，或者
- 包含一个称为根节点的节点，从根节点向下可以有零个或多个子树（子节点）。

树的性质

路径唯一性：
- 树中两个节点之间最多有一条路径。
无环性：
- 从节点 $N$ 出发的非零路径是否可以再次到达节点 $N$？
  - 答案：不可以。树中不能有循环（环）。

树的结构

每棵树由多个节点构成，节点之间通过边（links）相连。
树的结构通常包含以下术语：
- 节点（Node）：树的基本单元，存储数据。
- 边（Edge）：连接两个节点的线，表示节点之间的关系。
- 根节点（Root Node）：树的顶端节点，所有其他节点都是其子孙。
- 叶子节点（Leaf Node）：没有子节点的节点。
- 子树（Subtree）：以某个节点为根的树。
- 路径（Path）：从一个节点到另一个节点的边的序列。
- 深度（Depth）：从根节点到节点的路径长度。
- 高度（Height）：从节点到其最深的叶子节点的最长路径长度。

树的术语

节点深度：节点 $N$ 的深度是从根节点到 $N$ 的路径长度。
节点高度：节点 $N$ 的高度是从 $N$ 到叶子节点的最长路径的长度。
树的深度：树中最深节点的深度。
树的高度：根节点的高度。

树的特点总结

树是一种非线性的数据结构，适合表达层次关系。
在树结构中，节点的连接是单向的，不允许形成环路。
每个节点可以有多个子节点，但只有一个父节点。

例子

文件目录结构：
- 计算机中的文件系统可以用树来表示，根节点是磁盘驱动器，各个文件夹和文件是子节点。
组织结构图：
- 组织中各级别的员工可以用树形结构表示，根节点是最高领导，子节点是各级别管理者和员工。

证明：一棵树有 $ N $ 个节点时，总是有 $ N - 1 $ 条边

定理

在一棵有 $ N $ 个节点的树中，总是有 $ N - 1 $ 条边。

归纳证明

基础情况：$ N = 1 $

考虑一棵只有一个节点（根节点）的树。

这棵树没有边。

因此，对于 $ N = 1 $：$ = 1 - 1 = 0 $

基础情况成立。

归纳假设

假设该定理对于 $ N = k $ 的树成立。

也就是说，我们假设有 $ k $ 个节点的树有 $ k - 1 $ 条边。

归纳步骤：证明其对于 $ N = k + 1 $ 成立

现在，考虑一棵有 $ N = k + 1 $ 个节点的树。

我们需要证明这棵树有 $ (k + 1) - 1 = k $ 条边。

从有 $ k $ 个节点的树开始，根据归纳假设，该树有 $ k - 1 $ 条边。

为了创建一棵有 $ k + 1 $ 个节点的树，我们添加一个新节点（记作节点 $ k + 1 $）。

这个新节点必须与现有的树相连。

为了保持树的性质（特别是无环性），新节点只能通过一条边连接到现有的节点上。

结论

如果新节点通过多条边连接，则会形成一个环，违反树的定义。

因此，新节点仅通过一条边连接。

这意味着： $ = (k - 1) + 1 = k $

因此，对于 $ N = k + 1 $，树有 $ k $ 条边。

最终结果

通过数学归纳法，我们得出结论：一棵有 $ N $ 个节点的树总是有 $ N - 1 $ 条边，适用于所有 $ N $。

树的实现

基于指针的实现

// 树的节点声明
struct TreeNode {
  Object element;          // 节点值
  TreeNode *firstChild;   // 指向第一个子节点的指针
  TreeNode *nextSibling;  // 指向下一个兄弟节点的指针
};

实现思路:
- 使用指针表示节点的值及其子节点关系。
- 可通过第一个子节点/下一个兄弟节点的方式，灵活处理任意数量的子节点。

二叉树

定义: 每个节点最多有两个子节点。
特性:
- 二叉树是计算机科学中最流行的树。
- 最小深度 $d_{min} = \log_2 N$。

树的深度与节点数量的关系

节点数量

在深度 $ d $ 的树中，节点的数量 $ N $ 的范围为： $ N = 2^d 2^{d+1} - 1 $

深度与节点数量的关系

最小深度 $ d $ 与节点数量 $ N $ 的关系为： $ d = (N) $ 这表示深度 $ d $ 的增长与节点数量 $ N $ 的对数成正比。

大O符号与渐近相等

当我们说 $ T(n) = (f(n)) $ 时，这意味着：
- $ T(n) = O(f(n)) $（$ T(n) $ 的增长不超过 $ f(n) $ 的增长）
- $ f(n) = O(T(n)) $（$ f(n) $ 的增长不超过 $ T(n) $ 的增长）
因此，$ T(n) $ 和 $ f(n) $ 具有相同的增长速率。

示例

当 $ d = 2 $ 时，节点数量 $ N $ 的范围为： $ N = 2^2 2^{3} - 1 $ 即： $ N = 4 7 $
最大深度为 $N-1$（链表的情况）。

二叉树的节点模板

template <typename E>
class BinNode {
public:
    virtual E& element() = 0; // 返回节点的值
    virtual void setElement(const E&) = 0; // 设置节点的值
    
    virtual BinNode* left() const = 0; // 返回节点的左子树
    virtual void setLeft(BinNode*) = 0; // 设置左子树

    virtual BinNode* right() const = 0; // 返回右子树
    virtual void setRight(BinNode*) = 0; // 设置右子树

    virtual bool isLeaf() = 0; // 检查节点是否为叶子节点
};

遍历的递归定义

遍历二叉树的定义是递归的，以下是常见的遍历方式：

前序遍历（Preorder Traversal）：
- 访问根节点
- 递归访问左子树
- 递归访问右子树
示例:
- 表达式：+ * + A B C D
中序遍历（Inorder Traversal）：
- 递归访问左子树
- 访问根节点
- 递归访问右子树
示例:
- 表达式：A + B * C + D
后序遍历（Postorder Traversal）：
- 递归访问左子树
- 递归访问右子树
- 访问根节点
示例:
- 表达式：A B + C * D +

前序遍历的实现

template<typename E>
void preorder(BinNode<E>* root){
    if (root == NULL) return; // 空子树
    visit(root);  // 执行所需操作
    preorder(root->left());
    preorder(root->right());
}

中序遍历的实现

template<typename E>
void inorder(BinNode<E>* root) {
    if (root == NULL) return; // 空子树
    inorder(root->left());    // 递归访问左子树
    visit(root);              // 执行所需操作
    inorder(root->right());   // 递归访问右子树
}

后序遍历的实现

template<typename E>
void postorder(BinNode<E>* root) {
    if (root == NULL) return; // 空子树
    postorder(root->left());  // 递归访问左子树
    postorder(root->right()); // 递归访问右子树
    visit(root);              // 执行所需操作
}

示例树结构

假设我们有以下二叉树：
1
2
3
4
5
    A
   / \
  B   C
 / \   \
D   E   F
1. 前序遍历 (Preorder Traversal)

遍历顺序：访问根节点，先左子树，再右子树。

步骤：

访问 A

访问 B

访问 D

访问 E

访问 C

访问 F

前序遍历结果：A, B, D, E, C, F

2. 中序遍历 (Inorder Traversal)

遍历顺序：先访问左子树，再根节点，最后右子树。

步骤：

访问 D (左子树)

访问 B (根节点)

访问 E (右子树)

访问 A (根节点)

访问 C (右子树)

访问 F (右子树)

中序遍历结果：D, B, E, A, C, F

3. 后序遍历 (Postorder Traversal)

遍历顺序：先访问左子树，再右子树，最后根节点。

步骤：

访问 D (左子树)

访问 E (右子树)

访问 B (根节点)

访问 F (右子树)

访问 C (根节点)

访问 A (根节点)

后序遍历结果：D, E, B, F, C, A

唯一二叉树的构造

给定两种遍历方式（前序和中序或后序和中序），可以构建唯一的二叉树。

示例 1

前序遍历: G H I J
中序遍历: I H G J

构建步骤：

根据前序遍历，根节点为 G。
在中序遍历中，G 左边为左子树（I H），右边为右子树（J）。
继续递归构建 H 的左子树为 I，右子树为空，右子树为 J。

示例 2

后序遍历: D E C B H G F A
中序遍历: B D C E A F H G

构建步骤：

根据后序遍历，根节点为 A。
在中序遍历中，A 左边为左子树（B D C E），右边为右子树（F H G）。
继续递归构建左右子树。

代码详情见力扣构建二叉树。

二叉搜索树

定义: 二叉树中，左子树中的所有值小于节点值，右子树中的所有值大于节点值。
操作: 查找、查找最小值、查找最大值、插入、删除。
中序遍历结果: 按升序排列的值。

二叉搜索树的性质

定义：二叉搜索树是一种特殊的二叉树，其中每个节点的左子树包含小于该节点值的所有值，而右子树包含大于该节点值的所有值。
特性：
- 节点的值遵循左 < 节点 < 右的关系。
- 左右子树均为二叉搜索树。

基本操作

查找（Find）

实现：递归比较当前节点的值与要查找的值，决定向左或向右子树继续查找。
时间复杂度：平均情况下为 $O(\log n)$，最坏情况下为 $O(n)$。

bool contains(const Comparable &x, BinaryNode *t) const {
    if (t == nullptr) return false; // 空树
    else if (x < t->element) return contains(x, t->left); // 左子树查找
    else if (t->element < x) return contains(x, t->right); // 右子树查找
    else return true; // 找到
}

查找最小值（FindMin）

实现：沿着左子树不断查找，直到找到最左侧的节点。
时间复杂度：平均情况下为 $O(\log n)$，最坏情况下为 $O(n)$。

BinaryNode *findMin(BinaryNode *t) const {
    if (t == nullptr) return nullptr; // 空树
    if (t->left == nullptr) return t; // 找到最小值
    return findMin(t->left); // 继续查找
}

查找最大值（FindMax）
- 实现：沿着右子树查找，直到找到最右侧的节点。
- 时间复杂度同查找最小值。

插入（Insert）

实现：查找合适的位置插入新的节点，遵循BST的性质。
时间复杂度：平均情况下为 $O(\log n)$，最坏情况下为 $O(n)$。

void insert(const Comparable &x, BinaryNode *&t) {
    if (t == nullptr)
        t = new BinaryNode{x, nullptr, nullptr}; // 创建新节点
    else if (x < t->element)
        insert(x, t->left); // 插入左子树
    else if (t->element < x)
        insert(x, t->right); // 插入右子树
    else
        ; // 重复，不插入
}

删除（Remove）

实现：查找要删除的节点，根据其子树的情况（无子树、一个子树、两个子树）来决定如何替换。
删除策略：
- 如果没有子节点，直接删除。
- 如果有一个子节点，用该子节点替换。
- 如果有两个子节点，用右子树中最小的节点替换（继承其值），然后递归删除该节点。
时间复杂度同插入。

void remove(const Comparable &x, BinaryNode *&t) {
    if (t == nullptr) return; // 找不到该项，什么都不做
    if (x < t->element)
        remove(x, t->left); // 在左子树删除
    else if (t->element < x)
        remove(x, t->right); // 在右子树删除
    else if (t->left != nullptr && t->right != nullptr) { // 有两个子节点
        t->element = findMin(t->right)->element; // 复制右子树最小值
        remove(t->element, t->right); // 删除右子树中最小值
    } else { // 至少有一个子节点
        BinaryNode *oldNode = t;
        t = (t->left != nullptr) ? t->left : t->right; // 用子节点替换
        delete oldNode; // 删除旧节点
    }
}

平衡的重要性

操作成本：查找、插入和删除操作的成本与树的深度有关，理想情况下深度应为 $O(\log n)$。
平衡树的优点：通过保持树的平衡，能够减少最坏情况下的操作时间。
- 平均情况下：平衡二叉搜索树的时间复杂度为 $O(\log n)$。
- 最坏情况下：如果树不平衡（如链状结构），时间复杂度为 $O(n)$。