C ++ проблема с функцией, чтобы проверить, заполнено ли дерево - PullRequest
Новая
       71

C ++ проблема с функцией, чтобы проверить, заполнено ли дерево

0 голосов
/ 27 апреля 2020

Итак, у меня есть функция, чтобы проверить, является ли дерево полным (если у каждого узла есть только 0 или 2 дочерних элемента). Любая другая функция работает, и проблема в этом (вторая просто вызывает помощник). Сначала пользователь вводит строку, и она сортируется по порядку (работает). char в позиции: len / 2 превращается в root и вызывает рекурсивно, чтобы сделать остальную часть дерева (работает попытка отображения). При запуске кода независимо от того, какой ввод строки я предоставляю, я получаю, что Дерево не заполнено. Любая помощь приветствуется. дополнительное примечание: если закомментированные строки не закомментированы, проблема решается, и я постоянно получаю дерево заполнено для каждого ввода. При необходимости может предоставить код для других функций.

входные данные, которые я пробовал: rats -> arst (root node r) не должен быть полным victorn -> cinortv (root node o) должен быть заполнен 

bool isFullTreehelper(TreeNode* R00t) 
{

    //if empty tree then true
    if (R00t == NULL)
        return true;

    //leaf node
    if (R00t->left == NULL && R00t->right == NULL)
        return true;

    //if (R00t->left != NULL && R00t->right != NULL)
        //return true;


    if ((R00t->left != NULL) && (R00t->right != NULL))
    return (isFullTreehelper(R00t->left) && isFullTreehelper(R00t->right));

    return false;

}


//update: addditonal code (currently checking to see if this creates a balanced tree)

TreeNode* sortedArrayToBST_helper(ItemType items[], int start, int end)
{
    // continue while this branch has values to process
    if (start > end)
        return NULL;
        // Get the middle element and make it root
    int mid = start + (end - start) / 2;
    TreeNode* head = new TreeNode(items[mid]);
    // Recursively construct the left subtree
    // and make it left child of root
    head->left = sortedArrayToBST_helper(items, start, mid - 1);
    // Recursively construct the right subtree
    // and make it right child of root
    head->right = sortedArrayToBST_helper(items, mid + 1, end);
    return head;
}

void TreeType::sortedArrayToBST(ItemType items[], int l)
{
    root = sortedArrayToBST_helper(items, 0, l);

    //debug lines
    //cout << root->info << endl;
    //cout << root->left->info << endl;
    //cout << root->right->info << endl;
    //cout << root->left->left->info << endl;
    //cout << root->left->right->info << endl;
    //cout << root->right->left->info << endl;
    //cout << root->right->right->info << endl;

}

1 Ответ

0 голосов
/ 27 апреля 2020

"@ VictorNath Какое значение вы передаете как l в функцию sortedArrayToBST? Кажется, в конце вспомогательной функции находится последний элемент (а не один после последнего). Если это так, вы должны передать элементы размером минус один. во втором аргументе для sortedArrayToBST. " - Михаил

в итоговом решении должен был вычесть 1 из длины при вызове sortedArrayBST

...