Функция построения дерева из предварительно рассчитанного дерева - PullRequest
Новая
       75

Функция построения дерева из предварительно рассчитанного дерева

2 голосов
/ 31 мая 2011

Я строю двоичное дерево.Двоичное дерево предварительно встроено в файл, и мне нужно его построить.Из-за того, как он структурирован, я прочитал дерево в массив.Каждый узел дерева выглядит примерно так: 

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до сбоя программы.

Может кто-нибудь помочь мне с этим?

1 Ответ

0 голосов
/ 31 мая 2011 
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], чтобы рекурсивный вызовto treeInsert создает следующий узел.

...