树

在数据结构中，树（Tree）是一种分层的非线性数据结构，它由节点（node）和边（edge）组成，并且具有以下性质：

树的概念

1. 节点和边：树包含一组节点，通过边连接，节点之间呈现出层级关系。
2. 根节点：树的起始节点称为根节点（root），通常位于树的顶端。
3. 父节点和子节点：每个节点可以连接其他节点，称为子节点（children）；连接它们的节点称为父节点（parent）。
4. 叶子节点：没有子节点的节点称为叶子节点（leaf）。
5. 层级：树的每一层从根节点开始，按层级关系排列。
6. 路径：节点之间的路径由节点和边组成，从根节点到某个特定节点的路径是节点之间的唯一路径。

树的性质

1. 唯一根节点：树中只有一个根节点，没有父节点。
2. 节点数量关系：有 ( n ) 个节点的树，边的数量为 ( n - 1 )。
3. 层次性：树具有层次结构，自上而下逐级分层。
4. 无回路性：树中不存在回路，任何两个节点之间只有唯一一条路径。
5. 连通性：树是一个连通的无向图，从根节点可以到达所有节点。

特殊类型的树

• 二叉树：每个节点最多只有两个子节点的树。
• 完全二叉树：除最后一层外，所有层的节点数都达到最大值，且最后一层节点从左到右连续排列。
• 平衡二叉树：任意节点的左右子树高度差不超过一定值（如 AVL 树）。
• 二叉搜索树（BST）：左子节点的值小于根节点，右子节点的值大于根节点，便于快速查找。

好的，这里是考试大纲所涉及的二叉树和树的基本概念、性质和C++的实现示例：

二叉树的概念、性质和实现

二叉树是每个节点最多有两个子节点的树结构。每个节点的子节点通常被称为左子节点和右子节点。

性质：

1. 二叉树的第 (i) 层最多有 (2^{i-1}) 个节点。
2. 高度为 (h) 的二叉树最多有 (2^h - 1) 个节点。
3. 完全二叉树和满二叉树是特殊的二叉树。

实现（链式存储）：

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 插入节点示例
TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

二叉树的顺序存储结构和链式存储结构

顺序存储结构：顺序存储通常使用数组存储完全二叉树。第 (i) 个节点的左子节点在 (2i+1)，右子节点在 (2i+2)。

int binaryTree[100];  // 顺序存储二叉树的数组表示

链式存储结构：链式存储用指针实现更灵活，适用于非完全二叉树。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

遍历二叉树

前序遍历、中序遍历、后序遍历和层序遍历是常见的二叉树遍历方式。

// 前序遍历 (根 -> 左 -> 右)
void preorder(TreeNode* root) {
    if (root) {
        cout << root->val << " ";
        preorder(root->left);
        preorder(root->right);
    }
}

// 中序遍历 (左 -> 根 -> 右)
void inorder(TreeNode* root) {
    if (root) {
        inorder(root->left);
        cout << root->val << " ";
        inorder(root->right);
    }
}

// 后序遍历 (左 -> 右 -> 根)
void postorder(TreeNode* root) {
    if (root) {
        postorder(root->left);
        postorder(root->right);
        cout << root->val << " ";
    }
}

树和森林的存储结构、遍历

树的存储：一般用链式结构存储树（多叉树），每个节点指向多个子节点。

struct TreeNode {
    int val;
    vector<TreeNode*> children;  // 每个节点可以有多个子节点
    TreeNode(int x) : val(x) {}
};

森林的概念：森林是一组互不相交的树的集合。常用递归将森林表示为一棵树，每棵树的根节点作为链式存储的下一节点。

遍历森林：可以通过先序、后序等遍历方式实现，每个子树递归遍历。

void traverseForest(const vector<TreeNode*>& forest) {
    for (TreeNode* tree : forest) {
        preorder(tree);  // 遍历每棵树
    }
}

堆与优先队列

堆是一种特殊的二叉树，是完全二叉树的一种。堆有两种常见的类型：最大堆和最小堆。

• 最大堆：每个父节点的值都大于等于其子节点的值，根节点是堆中最大的元素。
• 最小堆：每个父节点的值都小于等于其子节点的值，根节点是堆中最小的元素。

堆的性质

1. 完全二叉树：堆使用完全二叉树的结构，因此适合用数组表示。
2. 节点关系：在堆的数组表示中，对于第 i 个节点：
   • 父节点位置为 (i-1)/2。
   • 左子节点位置为 2i+1。
   • 右子节点位置为 2i+2。

优先队列

