二叉树的内存池

以下摘自算法书：

内存池（memory pool），用来防止内存溢出的一个工具，具体来说就是维护一个空闲列表（free list），初始时把上述node数组中所有元素的指针放到该列表中，如下所示：

queue<Node*> freenodes;
Node node[maxn];
void init{
    for(int i = 0; i < maxn; i++)
        freenodes.push(&node[i]);//初始化内存池
}
Node* newnode(){
    Node * u = freenodes.front();
    u->left = u->right = NULL; u->have_value = false;//重新初始化该结点
    freenodes.pop();
    return u;
}
void deletenode(Node * u){
    freenodes.push(u);
}

其中，Node结构的定义可以参考我上一篇博客：

Trees on the level（UVA 122）-CSDN博客

提示：可以用静态数组配合空闲列表来实现一个简单的内存池。虽然在大多数算法竞赛题目中用不上，但是内存池技术在高水平竞赛及工程实践中都极为重要。

当然你也可以动态分配内存，只要用上new和delete就行了（记得用delete，要不然有可能会内存溢出），C的话是用malloc函数。上述方法是用数组来实现二叉树的，内存池是用了静态化动态的思想，使不用的结点的内存释放更加方便。而动态分配内存是用”指针+结构体“来实现二叉树的