函数没有 return 默认值

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，如果树是二叉树，它不会 return 任何东西。
问题是如果树是二叉树，函数 CheckIfTreeIsBinaryPrivate 不会 return 任何东西，但最终 isBinary 是假的。

Answer 1

在CheckIfTreeIsBinaryPrivate()中添加一个基本条件以设置为真，因为一旦你将 isBinary 分配给 CheckIfTreeIsBinaryPrivate() 它将默认设置为 false，你需要一个 return 值才能得到 true。

Answer 2

你的递归逻辑不正确。函数中的所有路径都应该 return 一个值，并且您应该始终检查对 CheckIfTreeIsBinaryPrivate 的递归调用的 return 值。没有'a value remaining the same'的概念。这是我认为您正在努力实现的目标，但它非常复杂。

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

我想我明白你的误解在哪里了；您期望 isBinary 仅在 CheckIfTreeIsBinaryPrivate return 是一个值时更新。

它不是这样工作的 - 具有非 void return 类型的函数必须始终 return something.
如果函数没有明确地 return 任何东西——例如，通过到达函数的末尾——程序有未定义的行为。

您无法确定某个函数是否 return 执行了任何操作，您必须 return 在通过该函数的每条路径上执行某些操作。

你可以用一个大表达式来做到这一点，

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;
}

函数没有 return 默认值

Function doesn't return default value

c++

recursion

binary-tree