优先队列是一种基于堆的数据结构，可以快速访问和删除优先级最高（或最低）的元素。在 C++ 中，标准库提供了 priority_queue，其默认实现为最大堆。

最大堆

以下是一个最大堆的简单实现，包括插入和删除最大值的操作：

#include <iostream>
#include <vector>
using namespace std;

class MaxHeap {
    vector<int> heap;

    void heapifyUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[index] > heap[parent]) {
                swap(heap[index], heap[parent]);
                index = parent;
            } else {
                break;
            }
        }
    }

    void heapifyDown(int index) {
        int size = heap.size();
        while (2 * index + 1 < size) {
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int largerChild = leftChild;

            if (rightChild < size && heap[rightChild] > heap[leftChild]) {
                largerChild = rightChild;
            }

            if (heap[index] < heap[largerChild]) {
                swap(heap[index], heap[largerChild]);
                index = largerChild;
            } else {
                break;
            }
        }
    }

public:
    void insert(int val) {
        heap.push_back(val);
        heapifyUp(heap.size() - 1);
    }

    int extractMax() {
        if (heap.empty()) return -1;
        int maxVal = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
        return maxVal;
    }

    bool isEmpty() const {
        return heap.empty();
    }
};

int main() {
    MaxHeap heap;
    heap.insert(10);
    heap.insert(20);
    heap.insert(15);

    cout << "Extracted Max: " << heap.extractMax() << endl;  // 输出 20
    cout << "Extracted Max: " << heap.extractMax() << endl;  // 输出 15
    cout << "Extracted Max: " << heap.extractMax() << endl;  // 输出 10

    return 0;
}

优先队列的实现（C++ 标准库）

C++ STL 提供了 priority_queue，默认是最大堆，但可以通过传递自定义比较器来实现最小堆。

好的，以下是一个直接实现的优先队列，不依赖 C++ 标准模板库（STL）。我们将使用最大堆的方式来实现优先队列，可以快速地获取最大值并进行插入和删除操作。最小堆的实现方式类似，只需调整比较逻辑。

基于最大堆的优先队列实现

#include <iostream>
#include <vector>
using namespace std;

class PriorityQueue {
private:
    vector<int> heap; // 使用数组来表示堆

    // 上浮操作，用于插入元素后调整堆
    void heapifyUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[index] > heap[parent]) { // 如果当前节点大于父节点，交换位置
                swap(heap[index], heap[parent]);
                index = parent; // 更新当前节点为父节点位置
            } else {
                break;
            }
        }
    }

    // 下沉操作，用于删除元素后调整堆
    void heapifyDown(int index) {
        int size = heap.size();
        while (2 * index + 1 < size) { // 只需检查左子节点存在的情况
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int largerChild = leftChild;

            // 找到较大的子节点
            if (rightChild < size && heap[rightChild] > heap[leftChild]) {
                largerChild = rightChild;
            }

            // 如果当前节点小于较大的子节点，交换
            if (heap[index] < heap[largerChild]) {
                swap(heap[index], heap[largerChild]);
                index = largerChild; // 更新当前节点为交换后的子节点位置
            } else {
                break;
            }
        }
    }

public:
    // 插入元素
    void push(int val) {
        heap.push_back(val);  // 添加到堆的末尾
        heapifyUp(heap.size() - 1); // 调整堆
    }

    // 获取最大元素
    int top() const {
        if (heap.empty()) throw runtime_error("PriorityQueue is empty");
        return heap[0];
    }

    // 删除最大元素
    void pop() {
        if (heap.empty()) throw runtime_error("PriorityQueue is empty");
        heap[0] = heap.back();  // 将最后一个元素移到堆顶
        heap.pop_back();  // 删除最后一个元素
        heapifyDown(0); // 调整堆
    }

    // 检查队列是否为空
    bool empty() const {
        return heap.empty();
    }
};

int main() {
    PriorityQueue pq;

    pq.push(10);
    pq.push(20);
    pq.push(15);

    cout << "Top Element: " << pq.top() << endl;  // 输出 20
    pq.pop();
    cout << "Top Element after pop: " << pq.top() << endl;  // 输出 15

    return 0;
}

代码解释

1. push 方法：将新元素插入堆的末尾，之后调用 heapifyUp 进行上浮调整，保证堆的最大性质。

2. top 方法：返回堆顶元素，即优先级最高的元素（最大值）。

3. pop 方法：删除堆顶元素，将堆的最后一个元素移到堆顶，并调用 heapifyDown 进行下沉调整，保证堆的最大性质。

4. heapifyUp 和 heapifyDown 方法：维护堆的性质，分别用于元素插入和删除后的调整操作。

