驗證二叉搜索樹 - 初學者在哈斯克爾

所以基本上我想開始一個節點，它必須大於左子樹，但比右邊小...等等。在我的工作表上，它表示將其分成兩個功能以使其更容易。使用'也許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

它可以編譯，但如果我刪除空在詳盡的get_element模式說。 - >沒什麼的is_valid_binary_search_tree也沒有，如果子樹的右子樹比主節點小的比較（這是真的是我的大問題）

來源

2012-05-12 Herr Schlachter

與你所描述的解決方案的問題是，它是不是足以簡單地檢查當前樹元素是否大於左側，分別小於右側子元素。例如，下面是不是有效的二叉樹：

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-12 04:07:54 Peter

謝謝，我把它放在一起，並得到了它。我決定在這個過程中寫一個布爾is_ordered功能，發現它遞歸地檢查它是否是按升序排列，不接受'X：XS = X <= is_ordered xs' 相反：'X：Y ：ZS = X <= Y && is_ordered（Y：ZS）' 你知道爲什麼發生這種情況？ –

@HerrSchlachter：'x'具有類型'A'，同時'is_ordered xs'具有輸入'Bool'。將它們與'<='進行比較是沒有意義的。 – hammar

我建立在彼得的答案提供了一個有效的解決方案

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-12 11:54:08 jackdh

驗證二叉搜索樹 - 初學者在哈斯克爾

回答

相關問題