中山大学数据结构与算法实验报告8 – Michael Yeungの学习笔记

第一题二叉搜索树的遍历

1.实验题目

2. 实验目的

本实验的主要目的是实现计算二叉树中最长交错路径的算法。通过本实验，学生能够：

理解递归和深度优先搜索（DFS）在树形结构中的应用。

掌握如何使用递归策略来实现树的遍历，处理动态方向变化的问题。

提高树形结构问题的算法设计与优化能力，尤其是涉及路径问题的求解。

3. 算法设计

为实现求解二叉树中最长交错路径的目标，使用了深度优先搜索（DFS）与递归的结合。具体的算法步骤如下：

交错路径的定义：
- 在二叉树中选择一个节点和一个方向（左或右），并从该节点开始沿该方向进行移动。
- 每次改变移动方向，从左移到右，或从右移到左，直到无法继续移动。
- 路径的长度定义为访问过的节点数目减去 1。
递归遍历：
- 通过 DFS 遍历每个节点，并在每个节点计算从该节点出发的最长交错路径。
- 对每个节点的左右子节点分别递归计算，在每次递归时会有一个方向的改变。
方向管理：
- 对于每个节点，分别向左和向右的递归路径都需要计算，并记录当前路径长度。
- 如果方向为左，则向右方向继续递归；如果方向为右，则向左方向继续递归。
最大路径的更新：
- 在递归过程中，不断更新当前树中已知的最大交错路径长度。
时间复杂度：
- 对每个节点执行两次递归（一次向左递归，一次向右递归），因此时间复杂度为 O(n)，其中 n 为节点数。
代码实现：

#include <algorithm>
#include <iostream>
#include "TreeNode.h"
using namespace std;

void dfs(TreeNode* node, int direction, int length, int* maxLength) {
    if (!node) return;  // 如果节点为空，直接返回
    *maxLength = max(*maxLength, length);  // 更新最大路径长度
    if (direction == 0) {  // 如果当前方向是向左
        dfs(node->right, 1, length + 1, maxLength);  // 向右子树递归
        dfs(node->left, 0, 1, maxLength);  // 向左子树重新开始，长度为 1
    } else {  // 如果当前方向是向右
        dfs(node->left, 0, length + 1, maxLength);  // 向左子树递归
        dfs(node->right, 1, 1, maxLength);  // 向右子树重新开始，长度为 1
    }
}

