Преемник и преемник в двоичном дереве

Question

Я хотел реализовать 2 кода, один для самого большого преемника x и один для самого маленького предшественника x в двоичном дереве.

data LookupTree a = Blatt | Knoten a (LookupTree a) (LookupTree a) 
biggestSucc :: Ord a => a -> LookupTree a -> Int 
biggestSucc x Blatt = error "Am Knoten" 
biggestSucc x (Knoten a l r) 
    |a == x = max l r 
    |a /= x = biggestSucc x _ 

smallestPre :: Ord a => a -> LookupTree a -> Int 
smallestPre x Blatt = error "Am Knoten" 
smallestPre x (Knoten a l r) 
    |a == x = 
    |a /= x = smallestPre x _ 

Проблема заключается функция max и min и smallestPre/biggestSucc x _ вещь. Но как еще я могу сказать ему идти в обоих направлениях узла? Благодаря!

Answer 1

Если вы говорите о предшественнике или преемнике узла в BST, я представляю нижеприведенное решение. Я не понимаю, что вы подразумеваете под наименьшим предшественником узла, потому что самый маленький предшественник узла - это самый маленький элемент в BST, который очень легко найти.

Так что я показываю ниже дается узел с поиском заказовМои предшественника или крупнейшего предшественника:

Подпись, которые вы передаете не будет работать, потому что нам нужно закодировать родительскую информацию:

Следовательно, дерево будет выглядеть следующим образом:

type Parent = BstP 
type LChild = BstP 
type RChild = BstP 

data BstP = None | Node1 Key Parent LChild RChild deriving Show 

И код, чтобы найти заказовМои предшественника приводится ниже:

type Key = Int 

predecessor :: BstP -> Key 
predecessor None    = undefined 
predecessor (Node1 a p None _) = findPredAncestor a p 
predecessor (Node1 a _ l _) = treeMaximumP l 

treeMaximumP :: BstP -> Key 
treeMaximumP None    = undefined 
treeMaximumP (Node1 a _ _ None) = a 
treeMaximumP (Node1 _ _ _ r)  = treeMaximumP r 

findPredAncestor :: Key -> BstP -> Key 
findPredAncestor k (Node1 a p l r) 
    | (keyP r) == k = a 
    | otherwise = findPredAncestor a p 

keyP :: BstP -> Key 
keyP None   = undefined 
keyP (Node1 a _ _ _) = a