二叉排序树

二叉排序树（Binary Search Tree, BST）是一种特殊的二叉树，用于快速查找、插入和删除操作。BST 在很多应用中用于构建集合和字典。

二叉排序树的概念

• 二叉排序树是一种有序的二叉树。对于 BST 中的每个节点 N，满足以下性质：
  1. 左子树所有节点的值小于 N 节点的值。
  2. 右子树所有节点的值大于 N 节点的值。
  3. 左右子树也是二叉排序树。

二叉排序树的性质

1. 查找、插入和删除操作的时间复杂度平均为 O(log n)，最坏情况下为 O(n)，当 BST 退化为链表（即每个节点只有一个子节点）时会达到最坏情况。
2. 中序遍历可以得到一个升序的序列。
3. 二叉排序树不允许有重复的节点。

二叉排序树的简洁 C++ 实现

以下是一个简单的 C++ 实现，包括插入、查找和删除操作：

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BinarySearchTree {
public:
    // 插入节点
    TreeNode* insert(TreeNode* root, int val) {
        if (!root) return new TreeNode(val);  // 空节点，创建新节点
        if (val < root->val)
            root->left = insert(root->left, val);  // 插入左子树
        else if (val > root->val)
            root->right = insert(root->right, val); // 插入右子树
        return root;
    }

    // 查找节点
    bool search(TreeNode* root, int val) {
        if (!root) return false;  // 空节点表示未找到
        if (val == root->val) return true;
        else if (val < root->val)
            return search(root->left, val);  // 在左子树中查找
        else
            return search(root->right, val); // 在右子树中查找
    }

    // 删除节点
    TreeNode* remove(TreeNode* root, int val) {
        if (!root) return nullptr;
        if (val < root->val)
            root->left = remove(root->left, val);  // 删除左子树节点
        else if (val > root->val)
            root->right = remove(root->right, val); // 删除右子树节点
        else { // 找到要删除的节点
            if (!root->left) {
                TreeNode* rightChild = root->right;
                delete root;
                return rightChild;
            } else if (!root->right) {
                TreeNode* leftChild = root->left;
                delete root;
                return leftChild;
            } else { // 有两个子节点
                TreeNode* minNode = getMin(root->right);
                root->val = minNode->val;  // 用右子树中的最小节点替换当前节点
                root->right = remove(root->right, minNode->val); // 删除右子树中的最小节点
            }
        }
        return root;
    }

    // 获取最小节点
    TreeNode* getMin(TreeNode* root) {
        while (root->left) root = root->left;
        return root;
    }

    // 中序遍历（输出树中节点的值）
    void inorder(TreeNode* root) {
        if (root) {
            inorder(root->left);
            cout << root->val << " ";
            inorder(root->right);
        }
    }
};

int main() {
    BinarySearchTree bst;
    TreeNode* root = nullptr;

    // 插入节点
    root = bst.insert(root, 50);
    bst.insert(root, 30);
    bst.insert(root, 20);
    bst.insert(root, 40);
    bst.insert(root, 70);
    bst.insert(root, 60);
    bst.insert(root, 80);

    // 中序遍历（输出有序序列）
    cout << "Inorder traversal: ";
    bst.inorder(root);
    cout << endl;

    // 查找节点
    cout << "Search for 40: " << (bst.search(root, 40) ? "Found" : "Not found") << endl;

    // 删除节点
    root = bst.remove(root, 20);
    cout << "Inorder traversal after deleting 20: ";
    bst.inorder(root);
    cout << endl;

    return 0;
}

代码解释

1. 插入节点：递归地找到正确的插入位置，将节点添加到左子树或右子树。
2. 查找节点：根据值在左子树或右子树中递归查找。
3. 删除节点：
   • 如果要删除的节点没有子节点，直接删除。
   • 如果只有一个子节点，用子节点替换当前节点。
   • 如果有两个子节点，用右子树中最小的节点替换当前节点，然后删除替换节点。
4. 中序遍历：按照左子树 -> 根节点 -> 右子树的顺序遍历节点，输出排序后的值。

平衡二叉树

平衡二叉树（Balanced Binary Tree）是一种改进的二叉搜索树，它保证树的高度保持平衡，从而避免最坏情况下退化为链表。常见的平衡二叉树包括 AVL树 和 红黑树。这里以 AVL树 为例，来介绍平衡二叉树的概念、性质以及实现。

平衡二叉树的概念和性质

1. 平衡因子：每个节点的左子树和右子树的高度差不超过1，称为平衡二叉树。具体来说，对于 AVL 树，任一节点的平衡因子（左子树高度减去右子树高度的差）只能是 -1、0 或 1。

