0

そのため、2 つのバイナリ ツリーに同じ番号が含まれているかどうかを検出する関数に取り組んでいます。

だから私が思いついたのは次のとおりです。これはうまく機能しますが、問題は合計5つの機能を使用していることです。2 つの BT が 1 つの機能だけを持つ同じ要素を持っているかどうかを検出する別の方法はありますか? これまでのところ、うまくいくように見える私の解決策があります。

flatten :: BinTree a -> [a]
flatten Empty        = []
flatten (Node l x r) = flatten l ++ [x] ++ flatten r

splt :: Int -> [a] -> ([a], [a])
splt 0 xs = ([], xs)
splt _ [] = ([],[])
splt n (x:xs) = (\ys-> (x:fst ys, snd ys)) (splt (n-1) xs)

merge :: Ord a => [a] -> [a] -> [a] 
merge xs [] = xs
merge [] ys = ys    
merge (x:xs) (y:ys) = if (x > y) then y:merge (x:xs) ys else x:merge xs(y:ys)

msort :: Ord a => [a] -> [a]
msort [] =[]
msort (x:[]) = (x:[])
msort xs = (\y -> merge (msort (fst y)) (msort (snd y))) (splt (length xs `div` 2) xs)

areTreesEqual :: (Ord a) => BinTree a -> BinTree a-> Bool
areTreesEqual Empty Empty = True
areTreesEqual Empty a = False
areTreesEqual a Empty = False
areTreesEqual a b = msort (flatten (a) ) == msort (flatten (b))
4

1 に答える 1

1

どうですか

import Data.MultiSet as Set

equal a b = accum a == accum b
  where accum Empty = Set.empty
        accum (Node l x r) = Set.insert x (accum l `Set.union` accum r)

セットは順序付けられていない比較に最適であり、マルチセットはそれを確実にします

 1   /=   1
1 1

たとえば、重複した数字は適切にカウントされます。これが大きな問題ではない場合はMultiSet、Set. この種のものには3行がかなりまともだと思います。

于 2013-09-28T22:38:50.720 に答える