程序填空不会做。。求助各位大佬。

Question

第一题

第二题

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

#include <iostream>
#include <string>

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int d) : data(d), left(nullptr), right(nullptr) {}
};

// Function to check the balance factor of a node.
int getBalance(Node* node) {
    return node ? abs(getBalance(node->left) - getBalance(node->right)) : 0;
}

// Function to perform rotations on a node and update its height accordingly.
Node* rotateRight(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    // Perform rotation
    x->right = y;
    y->left = T2;

    // Update heights
    y->h = max(height(y->left), height(y->right)) + 1;
    x->h = max(height(x->left), height(x->right)) + 1;

    // Return new root or updated node depending on the type of rotation performed
    return x;
}

Node* rotateLeft(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;

    // Update heights
    x->h = max(height(x->left), height(x->right)) + 1;
    y->h = max(height(y->left), height(y->right)) + 1;

    // Return new root or updated node depending on the type of rotation performed
    return y;
}

// Function to perform RR rotation on a tree and update its balance factor.
Node* RRRotation(Node* T) {
    // Check if the tree is empty or has only one node
    if (!T || !T->left) return T;

    // Find the inorder successor for R-R rotation
    Node* R = T->right;
    Node* S = R->left;

    // Perform rotation
    R->left = rotateRight(R->left);
    T->right = rotateLeft(T->right);

    // Update heights
    T->h = max(height(T->left), height(T->right)) + 1;
    R->h = max(height(R->left), height(R->right)) + 1;

    // Return the new root or updated node depending on the type of rotation performed
    return R;
}

这段代码实现了右旋操作的逻辑，并在旋转后更新树的高度。请注意，这个代码没有包含所有可能的边缘情况和错误处理。在实际应用中，你可能需要根据具体情况添加适当的异常处理和边界条件检查。