在haskell中的二叉搜索樹中刪除函數

如何實現刪除二叉搜索樹中的元素的函數？這是我的樹：在haskell中的二叉搜索樹中刪除函數

data Tree a = Leaf 
      | Node a (Tree a) (Tree a)

我知道，如果我的樹是葉

delete :: (Ord a) => a -> Tree a -> Tree a 
delete _ Leaf = Leaf

，並在情況下，左和右是不是空的，我不得不刪除權利的最低限度（或最大值從左），它成爲根。但是，我該如何實現它？

來源

2012-02-22 Marco Sero

這個功課？ – 2012-02-22 12:10:07

@ MatveyB.Aksenov是啊 – 2012-02-22 14:59:25

然後請在下次標記它。這是常見的做法。 – 2012-02-22 15:47:11

您應該實現的功能

delMin :: Tree a -> (Tree a, a)

從樹上刪除最小元素和返回兩個修改後的樹和最小元素。然後刪除算法變爲：找到具有要刪除項目的節點並致電

-- delete' n deletes the node n and returns a modified BST 
delete' :: Ord a => Tree a -> Tree a 
delete' (Node _ l Leaf) = l 
delete' (Node _ Leaf r) = r 
delete' (Node _ l r)  = let (r', min) = delMin r in 
           Node min l r'

來源

2012-02-22 11:18:39

如果'delMin'是頂級的，那麼使用'delMin :: Tree a - > Maybe（Tree a，a）'來處理'Leaf'可能是個好主意。 – 2012-02-22 14:23:39

@DanielFischer：'delMin'，至少在當前不應該從BST模塊中導出。它可能隱藏在「where」子句中。 – 2012-02-22 14:36:59

雖然它可能被認爲通常很有用，但是如果它暴露出來，我寧願安全地處理'Leaf'。如果它只是一個地方，那當然是不必要的混亂。 – 2012-02-22 14:45:27

在haskell中的二叉搜索樹中刪除函數

回答

相關問題