二叉树的实验结果与分析

为了进行二叉树的实验，首先需要设计二叉树的数据结构以及相应的操作函数。常见的二叉树操作包括插入节点、删除节点、查找节点、遍历二叉树等。在实验中，我们可以采用随机生成一定数量的节点，然后进行插入、删除、查找等操作，最后统计运行时间、空间占用等指标来评估算法的性能。

下面是一个简单的二叉树数据结构的定义：

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

接下来，我们可以实现二叉树的插入、删除、查找等操作。例如，二叉树的插入操作可以采用递归实现，代码如下：

void insert(TreeNode* &root, int val) {
    if (root == nullptr) {
        root = new TreeNode(val);
        return;
    }
    if (val < root->val) {
        insert(root->left, val);
    } else {
        insert(root->right, val);
    }
}

二叉树的删除操作比较复杂，需要分别考虑删除叶子节点、只有左子树或右子树的节点以及有两个子节点的节点。这里只给出删除有两个子节点的节点的代码：

void deleteNode(TreeNode* &root, int key) {
    if (root == nullptr) return;
    if (key < root->val) {
        deleteNode(root->left, key);
    } else if (key > root->val) {
        deleteNode(root->right, key);
    } else {
        if (root->left == nullptr) {
            root = root->right;
        } else if (root->right == nullptr) {
            root = root->left;
        } else {
            TreeNode* p = root->right;
            while (p->left) p = p->left;
            root->val = p->val;
            deleteNode(root->right, p->val);
        }
    }
}

在实验中，我们可以随机生成一定数量的节点，并分别测试插入、删除、查找等操作。例如，插入10000个随机数，并统计运行时间和空间占用：

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

int main() {
    srand(time(nullptr));
    int n = 10000;
    TreeNode* root = nullptr;
    clock_t start = clock();
    for (int i = 0; i < n; i++) {
        insert(root, rand());
    }
    clock_t end = clock();
    double t = (double)(end - start) / CLOCKS_PER_SEC;
    cout << "Insert " << n << " nodes: " << t << " s" << endl;
    cout << "Memory usage: " << sizeof(TreeNode) * n / 1024.0 / 1024.0 << " MB" << endl;
    return 0;
}

类似的，我们可以进行删除、查找等操作，并统计相应的运行时间和空间占用。最后，我们可以根据实验结果进行分析和总结，评估算法的优劣和适用场景。