使用数组实现四叉树

Question

我正在尝试使用 Barnes-Hut 树算法编写用于模拟 n 体问题的代码。我计划在未来使用 CUDA，因此希望我的四叉树数据结构不由堆对象组成。

作者从 Martin Burtscher 和 Keshav Pingali 的论文“基于树的 Barnes Hut n-Body 算法的高效 CUDA 实现”（抱歉找不到链接）中指出：

动态数据结构如树通常由堆对象构建，其中每个堆对象包含多个字段，例如子指针和数据字段，并且是动态分配的。因为堆对象的动态分配和访问往往很慢，所以我们使用基于数组的数据结构。如果数组元素是具有多个字段的对象，则无法合并对数组的访问，因此我们使用多个对齐的标量数组，每个字段一个，如图 6.6 所示。因此，我们的代码使用数组索引而不是指向树节点的指针。

我了解对齐标量数组的部分（即并行计算中的 SOA 与 AOS 习惯用法），但不幸的是，作者没有解释如何使用数组构造四叉树。

我的问题是如何使用数组实现四叉树数据结构（使用插入空间点的方法）？我知道如何使用节点结构和子节点指针等以传统方式实现四叉树。有人可以提供详细说明如何使用数组执行此操作的参考。甚至关于如何使用数组实现二叉树（或任何树）的信息在这里也可能有用。

Answer 1

使用数组实现二叉树非常简单，首先我们将从1开始对数组进行索引，即根节点为1，然后

左孩子将是：leftChildIndex = 2 * parentIndex;

右孩子将位于：rightChildIndex = 2 * parentIndex + 1;

现在如果想找到当前节点的父节点：parentIndex = currIndex/2;

我编写了一个 C++ 代码来执行树的前序遍历：

#include<iostream>

using namespace std;

int binaryTree[20], lengthOfTree;
int leftChild(int idx){ return 2*idx; }
int rightChild(int idx){ return 2*idx+1; }
int parentIndex(int idx){ return idx/2; }

void traverseTree(int idx){
    if(idx >= lengthOfTree) return;
    cout << binaryTree[idx] << " ";
    traverseTree(leftChild(idx));
    traverseTree(rightChild(idx));
}

int main(){

    lengthOfTree = 15;
    for(int i = 1;i <= lengthOfTree;i++){
        cin >> binaryTree[i];  
    }
    traverseTree(1);
    cout << endl;

return 0;
}

链接到 Ideone 上的解决方案：http://ideone.com/ZpTJCa

----------------------------------------------------------------------------

索引四叉树可能会更复杂一些，所以我们可以做的就是再次从 1 开始索引树，对于每个节点，我们可以找到该节点的级别，例如 : the level of node 1 is 0, level of node 4 is 1, level of node 11 is 2。

用于查找级别的伪代码：O(log n)

int findLevel(int nodeNo){
    int level = 0;
    int currNode = 1;
    while(currNode < nodeNo){
        currNode = currNode + pow(4, level++);
    }
    return level;
}

类似地，可以使用上面的伪代码计算当前级别的最左边节点和当前级别的最右边节点，然后找到当前节点的 4 个子节点，我们可以这样做：

当前节点的第一个子节点：child1 = (rightmostNode - currentNode) + 4 * (currentNode - leftmostNode);

当前节点的第二个子节点：child2 = child1 + 1;

当前节点的第三个子节点：child3 = child2 + 1;

当前节点的第四个子节点：child4 = child3 + 1;

您还可以创建一个映射来查找父级。