BST isBST() 解释

Question

所以我在这个网站上找到了这个 isBST() 函数：

static struct node *prev = NULL;

bool isBST(struct node* root)
{
    // traverse the tree in inorder fashion and keep track of prev node
    if (root)
    {
        if (!isBST(root->left))
          return false;

        // Allows only distinct valued nodes
        if (prev != NULL && root->data <= prev->data)
          return false;

        prev = root;

        return isBST(root->right);
    }

    return true;
}

我在跟踪发生的事情时遇到了一些麻烦。主要是

 if (!isBST(root->left))
          return false;

和

if (prev != NULL && root->data <= prev->data)
              return false;

出于某种原因，if (prev != NULL && root->data <= prev->data) 对我来说似乎是倒退的。我认为它应该是 if (prev != NULL && root->data >= prev->data) 因为如果 root->data 更大那么它就是错误的。我知道我们正在按顺序遍历树并检查它是否按顺序排列。然而，让我困惑的是每一行实际上在做什么。

有人可以详细说明一下这个函数是怎么回事吗？谢谢

Answer 1

首先，任何时候如果我们看到矛盾，我们都可以立即 return false - 将其视为短路。此时树的其余部分无关紧要。

这两个 isBST 调用是按顺序遍历的简单递归部分。

随着我们按顺序进行，值严格递增（无重复）。因此，如果我们看到不匹配，我们可以 return false，所以这是正确的条件：

root->data <= prev->data

我无法在评论中格式化示例，所以我在这里留下了一个显示@JerryCoffin 的解决方案将失败的地方：

Answer 2

好的，这里的基本思想是从树一直下降到最左边的节点开始。这是因为它在调用时所做的第一件事是检查 root 是否为空指针，如果不为空，则在左子树上递归调用自身。当它到达最左边的节点时，isBST(root->left) 传入一个空指针，因此它 return 为真。到目前为止，还不错。

然后它检查 prev 是否是一个空指针（在第一次下降到最左边的叶子时，它将是）。然后它将当前根存储到prev，并检查正确的子树。

在右子树中，它做同样的事情——下降到最左边的节点，returns true一次，然后回到最后一个"real"节点（即空指针以外的东西）。这就是它变得有趣的地方。它到达 if 语句，但这次是 prev != NULL，因此它检查当前节点中的值是否大于 prev 引用的节点中的值。

例如，让我们考虑这样一棵树：

        10
      /    \
     4      12
    / \    /  \
   3   5  11   14

事情变得有趣的第一个地方是当它return编辑向上到4 节点时。此时它将 prev 设置为指向 4 节点，然后从那里检查右后代 5 节点。要成为一棵有效的树，这两个必须按顺序排列，所以如果 root（当前的 5 节点）<= prev（当前的 4 节点）树将无效, 所以它会 return false.

完成后，它将 prev 设置为指向 5 节点，并检查其右子树（立即 returns true，因为它没有正确的后代）。

因为那没有改变 prev，它仍然指向 5 节点。所以现在我们 return 指向树的实际根，prev 指向 5 节点，root 指向 10 节点。同样，如果 root 指向一个 <= 到 prev 的值，我们将得到一个无效的树，所以如果发生这种情况，我们将 return false。

剩下的我就不说了——至此，我认为模式已经很明显了。特别是，每次查看 prev 处的值时，它都指向 "current" 根左侧的节点，因此它要求当前根大于 [=] 处的值13=].

不过我相信这可以清理（相当多）。我真的不喜欢在这里使用 static 等等。至少，这应该作为一个额外的参数传递，而不是使用静态变量。

BST isBST() 解释

BST isBST() explanation

c++

binary-search-tree