时间戳

首页 > 解决方案 > 检查树是否为 BST 的功能问题

c++ - 检查树是否为 BST 的功能问题

问题描述

所以我有一个函数来检查一棵树是否是 bst（如果每个节点的左边只有较小的值，右边有较大的值）。其他所有功能都有效，问题出在这个功能上（第二个功能只是调用助手）。我认为这个问题与递归调用 root-left 命中 null 但我不确定，即使它不确定如何修复。可以根据需要添加更多代码。任何帮助表示赞赏。

我得到的视觉工作室错误是：R00t -> 左边是 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);
}

标签： c++recursionbinary-search-treenodes

解决方案

根据你的评论

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（如果使用 C++，最好为 nullptr）
  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;

这是二叉搜索树的另一个属性（或者显然在您认为合适的情况下使用“>”而不是“<”）。

推荐阅读