已知一棵二叉排序树如下图所示，分别画出删除元素90和47后的二叉排序树。https://p.ananas.chaoxing.com/star3/origin/aed5473de7ddc1c282306bed919892f4.png

删除元素90后的二叉排序树如下图所示：https://p.ananas.chaoxing.com/star3/origin/2b6d4d8f4ecf6433d6da3d2e8af4f7be.png

删除元素47后的二叉排序树如下图所示：https://p.ananas.chaoxing.com/star3/origin/2f1d3d5f204a8b5302d5580d7e8c9d2e.png

相关问题

已知一棵二叉排序树，如何计算其ASL？用c++代码实现

计算二叉排序树的ASL，可以按照上面提到的公式进行计算。具体实现可以使用递归方式遍历整棵树，计算每个节点的深度和被查找到的概率，然后根据公式进行累加求和。以下是一个示例代码：

// 定义二叉树节点结构体
struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(NULL), right(NULL) {}
};

// 计算二叉排序树的ASL
double calculateASL(Node* root, int depth, int n) {
    if (root == NULL) {
        return 0;
    }
    double p = 1.0 / n;  // 计算概率
    int d = depth - 1;   // 计算深度
    double sum = p * d;
    sum += calculateASL(root->left, depth + 1, n);
    sum += calculateASL(root->right, depth + 1, n);
    return sum;
}

// 测试代码
int main() {
    // 构建一棵二叉排序树
    Node* root = new Node(4);
    root->left = new Node(2);
    root->left->left = new Node(1);
    root->left->right = new Node(3);
    root->right = new Node(6);
    root->right->left = new Node(5);
    root->right->right = new Node(7);

    // 计算ASL并输出结果
    int n = 7;  // 节点数
    double asl = calculateASL(root, 1, n);
    cout << "ASL = " << asl << endl;

    return 0;
}

在示例代码中，我们首先定义了一个二叉树节点的结构体，然后编写了一个递归函数calculateASL来计算二叉排序树的ASL。在测试代码中，我们构建了一棵二叉排序树，并计算了其ASL。

2.已知一棵二叉排序树的先序遍历序列为DBACGEF，它的后序遍历序列是什么？要求写出解题过程。

根据二叉排序树的性质，先序遍历的第一个元素是根节点，然后按照左子树小于根节点、右子树大于根节点的规则进行构建。因此，我们可以通过先序遍历序列来确定根节点及其左右子树的范围，然后递归地对左右子树进行相同的操作。

在本题中，先序遍历序列为DBACGEF，第一个元素是D，因此D为根节点。然后我们可以将序列分为D|BACGEF，其中D为根节点，BACGEF为其左子树和右子树的先序遍历序列。接下来，我们可以递归地对左右子树进行相同的操作，直到序列为空或只有一个元素。

对于左子树BACGEF，其最后一个元素F一定是其根节点，因此我们可以将其分为BA|CGEF，其中F为根节点，BA和CGEF为其左子树和右子树的先序遍历序列。同理，我们可以递归地对左右子树进行相同的操作，直到序列为空或只有一个元素。

最终，我们得到的后序遍历序列为ACBFGED。