algorithm - null 是二叉树吗？

Question

所以我看到了几个例子比如

How to validate a Binary Search Tree?

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

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

Answer 1

在纯计算机科学中，null 是一个有效的二叉树。它被称为空二叉树。就像空集仍然是有效集一样。此外，只有一个根节点且没有子节点的二叉树也是有效的(但不是空的)。参见 this Stack Overflow answer获取更多信息。

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

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

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

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