1

所以我看过一些例子，比如

如何验证二叉搜索树？

http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/

它们返回 1，或者 true 是一棵树为空。稍微扩展问题-假设我必须找到 TreeSmall 是否是 TreeBig 的子树，而我的 TreeSmall 是null，返回值应该是checkSubtree(smallTree)true 还是 false ？Atrue表示 TreeSmall 是一个tree值为 的null。这对我来说没有意义。

4

3 回答 3

2

在纯计算机科学中，null 是一个有效的二叉树。它被称为空二叉树。就像空集仍然是有效集一样。此外，只有一个根节点且没有子节点的二叉树也是有效的（但不是空的）。有关更多信息，请参阅此 Stack Overflow 答案。

在实际实现中，有两种方法可以解决。

  1. 假设一棵有效的二叉树必须至少有一个节点并且不允许有空树。每个节点不必有子节点。这棵树上的所有递归方法都不会下降到 null 的级别。相反，当他们看到节点的左孩子或右孩子为空时，它们就会停止。只要您不将 null 传递到任何需要树的地方，此实现就可以工作。

  2. 假设 null 是一个有效的二叉树（正式地，只是空树）。在此实现中，您首先检查指针是否为空，然后再对其进行任何操作（例如检查左/右子节点等）。此实现适用于任何指向树的指针。您可以自由地将空指针传递给期望树的方法。

两种方式都有效。第二种实现具有灵活性的优点。您可以将 null 传递给任何需要树的东西，并且它不会引发异常。第一个实现的优点是不会浪费时间下降到为空的“子节点”，并且您不必在每个在节点上运行的函数/方法的开头使用空检查。你只需要对孩子做空检查。

于 2013-09-21T21:31:07.187 回答
0

这取决于应用程序并且是定义问题。

编辑：

例如，维基百科“定义”了一个 BST，如下所示：

在计算机科学中，二叉搜索树 (BST)，有时也称为有序或排序二叉树，是一种基于节点的二叉树数据结构，具有以下属性：

  • 节点的左子树仅包含键小于节点键的节点。
  • 节点的右子树只包含键大于节点键的节点。
  • 左右子树也必须是二叉搜索树。
  • 不能有重复的节点

让我们测试一下null：

  • 左子树不存在，因此没有违反此规则的节点 -> 检查
  • 类似于第一个 -> 检查
  • 如果所有这些测试都通过了，那么这也通过了，因为两个子树都是空的 -> 检查
  • 当然没有重复->检查

所以根据这个定义null是一个有效的 BST。您也可以通过要求“必须有一个根节点”来反转这一点。这不会影响 BST 的任何实际属性，但可能会影响显式应用程序。

于 2013-09-21T21:12:44.060 回答
0

Ex falso sequitur quodlibet - 因为“null”根本不是什么，它可以被解释为任何东西。这真的是一个设计问题。有些人可能会声称在这种情况下 checkSubTree() 应该抛出类似 IllegalArgumentException 的东西。另一种方法是引入一种特殊的类型化对象或实例，它表示一棵空树（参见NullObjectPattern）。这样的空对象将是所有帐户的树，例如EmptyTree instanceof Tree，虽然null instanceof Tree总是错误的。

于 2013-09-21T21:31:29.043 回答