2

つまり、基本的にノードから始めたいのですが、それは左側のサブツリーよりも大きく、右側よりも小さくする必要があります...など。私のワークシートでは、簡単にするために2つの関数に分割するように書かれています。'多分'を使用するには。（タイプ'を'から'a'に一致させることはできません。これにより、完全に停止します。

これは私が持っているものです、私は同様の質問が尋ねられるのを見ましたが、それを正しく理解することができませんでした。前もって感謝します。

is_valid_binary_search_tree :: Ord a => BSTree a -> Bool
is_valid_binary_search_tree tree = case tree of 
    Null                               -> True
    Node element t1 t2
        | element > get_element t1 -> is_valid_binary_search_tree t1
        | element < get_element t2 -> is_valid_binary_search_tree t2
        | otherwise                -> False 

get_element :: BSTree a -> Maybe a
get_element tree = case tree of
    Null               -> Nothing
    Node element t1 t2 -> Just element

コンパイルはできますが、Null-> Nothingを削除すると、get_elementに網羅的でないパターンが表示されます。is_valid_binary_search_treeは、サブツリーの右側のサブツリーがメインノードよりも小さいかどうかも比較しません。（これは本当に私の大きな問題です）

4

2 に答える 2

5

説明したソリューションの問題は、現在のツリー要素が左よりも大きいかどうか、それぞれ右の子よりも小さいかどうかを単純に確認するだけでは十分ではないことです。たとえば、次は有効な二分木ではありません。

Node 3 (Node 1 (Node 0 Null Null) (Node 2 Null Null)) 
       (Node 10 (Node (-1) Null Null) (Node 12 Null Null))

実際には簡単な解決策があります。ツリーを順番にたどって (つまり、リストに変換して)、リストが昇順かどうかを確認します。

inOrder Null = [] 
inOrder (Node a t1 t2) = inOrder t1 ++ [a] ++ inOrder t2
于 2012-05-12T04:07:54.880 に答える
0

ピーターの答えに基づいて、実用的なソリューションを提供しました

inOrder :: Tree a -> [a]
inOrder Nil = []
inOrder (Node y l r) = inOrder l ++ [y] ++ inOrder r

isAscending :: [Int] -> Bool
isAscending [x] = True
isAscending (x:xs) = x <= head (xs) && isAscending xs

is_valid_binary_search_tree :: Tree Int -> Bool
is_valid_binary_search_tree = isAscending . inOrder
于 2017-05-12T11:54:08.710 に答える