Проблема с функцией, чтобы проверить, является ли дерево BST - PullRequest
Новая
       60

Проблема с функцией, чтобы проверить, является ли дерево BST

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

Итак, у меня есть функция, чтобы проверить, является ли дерево bst (если каждый узел имеет только меньшие значения слева и большие значения справа). Любая другая функция работает, и проблема в этом (вторая просто вызывает помощник). Я думаю, что проблема как-то связана с рекурсивным вызовом root с левым нажатием на null, но я не уверен и даже если не уверен, как исправить. Можно добавить больше кода по мере необходимости. Любая помощь приветствуется.

Ошибка Visual Studio, которую я получаю: R00t -> left был nullptr другой компилятор: ядро ​​ошибки сегментации сброшено. 

bool isBSThelper(TreeNode* R00t) 
{



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

        return isBSThelper(R00t->left) && isBSThelper(R00t->right);



}

bool TreeType::isBST() const
{
    return isBSThelper(root);
}

1 Ответ

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

Согласно вашему комментарию 

even with if (R00t->left != NULL || R00t->right != NULL) error persists

проблема будет сохраняться. Позвольте мне переписать и повторить оттуда (так как я не могу комментировать, чтобы попросить разъяснения - новый пользователь). Если бы ваш код был похож на 

bool isBSThelper(TreeNode* R00t) {
    if ( R00t == NULL )
        return true;
    if ( R00t->left != NULL || R00t->right != NULL ) {
        if ( R00t->info < R00t->left->info )
            return false;
        if ( R00t->info < R00t->right->info )
            return false;
    }

    return isBSThelper(R00t->left) && isBSThelper(R00t->right);
}

, то вы потенциально могли бы столкнуться с той же проблемой, поскольку выражение 

if (R00t->left != NULL || R00t->right != NULL) {

все равно получило бы это выражение со значениями 

R00t->left != NULL

, но 

R00t->right == NULL

оцените как истинное.

Одним из решений может быть

  1. Чтобы убедиться, что R00T-> left и R00t-> right либо действительны (указывает на узел) или NULL (предпочтительно nullptr, если вы используете C ++)
  2. И такой код: 
bool isBSThelper( TreeNode* R00t ) {
    if ( R00t == NULL )
        return true;
    if ( R00t->left != NULL && R00t->info > R00t->left->info )
        return false;
    if ( R00t->right!= NULL && R00t->info > R00t->right->info )
        return false;

    return isBSThelper( R00t->left ) && isBSThelper( R00t->right );
}

И проблемы больше не будет. (1) является критическим.

Дополнительное примечание: Ваш код не проверяет 

if (R00t->left != NULL && R00t->right!= NULL && R00t->left->info < R00t->right->info)
        return false;

, которое является другим свойством дерева двоичного поиска (или, очевидно, использует «>» вместо «< "здесь, как вы считаете нужным).

...