2. 自平衡：在插入或删除节点后，AVL 树会通过旋转操作（如单旋转、双旋转）来恢复平衡。

3. 查找、插入和删除操作的时间复杂度为 (O(\log n))，这是因为 AVL 树总是保持平衡，树的高度始终为 (O(\log n))。

AVL 树的旋转操作

• 左旋：右子树高度大于左子树时，将右子节点旋转为根节点。
• 右旋：左子树高度大于右子树时，将左子节点旋转为根节点。
• 双旋转：当插入节点破坏平衡因子后，先进行一次左旋或右旋，再进行一次右旋或左旋。

AVL 树的简洁 C++ 实现

以下是一个包含插入操作的简单 AVL 树实现代码。插入操作后会进行平衡调整。

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    int height;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr), height(1) {}
};

class AVLTree {
public:
    // 获取节点高度
    int getHeight(TreeNode* node) {
        return node ? node->height : 0;
    }

    // 更新节点高度
    int getBalance(TreeNode* node) {
        return node ? getHeight(node->left) - getHeight(node->right) : 0;
    }

    // 右旋
    TreeNode* rightRotate(TreeNode* y) {
        TreeNode* x = y->left;
        TreeNode* T2 = x->right;

        // 旋转
        x->right = y;
        y->left = T2;

        // 更新高度
        y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
        x->height = max(getHeight(x->left), getHeight(x->right)) + 1;

        return x;
    }

    // 左旋
    TreeNode* leftRotate(TreeNode* x) {
        TreeNode* y = x->right;
        TreeNode* T2 = y->left;

        // 旋转
        y->left = x;
        x->right = T2;

        // 更新高度
        x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
        y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

        return y;
    }

    // 插入节点并保持平衡
    TreeNode* insert(TreeNode* node, int val) {
        if (!node) return new TreeNode(val);

        // 插入到左子树或右子树
        if (val < node->val) node->left = insert(node->left, val);
        else if (val > node->val) node->right = insert(node->right, val);
        else return node; // 不允许插入重复值

        // 更新当前节点高度
        node->height = 1 + max(getHeight(node->left), getHeight(node->right));

        // 检查平衡因子并旋转
        int balance = getBalance(node);

        // 左左情况
        if (balance > 1 && val < node->left->val)
            return rightRotate(node);

        // 右右情况
        if (balance < -1 && val > node->right->val)
            return leftRotate(node);

        // 左右情况
        if (balance > 1 && val > node->left->val) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }

        // 右左情况
        if (balance < -1 && val < node->right->val) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }

        return node;
    }

    // 中序遍历输出
    void inorder(TreeNode* root) {
        if (root) {
            inorder(root->left);
            cout << root->val << " ";
            inorder(root->right);
        }
    }
};

int main() {
    AVLTree avl;
    TreeNode* root = nullptr;

    // 插入节点
    root = avl.insert(root, 10);
    root = avl.insert(root, 20);
    root = avl.insert(root, 30);
    root = avl.insert(root, 40);
    root = avl.insert(root, 50);
    root = avl.insert(root, 25);

    // 输出中序遍历
    cout << "Inorder traversal of AVL tree: ";
    avl.inorder(root);
    cout << endl;

    return 0;
}

代码解释

1. getHeight 和 getBalance：用于计算节点的高度和平衡因子。
2. 右旋和左旋操作：用于在失衡时恢复平衡。
3. insert 操作：按二叉搜索树的规则插入新节点，并在每次插入后检查平衡性并进行必要的旋转操作。
4. inorder 遍历：用于输出 AVL 树中节点的值，验证树结构的正确性。

哈夫曼(Huffman)树和哈夫曼编码

哈夫曼树（Huffman Tree）和哈夫曼编码（Huffman Coding）是数据压缩领域的重要概念。它们通过使用变长编码表对频率较高的数据分配较短的编码，从而有效地减少数据的存储空间。

哈夫曼树的概念

• 哈夫曼树是一种带权路径长度最短的二叉树，用于实现最优前缀编码。通常用于无损数据压缩。
• 在哈夫曼树中，频率较高的字符会被分配较短的编码，而频率较低的字符会被分配较长的编码，从而使整体编码长度最小化。

哈夫曼编码的概念

• 哈夫曼编码是一种基于哈夫曼树的前缀编码。每个字符用一串二进制数字表示，且不同字符的编码无公共前缀（前缀编码），避免了编码歧义。
• 在构建哈夫曼树后，从根到每个叶节点的路径形成该节点的编码，左子树为 0，右子树为 1。

