二叉查找树BinSearchTree——实验验证节点数与树高呈对数关系

整体思路

首先创建写入文件流用于储存节点数和其对应的树高，便于后期分析。在这里模拟了1个节点到800个节点的二叉树，每种情况都随机生成了200种情况进行计算平均树高。为了加大随机性，将随机数的最大值提高到了10000。
生成的数据通过 Excel 数据分析功能进行对数函数拟合，通过拟合优度R²得出二叉树的树高是否与节点数成对数关系。

部分代码

int main()
{
    ofstream out;           //写入文件流；
    out.open("E:\\类库与数据结构\\data.txt");
    double Num = 200;   //每个节点的模拟量
    int nodeNum = 800;  //节点个数模拟量   
    int MAX = 10000;    //随机最大值
    srand((unsigned)time(0));

    //遍历有1个节点到有800个节点的情况
    for (int k = 1; k <= nodeNum; k++) {
        double averageHeight = 0;
        //每种节点情况随机生成200个模拟量，求出该节点的平均树高
        for (int j = 1; j <= Num; j++) {
            BinSearchTree<int> mybst;
            int item;
            for (int i = 0; i < k; i++) {
                item = rand() % MAX;
                mybst.insert(item);
            }
            averageHeight += mybst.height();    //平均树高  
        }
        cout << k << "\t" << averageHeight / Num << endl;
        //将平均树高写入文件，便于后期分析
        out << k<<"\t"<<averageHeight / Num << endl;
    }
    out.close();
    cout << "FINISH!!" << endl;
}

实验总结

不仅要对节点数进行模拟计算平均数高，还要通过对各种节点数做分析找出他们之间的函数关系。
对数据的处理可以将树高取对数后与节点数线性拟合，但是这里我用了一个比较“懒”的方法，通过Excel中对数拟合的功能直接拟合出对数关系式和拟合优度R²。

实验结果

二叉树树高与节点数的关系分析