Функция не возвращает значение по умолчанию

Question

Вот мой код:

bool BinarySearchTree::CheckIfTreeIsBinary(){
    bool isBinary=true;
    isBinary=CheckIfTreeIsBinaryPrivate(root); // So if my tree is binary, this function does not return anything
                                               // and isBinary should remain true, but it is false.
    return isBinary;
}

bool BinarySearchTree::CheckIfTreeIsBinaryPrivate(nodePtr Ptr){ 
    if(Ptr->left!=NULL){
        CheckIfTreeIsBinaryPrivate(Ptr->left);
    }

    if(Ptr->left!=NULL){
        if(Ptr->data<Ptr->left->data)
            return false; // possibility 1 to return false
    }

    if(Ptr->right!=NULL){
        if(Ptr->data>Ptr->right->data)
            return false; // possibility 2 to return false
    }

    if(Ptr->right!=NULL){
        CheckIfTreeIsBinaryPrivate(Ptr->right);
    }
}

В моей функции CheckIfTreeIsBinary я установил для логического isBinary значение true для значения по умолчанию.После этого isBinary назначается функции CheckIfTreeIsBinaryPrivate, которая ничего не будет возвращать, если дерево двоичное.
Проблема в том, что функция CheckIfTreeIsBinaryPrivate ничего не возвращает, если дерево двоичное, но в конце концов isBinary имеет значение false.

Answer 1

Я думаю, я вижу, где твое недоразумение;вы ожидаете, что isBinary будет обновлено, только если CheckIfTreeIsBinaryPrivate вернет значение.

Это не так, как работает - функция с возвращаемым типом, отличным от void, всегда должна возвращать что-то .
Если функция явно ничего не возвращает - например,, достигнув конца функции - программа имеет неопределенное поведение.

Нет способа определить, возвратила ли функция что-либо или нет, и вы должны возвращать что-то на каждом пути через функцию.

Вы можете сделать это с одним большим выражением,

bool BinarySearchTree::isBST(nodePtr Ptr){
    return Ptr == nullptr
        || (   (Ptr->left == nullptr || (Ptr->left->data < Ptr->data && isBST(Ptr->left)))
            && (Ptr->right == nullptr || (Ptr->right->data > Ptr->data && isBST(Ptr->right))));
}

или по частям:

bool BinarySearchTree::isBST(nodePtr Ptr){
    // An empty tree is a BST.
    if (Ptr == nullptr)
        return true;
    // If the left subtree is not a BST, neither is the entire tree.
    else if (Ptr->left != nullptr && (Ptr->left->data > Ptr->data || !isBST(Ptr->left)))
        return false;
    // If the right subtree is not a BST, neither is the entire tree.
    else if (Ptr->right != nullptr && (Ptr->right->data < Ptr->data || !isBST(Ptr->right)))
        return false;
    // All tests passed.
    else
        return true;
}

Answer 2

Ваша рекурсивная логика неверна.Все пути в функции должны возвращать значение, и вы всегда должны проверять возвращаемое значение рекурсивных вызовов на CheckIfTreeIsBinaryPrivate.Там нет понятия «значение остается неизменным».Вот что я думаю, что вы пытаетесь достичь, но это довольно сложно.

bool BinarySearchTree::CheckIfTreeIsBinaryPrivate(nodePtr Ptr) { 
    return
        // check the left sub tree is ok
        (Ptr->left == NULL ||                 // NULL is ok OR
            (Ptr->data >= Ptr->left->data &&  // data >= left->data && left is ok
                 CheckIfTreeIsBinaryPrivate(Ptr->left))) &&
        // and check the right sub tree is ok
        (Ptr->right == NULL ||                // NULL is ok OR
            (Ptr->data <= Ptr->right->data && // data <= right->data && right is ok
                 CheckIfTreeIsBinaryPrivate(Ptr->right)));
}

Answer 3

Проблема в том, что CheckIfTreeIsBinaryPrivate не не имеет явное значение return во всех путях управления программой.

Это означает, что поведение вашей программы не определено.

Ваш компилятор предупредит вас об этом, и ваша задача - прислушаться к этим предупреждениям.

Answer 4

Добавьте еще одно базовое условие в CheckIfTreeIsBinaryPrivate(), чтобы установить true, потому что как только вы назначите isBinary на CheckIfTreeIsBinaryPrivate(), он по умолчанию установит значение false, и вам потребуется возвращаемое значение, чтобы получить значение true.