haskell - 在 Haskell 中列出的二叉搜索树

Question

我在haskell 中获得了一个BST，它能够添加、删除、查找、findMax 和removingMax。我必须制作一个将数据转换为列表结构的函数。

bstToList:: (BST k v) -> [String]
bstToList EmptyBST = ["hi"]
bstToList (BSTNode k v nl nr) = bstToList nl ++ bstToList nr

我有 EmptyBST = ["hi"] 的原因是检查它返回的内容。当给定输入

bstToList (bstAdd 1 "Phil" (bstAdd 2 "Ip" EmptyBST))

返回一个列表 ["hi","hi","hi"] 我不清楚为什么一切都返回空列表。假设除 bstToList 之外的所有函数都正确且工作正常。任何帮助表示赞赏！

score 3 · Accepted Answer

线

bstToList (BSTNode k v nl nr) = bstToList nl ++ bstToList nr

不使用节点上的值，这就是为什么您只能从 EmptyBST 位获取数据的原因。

你需要

BstToList :: BST k v -> [v] 
bstToList EmptyBST = []
bstToList (BSTNode k v nl nr) = bstToList nl ++ [v] ++ bstToList nr

这样这个节点的值就被插入到它左右两边的值之间。（这称为按顺序遍历。）

如果你想列出你需要的键和值

BstToList :: BST k v -> [(k,v)] 
bstToList EmptyBST = []
bstToList (BSTNode k v nl nr) = bstToList nl ++ [(k,v)] ++ bstToList nr

注意 (k, v) 周围的括号 - 它们将两个项目变成一对。类型签名也是如此。（缺少对语法是您遇到错误的原因。）

[k,v] 只能在 k 和 v 是相同类型的情况下作为数据使用，而 [k,v] 不能作为类型使用。

1 回答 1