int longestZigZag(TreeNode* root) {
    if (!root) return 0;  // 如果根节点为空，返回 0
    int maxLength = 0;
    dfs(root, 0, 0, &maxLength);  // 从根节点开始，向左递归
    dfs(root, 1, 0, &maxLength);  // 从根节点开始，向右递归
    return maxLength;  // 返回最长的交错路径长度
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了一些测试用例，包括不同规模的输入：

输入样例 1：
- 树：[1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
- 输出：3
- 解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。
输入样例 2：
- 树：[1,1,1,null,1,null,null,1,1,null,1]
- 输出：4
- 解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）。

程序运行

程序使用递归和 DFS 遍历二叉树，计算每个节点出发的最大交错路径。
对于每个节点，分别计算从该节点开始向左或向右方向的交错路径，并更新最大路径。
测试不同规模的树，程序能够在合理时间内输出正确的最大交错路径。

5. 实验总结与心得

通过本次实验，我学会了如何使用递归和深度优先搜索（DFS）来求解树形结构中的路径问题。实验中的挑战主要是如何正确管理路径的方向变化和递归的返回值。通过DFS，我们能够有效地遍历所有节点，并计算每个节点出发的最长交错路径。

此外，本次实验让我进一步理解了树形结构在算法设计中的重要性，并且通过递归的方法有效解决了交错路径的问题。通过这种方式，可以大大减少计算的复杂度，并快速得出答案。

对于类似的树形路径问题，递归与动态方向管理的结合非常有效，可以适应各种树结构并且解决复杂的路径求解问题。在面对树的问题时，递归通常是一个非常高效的解法，而结合方向管理的思路使得交错路径的计算变得更加直接和简洁。

第二题判断二叉查找树是否平衡

1.实验题目

2. 实验目的

本实验的主要目的是实现一个算法，用于判断给定的二叉查找树是否为平衡二叉树，即检查树中每个节点的两颗子树的高度差是否不超过 1。通过本实验，学生能够：

理解平衡二叉树的概念和判定方法。

掌握二叉查找树的构建和递归遍历技巧。

提高递归算法的设计和优化能力，特别是在树结构问题中的应用。

3. 算法设计

为判断给定的二叉查找树是否为平衡树，我们需要以下步骤：

构建二叉查找树：
- 根据先序遍历序列，按照二叉查找树的性质构建树。
- 若待插入值小于当前节点，则递归插入到左子树；否则，递归插入到右子树。
判断树的平衡性：
- 使用递归的方法计算每个节点的左右子树高度，并判断高度差是否超过 1。
- 具体步骤：
  - 如果节点为空，返回高度为 0。
  - 递归计算左子树高度 leftHeight。
  - 如果左子树不平衡（高度为 -1），则直接返回 -1。
  - 递归计算右子树高度 rightHeight。
  - 如果右子树不平衡（高度为 -1），则直接返回 -1。
  - 如果左右子树高度差超过 1，则返回 -1，表示不平衡。
  - 否则，返回当前节点的高度，即 max(leftHeight, rightHeight) + 1。
优化：
- 在递归过程中，一旦检测到子树不平衡，立即返回，不再继续计算，避免重复计算，提高效率。
时间复杂度分析：
- 每个节点最多访问一次，时间复杂度为 O(n)，其中 n 为节点数量。
代码实现：

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

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

// 插入节点到二叉查找树
TreeNode* insert(TreeNode* root, int v) {
    if (root == nullptr) {
        root = new TreeNode(v);
    }
    else if (v < root->val) {
        root->left = insert(root->left, v);
    }
    else {
        root->right = insert(root->right, v);
    }
    return root;
}

// 判断二叉树是否平衡，返回树的高度，-1 表示不平衡
int checkBalanced(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int leftHeight = checkBalanced(root->left);
    if (leftHeight == -1) return -1; // 左子树不平衡，直接返回
    int rightHeight = checkBalanced(root->right);
    if (rightHeight == -1) return -1; // 右子树不平衡，直接返回
    if (abs(leftHeight - rightHeight) > 1) {
        return -1; // 当前节点不平衡
    }
    return max(leftHeight, rightHeight) + 1; // 返回当前子树高度
}

int main() {
    int m;
    cin >> m;
    while (m--) {
        int n;
        cin >> n;
        TreeNode* root = nullptr;
        for (int i = 0; i < n; i++) {
            int v;
            cin >> v;
            root = insert(root, v);
        }
        if (checkBalanced(root) != -1) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了以下测试用例：

输入样例：

5
2
10 5
3
1 4 7
3 
5 3 2
3
10 4 23
5
10 6 5 8 20

预期输出：
```
YES
NO
NO
YES
YES
```

程序运行

第一组测试：
- 输入：2，10 5
- 构建的树：
```
    10
   /
  5
```
- 判断过程：
- 左子树高度：1，右子树高度：0
- 高度差：1，树平衡
- 输出：YES
第二组测试：
- 输入：3，1 4 7
- 构建的树：
```
1
 \
  4
   \
    7
```
- 判断过程：
- 左子树高度：0，右子树高度：2
- 高度差：2，树不平衡
- 输出：NO
第三组测试：
- 输入：3，5 3 2
- 构建的树：
```
    5
   /
  3
 /
2
```
- 判断过程：
- 左子树高度：2，右子树高度：0
- 高度差：2，树不平衡
- 输出：NO
第四组测试：
- 输入：3，10 4 23
- 构建的树：
```
    10
   /  \
  4    23
```
- 判断过程：
- 左子树高度：1，右子树高度：1
- 高度差：0，树平衡
- 输出：YES
第五组测试：
- 输入：5，10 6 5 8 20
- 构建的树：
```
    10
   /  \
  6    20
 / \
5   8
```
- 判断过程：
- 左子树高度：2，右子树高度：1
- 高度差：1，树平衡
- 输出：YES

结果验证

程序运行后，输出与预期结果一致，说明算法正确。

5. 实验总结与心得

通过本次实验，我深入了解了二叉查找树的构建方法以及如何判断一棵二叉树是否平衡。关键在于递归地计算每个节点的高度，并在计算过程中检查子树的平衡性。

在最初的实现中，如果简单地递归计算左右子树高度，然后再判断平衡性，可能会导致重复计算，时间复杂度上升为 O(n²)。为优化算法，我在递归函数中同时返回高度信息和平衡状态，一旦发现某个子树不平衡，立即返回，避免不必要的计算。这样将时间复杂度降低到 O(n)。

实验中，我还体会到了算法优化的重要性。在处理树形结构的问题时，合理利用递归，充分利用返回值，可以大大提高算法的效率。

总的来说，这次实验让我对平衡二叉树的判定方法有了更深刻的理解，同时也提高了我对递归算法设计和优化的能力。

第三题完全二叉树-最近公共祖先

1. 实验题目

2. 实验目的

本实验的主要目的是通过实现一个算法，解决在无限大的满二叉树中找到两个结点的最近公共祖先的问题。通过本实验，学生能够：

理解二叉树结构中祖先关系的定义与计算方法。

掌握如何通过简化路径来求解最近公共祖先问题。

提高算法设计与优化能力，特别是处理树结构问题的能力。

3. 算法设计

为了解决寻找两个结点的最近公共祖先问题，使用了不断将结点向上移动的策略，直到两个结点相等。具体算法步骤如下：

路径向上移动：
- 由于树的节点编号是按照满二叉树的规则排列的，任何结点 X 的父节点是 X / 2。所以我们可以通过不断将结点向上移动，直到找到公共的祖先。
过程设计：
- 输入两个节点 X 和 Y。
- 当 X 和 Y 不相等时，比较 X 和 Y 的大小，将较大的节点除以 2，逐步向上移动，直到两者相等。
- 最后输出相等的节点即为它们的最近公共祖先。
时间复杂度：
- 每次都将一个结点除以 2，因此每次操作的时间复杂度是 O(log n)，其中 n 为结点的值。由于最多进行 log n 次操作，整体时间复杂度为 O(log n)。
代码实现：

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int x, y;
        cin >> x >> y;
        // 直到 X 和 Y 相等
        while (x != y) {
            if (x > y) {
                x /= 2;  
            } else {
                y /= 2;  
            }
        }
        cout << x << endl;
    }
    return 0;
}

4. 程序运行与测试

测试用例

为验证程序的正确性，准备了以下测试用例：

输入样例：
- t = 2
- 10 4
- 7 13
输出：
- 对于输入 10 4，最近公共祖先是 2。
- 对于输入 7 13，最近公共祖先是 3。

程序运行

程序通过标准输入和输出进行多组测试，能够有效处理每组测试中的两个结点，输出它们的最近公共祖先。
程序通过简单的路径向上移动方法，确保时间复杂度为 O(log n)，适应大规模数据的计算。

5. 实验总结与心得

通过本次实验，我理解了如何利用树的父节点关系来求解最近公共祖先的问题。通过不断地向上移动结点，直到两个结点相等，这种方法简单且高效。

在处理类似问题时，树的结构和节点的关系非常关键。通过掌握二叉树的基本性质，能够有效简化问题。特别是对于类似的路径问题，利用树的父节点关系可以大大减少运算量，避免了复杂的遍历操作。

实验让我认识到，算法的优化往往来源于对问题本质的理解，利用简化的递归或迭代方法，能够快速找到问题的最优解。

近期文章

最新评论

第一题二叉搜索树的遍历

1.实验题目

2. 实验目的

3. 算法设计

4. 程序运行与测试

测试用例

程序运行

5. 实验总结与心得

第二题判断二叉查找树是否平衡

1.实验题目

2. 实验目的

3. 算法设计

4. 程序运行与测试

测试用例

程序运行

结果验证

5. 实验总结与心得

第三题完全二叉树-最近公共祖先

1. 实验题目

2. 实验目的

3. 算法设计

4. 程序运行与测试

测试用例

程序运行

5. 实验总结与心得

发送评论编辑评论

近期文章

第一题 二叉搜索树的遍历

1.实验题目

2. 实验目的

3. 算法设计

4. 程序运行与测试

测试用例

程序运行

5. 实验总结与心得

第二题 判断二叉查找树是否平衡

1.实验题目

2. 实验目的

3. 算法设计

4. 程序运行与测试

测试用例

程序运行

结果验证

5. 实验总结与心得

第三题 完全二叉树-最近公共祖先

1. 实验题目

2. 实验目的

3. 算法设计

4. 程序运行与测试

测试用例

程序运行

5. 实验总结与心得

发送评论 编辑评论

推荐文章

第一题二叉搜索树的遍历

第二题判断二叉查找树是否平衡

第三题完全二叉树-最近公共祖先

发送评论编辑评论