数据结构与算法试卷B

二叉搜索树

输入序列：{46, 25, 78, 62, 12, 37, 70, 29}

  1. 插入 46:

    • 树为空，46成为根节点。
    1
    46

  2. 插入 25:

    • 25 小于 46，插入到 46 的左边。
    1
    2
    3
      46
     /
    25

  3. 插入 78:

    • 78 大于 46，插入到 46 的右边。
    1
    2
    3
      46
     /  \
    25   78

  4. 插入 62:

    • 62 大于 46，小于 78，插入到 78 的左边。
    1
    2
    3
    4
    5
      46
     /  \
    25   78
       /
     62

  5. 插入 12:

    • 12 小于 46，小于 25，插入到 25 的左边。
    1
    2
    3
    4
    5
        46
       /  \
      25   78
     /    /
    12   62

  6. 插入 37:

    • 37 小于 46，大于 25，插入到 25 的右边。
    1
    2
    3
    4
    5
        46
       /  \
      25   78
     /  \  /
    12  37 62

  7. 插入 70:

    • 70 大于 46，小于 78，大于 62，插入到 62 的右边。
    1
    2
    3
    4
    5
    6
    7
        46
       /  \
      25   78
     /  \  /
    12  37 62
             \
              70

  8. 插入 29:

    • 29 小于 46，大于 25，小于 37，插入到 37 的左边。
    1
    2
    3
    4
    5
    6
    7
        46
       /  \
      25   78
     /  \  /
    12  37 62
       /   \
      29    70

最终的二叉搜索树结构如下：

1
2
3
4
5
6
7
    46
   /  \
  25   78
 /  \  /
12  37 62
   /   \
  29    70

这样每一层的节点都有正确的对齐，格式清晰了。

递归求和

问题：

假设给定的二叉树存储整数值。请编写一个递归函数，计算并返回树中所有节点值的和。

解释：

这个问题要求我们编写一个递归函数，遍历二叉树的每个节点，并返回所有节点值的和。在递归过程中，首先计算当前节点的值，然后递归地计算左子树和右子树的节点值和，最终将它们加起来。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;

// 定义二叉树节点结构体
struct TreeNode {
    int val;  // 节点的值
    TreeNode* left;  // 左子树
    TreeNode* right;  // 右子树
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  // 构造函数
};

// 递归函数：计算二叉树所有节点的和
int sumOfTree(TreeNode* root) {
    if (root == nullptr) {
        return 0;  // 如果节点为空，返回0
    }
    // 当前节点的值 + 左子树和 + 右子树和
    return root->val + sumOfTree(root->left) + sumOfTree(root->right);
}

// 示例：创建一个二叉树并计算节点和
int main() {
    // 创建二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    
    // 计算并输出二叉树的节点和值
    cout << "The sum of all nodes is: " << sumOfTree(root) << endl;

    return 0;
}

解释：

  1. TreeNode 结构体：定义了一个表示树节点的结构体，其中包含节点的值和指向左右子树的指针。
  2. sumOfTree 函数：这个函数是递归的，接收一个树节点 root 作为输入。如果节点为空 (nullptr)，返回 0；否则，返回当前节点的值加上左子树和右子树的值。
  3. 主函数：在 main() 函数中，创建了一个简单的二叉树并调用 sumOfTree() 函数来计算节点的和值。

运行示例：

假设树结构如下：

1
2
3
4
5
     1
   /   \
  2     3
 / \   / \
4   5 6   7

输出：

1
The sum of all nodes is: 28

时间复杂度：

  • 时间复杂度：O(n)，其中 n 是树的节点数。每个节点会被访问一次。
  • 空间复杂度：O(h)，其中 h 是树的高度。递归调用栈的最大深度是树的高度。

栈的运用

问题 (a)：

给定一个字符串，判断其中的括号是否是平衡的且正确嵌套的。如果括号正确嵌套，则返回 true，否则返回 false。使用栈来跟踪已看到的左括号的数量。提示：在扫描合法的字符串时，左括号的数量始终不小于右括号的数量。

解答 (a)：

我们可以使用栈来跟踪左括号的数量。扫描字符串时，遇到左括号时将其推入栈中，遇到右括号时检查栈是否为空。如果栈为空，则表示有多余的右括号。如果栈最终非空，则表示有多余的左括号。

