gpt4 book ai didi

Haskell 2-3-4 树

转载 作者:行者123 更新时间:2023-12-04 06:04:19 24 4
gpt4 key购买 nike

我们被要求在 Haskell 中创建一个 2-3-4 树,如写入数据类型、插入函数和显示函数。

我发现很难获得有关这种树的信息,即使使用我熟悉的语言(Java、C++)也是如此。

到目前为止我所拥有的 -

data Tree t = Empty 
| Two t (Tree t)(Tree t)
| Three t t (Tree t)(Tree t)(Tree t)
| Four t t t (Tree t)(Tree t)(Tree t)(Tree t) deriving (Eq, Ord, Show)


leaf2 a = Two a Empty Empty
leaf3 a b = Three a b Empty Empty Empty
leaf4 a b c = Four a b c Empty Empty Empty Empty

addNode::(Ord t) => t -> Tree t -> Tree t
addNode t Empty = leaf2 t
addNode x (Two t left right)
| x < t = Two t (addNode x left) right
| otherwise = Two t left (addNode x right)

这可以编译,但我不确定它是否正确,但不确定如何开始将插入写入三节点或四节点。

作业还说,显示功能的“派生显示”是不够的,它应该以通常在图表中看到的格式打印出树。再一次,不确定如何去做。

任何帮助或方向表示赞赏。

最佳答案

我对 2-3-4 树一无所知,但是对于三节点,您将从以下内容开始:

addNode t (Three x y left mid right)
| cond1 = expr1
| cond2 = expr2
(etc)

什么 cond1 , cond2 , expr1 , 和 expr2确切地说,取决于 2-3-4 树是什么的定义。

至于 show方法,大纲是这样的:
instance (Show t) => Show (Tree t) where
show Empty = ...
show (Two x l r) = ...show x...show l...show r...
show (Three x y l m r) = ...
show (Four x y z l m n r) = ...

实现取决于您希望它的外观,但对于非 Empty 情况,您可能会调用 show在显示的树的所有组件上。如果你想缩进树的嵌套部分,那么也许你应该创建一个单独的方法:
instance (Show t) => Show (Tree t) where
show = showTree 0

showTree :: Show t => Int -> Tree t -> String
showTree n = indent . go
where indent = (replicate n ' ' ++)
go Empty = "Empty"
go (Two x l r) = (...show x...showTree (n+1) l...showTree (n+1) r...)
(etc)

关于Haskell 2-3-4 树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8549057/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com