哈夫曼树的性质

1. 最优编码：哈夫曼编码是无损压缩的最优编码方式之一，可有效减少存储空间。
2. 前缀编码：无公共前缀，避免编码歧义。
3. 构造复杂度：哈夫曼树构建过程的时间复杂度为 (O(n \log n))，其中 (n) 是字符的种类数。

无公共前缀的意思是，在一个编码系统中，任何一个字符的编码都不是另一个字符编码的开头部分（前缀）。在这种情况下，解码时不会有歧义，因为每个编码是唯一且独立的。

在哈夫曼编码中，这种“无公共前缀”性质被称为前缀码（Prefix Code）。具体来说：

• 例如，如果字符 A 的编码是 0，字符 B 的编码是 10，字符 C 的编码是 110，字符 D 的编码是 111，那么这些编码没有公共前缀，因为：
  • 0 不会是其他编码（10, 110, 111）的前缀。
  • 10 也不会是 110 或 111 的前缀。

这样可以确保唯一解码，即每当我们解码时，遇到编码 0 时立即知道是 A，遇到 10 时就是 B，以此类推。

哈夫曼树和哈夫曼编码的C++实现

以下是一个简洁的C++实现，使用最小堆来构建哈夫曼树，并生成哈夫曼编码。

#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <string>
using namespace std;

// 定义哈夫曼树的节点结构
struct HuffmanNode {
    char ch;              // 字符
    int freq;             // 字符频率
    HuffmanNode* left;    // 左子节点
    HuffmanNode* right;   // 右子节点

    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 比较函数，用于优先队列（最小堆）
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

// 生成哈夫曼编码
void generateCodes(HuffmanNode* root, string code, unordered_map<char, string>& huffmanCode) {
    if (!root) return;

    // 到达叶节点，保存字符及其对应编码
    if (!root->left && !root->right) {
        huffmanCode[root->ch] = code;
    }

    generateCodes(root->left, code + "0", huffmanCode);
    generateCodes(root->right, code + "1", huffmanCode);
}

// 释放哈夫曼树内存
void freeTree(HuffmanNode* root) {
    if (!root) return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

// 构建哈夫曼树并生成编码
unordered_map<char, string> buildHuffmanTree(const unordered_map<char, int>& freq) {
    // 使用最小堆来构建哈夫曼树
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> minHeap;

    // 初始化每个字符的节点并加入优先队列
    for (const auto& pair : freq) {
        minHeap.push(new HuffmanNode(pair.first, pair.second));
    }

    // 合并节点，构建哈夫曼树
    while (minHeap.size() > 1) {
        HuffmanNode* left = minHeap.top(); minHeap.pop();
        HuffmanNode* right = minHeap.top(); minHeap.pop();

        // 创建新的内部节点，频率为左右子节点频率之和
        HuffmanNode* sum = new HuffmanNode('\0', left->freq + right->freq);
        sum->left = left;
        sum->right = right;
        minHeap.push(sum);
    }

    // 生成哈夫曼编码
    HuffmanNode* root = minHeap.top();
    unordered_map<char, string> huffmanCode;
    generateCodes(root, "", huffmanCode);

    freeTree(root);  // 释放内存
    return huffmanCode;
}

int main() {
    // 定义字符频率
    unordered_map<char, int> freq = {
        {'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}
    };

    // 构建哈夫曼树并生成编码
    unordered_map<char, string> huffmanCode = buildHuffmanTree(freq);

    // 输出编码
    cout << "Huffman Codes:\n";
    for (const auto& pair : huffmanCode) {
        cout << pair.first << " : " << pair.second << endl;
    }

    return 0;
}

代码解释

1. HuffmanNode：定义哈夫曼树的节点结构体，包含字符、频率及左右子节点。
2. Compare 函数对象：用于最小堆比较，以频率为基础构建最小堆。
3. buildHuffmanTree：构建哈夫曼树，通过合并最小频率的节点，最终形成一棵树。
4. generateCodes：递归生成编码，通过树的路径生成每个字符的二进制编码。
5. main 函数：定义字符频率，调用 buildHuffmanTree 构建哈夫曼树并生成编码，最后输出编码结果。

输出示例

假设频率表为 {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}，输出结果可能如下：

Huffman Codes:
a : 1100
b : 1101
c : 100
d : 101
e : 111
f : 0

代码说明

通过哈夫曼编码，字符 ‘f’ 频率最高，编码最短，而频率较低的字符 ‘a’ 和 ‘b’ 编码更长，从而达到压缩效果。