算法步骤：

  1. 初始化一个空栈。
  2. 从左到右扫描字符串：
    • 如果遇到左括号 '('，将其压入栈中。
    • 如果遇到右括号 ')'，检查栈是否为空：
      • 如果栈为空，说明右括号没有匹配的左括号，返回 false。
      • 如果栈非空，弹出栈顶元素，表示匹配了一个左括号。
  3. 如果扫描完成后栈为空，返回 true，否则返回 false。

代码 (a)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <stack>
using namespace std;

bool areParenthesesBalanced(const string& str) {
    stack<char> s;  // 用栈来存储左括号

    for (char ch : str) {
        if (ch == '(') {
            s.push(ch);  // 遇到左括号，压入栈
        } else if (ch == ')') {
            if (s.empty()) {
                return false;  // 遇到右括号，但栈为空，表示多余的右括号
            }
            s.pop();  // 匹配到左括号，弹出栈顶元素
        }
    }

    return s.empty();  // 如果栈为空，表示括号匹配成功
}

int main() {
    string str = "((())())()";
    if (areParenthesesBalanced(str)) {
        cout << "Parentheses are balanced." << endl;
    } else {
        cout << "Parentheses are not balanced." << endl;
    }
    return 0;
}

解释：

  • 栈操作：使用栈来存储每个左括号的位置，遇到右括号时判断栈是否为空，如果为空则表示不平衡，否则弹出栈顶元素。
  • 时间复杂度：O(n)，其中 n 是字符串的长度。我们只需扫描一遍字符串。
  • 空间复杂度：O(n)，栈最多需要存储所有左括号的位置。

问题 (b)：

给定一个字符串，返回第一个不匹配的括号的位置（如果存在），否则返回 -1。如果字符串中有过多的右括号，返回第一个多余右括号的位置；如果有过多的左括号，返回第一个多余左括号的位置。

解答 (b)：

我们可以使用栈来存储左括号的位置，并在扫描过程中跟踪不匹配的括号。当遇到右括号时，如果栈为空，表示多余的右括号；如果扫描结束时栈非空，表示有多余的左括号。

算法步骤：

  1. 初始化一个空栈。
  2. 从左到右扫描字符串：
    • 如果遇到左括号 '('，将其位置压入栈中。
    • 如果遇到右括号 ')'：
      • 如果栈为空，返回当前位置，表示发现多余的右括号。
      • 如果栈非空，弹出栈顶元素，表示匹配到左括号。
  3. 扫描完成后，如果栈非空，返回栈顶元素的位置，表示多余的左括号；如果栈为空，则返回 -1，表示括号匹配成功。

代码 (b)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <stack>
using namespace std;

int firstUnbalancedParenthesis(const string& str) {
    stack<int> s;  // 用栈来存储左括号的位置

    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            s.push(i);  // 遇到左括号，压入栈
        } else if (str[i] == ')') {
            if (s.empty()) {
                return i;  // 遇到右括号，但栈为空，表示多余的右括号
            }
            s.pop();  // 匹配到左括号，弹出栈顶元素
        }
    }

    if (!s.empty()) {
        return s.top();  // 栈非空，表示有多余的左括号，返回第一个多余左括号的位置
    }

    return -1;  // 如果没有多余括号，表示括号匹配成功
}

int main() {
    string str = "())(";
    int result = firstUnbalancedParenthesis(str);
    if (result == -1) {
        cout << "Parentheses are balanced." << endl;
    } else {
        cout << "First unbalanced parenthesis is at position: " << result << endl;
    }
    return 0;
}

解释：

  • 栈操作：我们使用栈存储左括号的位置。当遇到右括号时，检查栈是否为空。如果为空，则表示多余的右括号，返回其位置；如果栈非空，则弹出栈顶元素。
  • 返回值：
    • 如果发现多余的右括号，返回其位置。
    • 如果扫描完成后栈非空，返回栈顶元素的位置，表示多余的左括号。
    • 如果括号匹配成功，返回 -1。

时间复杂度：

  • 时间复杂度：O(n)，其中 n 是字符串的长度。我们只需扫描一遍字符串。
  • 空间复杂度：O(n)，栈最多存储所有左括号的位置。

示例：

对于字符串 ())(，程序将返回位置 2，因为第一个多余的右括号出现在位置 2。