所以我看到了几个例子比如
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
。这对我来说没有意义。
最佳答案
在纯计算机科学中,null 是一个有效的二叉树。它被称为空二叉树。就像空集仍然是有效集一样。此外,只有一个根节点且没有子节点的二叉树也是有效的(但不是空的)。参见 this Stack Overflow answer获取更多信息。
在实际实现中,有两种方法可以解决。
假设一棵有效的二叉树必须至少有一个节点并且不允许有空树。每个节点不必有子节点。此树上的所有递归方法都不会下降到 null 级别。相反,当他们看到节点的左 child 或右 child 为空时,他们就会停止。只要您不将 null 传递到任何需要树的地方,此实现就有效。
假设 null 是一个有效的二叉树(形式上,只是空树)。在此实现中,您首先检查指针是否为空,然后再对其进行任何操作(如检查左/右子节点等)。此实现适用于任何指向树的指针。您可以自由地将空指针传递给需要树的方法。
两种方式都有效。第二种实现具有灵 active 的优点。您可以将 null 传递给任何需要树的东西,它不会引发异常。第一个实现的优点是不会浪费时间下降到 null 的“子节点”,并且您不必在节点上运行的每个函数/方法的开头使用 null 检查。您只需要对 child 进行空检查即可。
关于algorithm - null 是二叉树吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18937604/