测试二进制树是否是搜索树并计算完整分支的算法

Question

我需要创建一种递归算法，以查看二进制树是否是二进制搜索树，并计算有多少个完整的分支（带有左和右子女节点的父节点）具有假定的全局计数变量。这是我的数据结构类的作业。

到目前为止

void BST(tree T) {
   if (T == null) return
   if ( T.left and T.right) {
      if (T.left.data < T.data or T.right.data > T.data) {
        count = count + 1
        BST(T.left)
        BST(T.right)
      }
   }
}

但是我真的不能弄清楚这个。我知道该算法无法解决问题，因为如果第二个语句不正确，则计数将为零。

谁能帮我解决这个问题？

Answer 1

正如其他人在评论中已经指出的那样，您确实在这里确实有两个无关的功能：测试树是否是搜索树，并计算完整的分支。除非分配专门要求它，否则我将编写两个单独的功能。

让我们首先看一下完整的分支。这意味着计算既有左孩子又有右孩子的节点。然后，您需要增加计数器（count = count + 1） 当两个 T.left 和 T.right 是非效果（不是 T.left.data 和 T.right.data: ：数据对此任务无关紧要）。

if (T.left and T.right) {
    count = count + 1

此外，即使右子树是空的，您也需要探索左子树，即使左子树是空的，也需要探索右子树。因此，请观察您打电话给递归电话的位置。

要测试树是否是搜索树，您需要检查数据值。您已经有了接近正确的比较；不太正确。 写几个具有各种形状的示例树 （不是很大，2至5个节点）并在它们上运行算法以查看会发生什么。

您仍然需要找到一些位置来放置有效性检查的结果。同样，请注意将递归呼叫的位置（如果您仅执行此部分，则有几种解决方案，但是在此阶段，不用担心您只看到一个解决方案）。

最后，一旦您设法单独编写两个功能，并且您已经在几个示例中对其进行了测试，请仔细地将它们放在一起（如果作业需要）。

Answer 2

在这样的事情中，通常更容易地思考，因此首先考虑您需要的东西。从您的描述中，让我们列出它们：

• 递归
• 有效性
• 完整节点的计数

好的，这是一个相当短的清单，这应该是可以管理的。让我们从一个空的方法开始，我将添加有关应该发生的事情的描述。

valid_bst () {
}

现在有效。您如何检查有效性？在聊天中，您说一棵树是有效的：“如果...所有左派孩子都比父母小，而正确的孩子比父母大。”我敢肯定，您也要允许平等。那会 t.left.value <= t.value <= t.right.value.

valid_bst () {
    This node is valid if t.left.value <= t.value <= t.right.value
}

但是，如果一个孩子失踪了怎么办？从您所说的话来看，我相信您知道如果缺少（或两者），节点仍然有效。让我们添加它，稍微重组：

valid_bst () {
    This node is valid to the left if 
        there is no left child or 
        it is no greater than the current node.
    This node is valid to the right if 
        there is no right child or 
        it is no less than the current node.
    This node is valid overall if it is valid to the left and right.
}

好的，我们现在知道此节点是否有效。我们如何检查整棵树是否有效？它不在数组中，所以我们可能不能/不想线性地循环。您的作业给出了答案：递归。但是，我们如何使用递归积累答案？我们可以访问三个信息，无论该节点是否有效，并且询问左和右节点是否有效的结果。显然，只有所有三个都是真实的，这棵树才有效。

valid_bst () {
    This node is valid to the left if 
        there is no left child or 
        it is no greater than the current node.
    This node is valid to the right if 
        there is no right child or 
        it is no less than the current node.
    This node is valid overall if it is valid to the left and right.
    Is the left child valid?
    Is the right child valid?
    This tree is only valid if this node and both its children are.
}

如果您要注意，那甚至告诉我们我们的功能需要返回什么。

现在，我们如何整合计数？您说什么很重要（“带有左和右子女节点的父节点”），这不难转换为实际代码。检查该条件是否满足并适当地递增计数器。请记住，这必须是每次真实的地方都可以到达的地方。

当然，我遗漏了一些细节，例如递归停止条件和检查null。

Answer 3

我上面的三个评论是您代码问题的三个提示。

1. 除非您已经明确定义了比较操作员应如何处理节点数据类型，否则很可能直接比较两个节点不会做您想要的。您可能的意思是比较存储在节点中的字段，例如 node1.value < node2.value
2. 现在，如果第三 if 是真的吗，您确定这就是您的意思吗？顺便说一句，您可能需要仔细检查一下如果语句执行您想要的。
3. 我认为，如果树是有效的BST，则您要返回true，否则要返回。这意味着您必须在基本情况下始终返回真或错误，并且您也应该返回递归电话的结果。