我正在构建一个二叉树。二叉树是预先构建在一个文件中的,我需要构建它。由于它的结构方式,我将树读入数组。每个树节点看起来像这样。
struct Tree_Node
{
float normalX;
float normalY;
float normalZ;
float splitdistance;
long region;
long left, right; //array index
Tree_Node* left_node; // pointer to left node
Tree_Node* right_node; // pointer to right node
} typedef Tree_Node;
我已经尝试了多种方法来编写一些代码来构建这棵树。让我给您一些伪代码,以便您了解我要做什么。
- 读入头节点。节点是数组中的第一个。
- 如果节点有左右数组索引,则创建新节点并 插入数组中的信息 索引到该树节点。
- 如果节点没有左右索引,则为叶节点。
这是我的构建函数:
void WLD::treeInsert(BSP_Node *tree_root, int node_number)
{
/// Add the item to the binary sort tree to which the parameter
// "root" refers. Note that root is passed by reference since
// its value can change in the case where the tree is empty.
if ( tree_root == NULL )
{
// The tree is empty. Set root to point to a new node containing
// the new item. This becomes the only node in the tree.
tree_root = new BSP_Node();
tree_root->normalX = bsp_array[node_number].normal[0];
tree_root->normalY = bsp_array[node_number].normal[1];
tree_root->normalZ = bsp_array[node_number].normal[2];
tree_root->splitdistance = bsp_array[node_number].splitdistance;;
tree_root->region = bsp_array[node_number].region;
tree_root->left = bsp_array[node_number].left;
tree_root->right = bsp_array[node_number].right;
tree_root->left_node[node_number];
tree_root->right_node[node_number];
errorLog.OutputSuccess("Inserting new root node: %i", node_number);
// NOTE: The left and right subtrees of root
// are automatically set to NULL by the constructor.
// This is important...
}
if ( tree_root->left != 0 )
{
errorLog.OutputSuccess("Inserting left node number: %i!", tree_root->left);
treeInsert( tree_root->left_node, tree_root->left );
}
else if ( tree_root->right != 0 )
{
errorLog.OutputSuccess("Inserting right node: %i!", tree_root->right);
treeInsert( tree_root->right_node, tree_root->right );
}
else if ( tree_root->right == 0 && tree_root->left == 0)
{
errorLog.OutputSuccess("Reached a leaf node!");
return;
}
else
{
errorLog.OutputError("Unknown BSP tree error!");
}
}
我的调试显示该函数会尝试插入节点 2,直到程序崩溃。
有人可以帮我解决这个问题吗?
最佳答案
tree_root->left_node[node_number];
我没有看到任何初始化这个数组的代码,所以这将引用一些无效的东西。
然后当你来到下一个函数的时候
treeInsert( tree_root->left_node, tree_root->left );
treeInsert
将使用无效指针调用,因为 left_node
不会去任何地方。
我想您需要像 tree_root->left_node = NULL
而不是 tree_root->left_node[node_number]
这样递归调用 treeInsert 创建下一个节点。
关于c++ - 预先计算的树的树构建函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6184270/