如何检查我的二进制搜索树是否完成? (哈斯克尔) [英] How to check if my binary search Tree is complete? (Haskell)

问题描述

data BTree a = Nil | Node a (BTree a) (BTree a) deriving Show

我了解了两个二进制搜索树.一个是完美的，另一个是 完成.

二叉树是完美二叉树，其中所有内部节点都有两个孩子，并且所有叶子都在同一级别.

如果所有级别都已完全填充，则二叉树就是完整的二叉树，除了最后一个级别，并且最后一个级别中的所有键都尽可能地剩余

检查二叉树是否完美的代码非常简单

isPerfect :: BTree a -> Bool
isPerfect Nil = True
isPerfect (Node x Nil Nil) = True
isPerfect (Node x lt Nil ) = False
isPerfect (Node x Nil rt ) = False
isPerfect (Node x lt  rt ) = (&&) (isPerfect lt) (isPerfect rt)

如何检查树是否完整?

解决方案

我相信您正在尝试使此问题稍微简单一些.要检查二叉树是否完美，您不仅需要知道两个孩子都是完美的，而且要知道它们具有相同的深度.因此，递归地知道isPerfect在子级上的结果仍然不足以回答问题.

在编写递归函数时会遇到很多问题.您需要编写一个递归函数来做一些比您想做的强大的工作，然后从中提取出您想要的信息.您可以从这里开始，例如:

-- | Gives the depth of a tree if it's perfect;
-- or otherwise, Nothing
perfectDepth :: BTree a -> Maybe Int
perfectDepth Nil = Just 0
perfectDepth (Node x a b) =
    case (perfectDepth a, perfectDepth b) of
        (Just da, Just db) | da == db -> Just (da + 1)
        _ -> Nothing

(这也不是理想的实现.当您已经知道深度是错误的时，您可能会在b方面进行大量工作来验证完美性.但这是可行的，我在这里选择了简单性而不是效率)

现在您的递归为您提供了正确的信息，您应该可以以此编写isPerfect. isComplete将使用类似的策略.

data BTree a = Nil | Node a (BTree a) (BTree a) deriving Show

I learned about two binary search trees. One is perfect the other one is complete.

A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level.

A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

The code to check if a binary tree is perfect is pretty easy

isPerfect :: BTree a -> Bool
isPerfect Nil = True
isPerfect (Node x Nil Nil) = True
isPerfect (Node x lt Nil ) = False
isPerfect (Node x Nil rt ) = False
isPerfect (Node x lt  rt ) = (&&) (isPerfect lt) (isPerfect rt)

How can I check if the tree is complete?

解决方案

I believe you are trying to make this problem just a little bit simpler than possible. To check whether a binary tree is perfect, you need to know not just that both children are perfect, but that they have the same depth. So knowing the result of isPerfect recursively on the children still isn't enough to answer the question.

This comes up a lot when writing recursive functions. You need to write a recursive function to do something a little bit more powerful than you want, and then extract the info you want from that. You could start with this, for example:

-- | Gives the depth of a tree if it's perfect;
-- or otherwise, Nothing
perfectDepth :: BTree a -> Maybe Int
perfectDepth Nil = Just 0
perfectDepth (Node x a b) =
    case (perfectDepth a, perfectDepth b) of
        (Just da, Just db) | da == db -> Just (da + 1)
        _ -> Nothing

(This isn't an ideal implementation, either. You will potentially do a bunch of work on the b side verifying perfectness when you already knew the depth was wrong. But it works, and I chose simplicity over efficiency here.)

Now that your recursion is giving you the right information, you should be able to write isPerfect in terms of this. isComplete would use a similar strategy.

这篇关于如何检查我的二进制搜索树是否完成? (哈斯克尔)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！