Рекурсивная функция двоичного дерева - PullRequest
Новая
       11

Рекурсивная функция двоичного дерева

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

Я пытаюсь вставить элементы из моего массива в мое дерево. Моя функция работает нормально и создает узлы вплоть до конечного узла с левой стороны моего дерева. Проблема в том, что когда он должен возвращаться рекурсивно при обнаружении листового узла на более высокий уровень, он просто перестает строить дерево полностью. Вот код: 

void WLD::treeInsert(BSP_Node *tree_root, int node_number)

{

if ( tree_root == NULL ) 
    {
        tree_root = new BSP_Node();

        tree_root->node_number = node_number;
        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; //because the array starts at index 0
        tree_root->right = bsp_array[node_number].right; //because the array starts at index 0
        tree_root->left_node = NULL;
        tree_root->right_node = NULL;

        errorLog.OutputSuccess("Inserting new node: %i", node_number);
        errorLog.OutputSuccess("Left node index: %i", bsp_array[node_number].left);
        errorLog.OutputSuccess("Right node index: %i", bsp_array[node_number].right);

        node_number++;

        // Check for leaf nodes
        if(tree_root->region != 0)
        {
            errorLog.OutputSuccess("This is a leaf node! Returning!");
            return;
        }
    }


    if ( tree_root->left > 0) 
    {
        //tree_root->left_node = new BSP_Node();
        errorLog.OutputSuccess("Left node not NULL, inserting it!");
        treeInsert( tree_root->left_node, tree_root->left );
    }
    else if (tree_root->right > 0)
    {
        //tree_root->right_node = new BSP_Node();
        errorLog.OutputSuccess("Right node not NULL, inserting it!");
        treeInsert( tree_root->right_node = NULL, tree_root->right );
    }

}

Как вы можете видеть, когда он обнаруживает конечный узел, он должен вернуться к вызывающей функции (эта функция, но на уровне ближе к узлу. У кого-нибудь есть предложения?

1 Ответ

2 голосов
/ 31 мая 2011 
if ( tree_root->left > 0)  {
   // implementation
}
else if (tree_root->right > 0) {
   // implementation
}

Разве это не два отдельных оператора if, а не if / else?В противном случае он делает только одну или другую сторону, но не обе.

...