Oto sposób na zrobienie tego bez spłaszczania drzewa.
Z definicji tutaj
data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
deriving Show
widać, że przemierzanie drzewa od lewej do prawej, ignorowanie Node
i nawiasy, daje naprzemienną sekwencję Null
s i a
s. Oznacza to, że między każdymi dwiema wartościami jest Null
.
Moim planem jest sprawdzenie, czy każde poddrzewo spełnia odpowiednie wymagania : możemy uszczegółowić wymagania dla każdego z nich Node
, pamiętając, które wartości są pomiędzy, a następnie przetestować je dla każdego z nich Null
. Ponieważ istnieje Null
para wartości między kolejnymi wartościami, sprawdzimy, czy wszystkie pary w kolejności (od lewej do prawej) nie maleją.
Co jest wymagane? Jest to luźna dolna i górna granica wartości w drzewie. Aby wyrazić wymagania, w tym te na skraju lewej i skrajnej prawej strony, możemy rozszerzyć dowolne zamówienie o Bot
tom i Top
elementy w następujący sposób:
data TopBot a = Bot | Val a | Top deriving (Show, Eq, Ord)
Sprawdźmy teraz, czy dane drzewo spełnia wymagania bycia zarówno w porządku, jak i między podanymi granicami.
ordBetween :: Ord a => TopBot a -> TopBot a -> BinaryTree a -> Bool
-- tighten the demanded bounds, left and right of any Node
ordBetween lo hi (Node l x r) = ordBetween lo (Val x) l && ordBetween (Val x) hi r
-- check that the demanded bounds are in order when we reach Null
ordBetween lo hi Null = lo <= hi
Drzewo wyszukiwania binarnego to drzewo, które jest w porządku oraz między Bot
i Top
.
isBSTree :: Ord a => BinaryTree a -> Bool
isBSTree = ordBetween Bot Top
Obliczanie rzeczywistych wartości ekstremalnych w każdym poddrzewie, propagowanie ich na zewnątrz, daje więcej informacji, niż potrzebujesz, i jest kłopotliwe w skrajnych przypadkach, w których lewe lub prawe poddrzewo jest puste. Utrzymywanie i sprawdzanie wymagań , popychanie ich do wewnątrz, jest raczej bardziej jednolite.
flattenTree
pierwszego. Możesz wrócićFalse
wcześniej, jeśli węzeł narusza właściwość wyszukiwania bez konieczności przechodzenia przez całe poddrzewo zrootowane w tym węźle.