时间戳

首页 > 解决方案 > 如何使用 f# 中的给定字符串列表为树编写删除函数？

data-structures - 如何使用 f# 中的给定字符串列表为树编写删除函数？

问题描述

我正在尝试编写一个“删除”函数，该函数可以根据给定字符串列表的值删除树类型，但是当我使用该函数时，我没有得到正确的结果，例如：

代码：

type Tree = Leaf of string | Branch of (string * Tree) list

let rec remove (p :string list) (tree: Tree) :Tree =
  match p, tree with
  | a::b, y  -> 
    match y with
    | Leaf(n) when a = n -> Leaf("") 
    | Branch[(x, p)] when a = x ->  Branch[("",  remove b p)]
    | _     -> remove b y
  | [], y    -> tree

测试：

remove ["1"; "2"; "3"; "4"]  
  (Branch [("6", Branch [("1", Branch [("2", Branch [("13", Leaf "4")])])])])

给出了答案

Branch [("6", Branch [("1", Branch [("2", Branch [("13", Leaf "4")])])])]

代替

(Branch [("6", Branch [(" ", Branch [(" ", Branch [("13", Leaf " ")])])])])

如果有人可以帮助我，那就太好了，因为我无法理解我做错了什么。

标签： data-structuresf#treef#-3.0

解决方案

您这样做的方式是同时迭代列表和树。这意味着只有当数字出现在树中的顺序与它们在要删除的项目列表中出现的顺序相同时，您的代码才能工作。

如果这是您真正想要的，您可以在函数中添加一个案例以使其工作：

let rec remove (p :string list) (tree: Tree) :Tree =
  match p, tree with
  | a::b, y  -> 
    match y with
    | Leaf(n) when a = n -> Leaf("") 
    | Branch[(x, p)] when a = x ->  Branch[("",  remove b p)]
    | Branch[(x, p)] -> Branch[(x, remove (a::b) p)] // Added this line!
    | _     -> remove b y
  | [], y    -> tree

当您找到一个编号不在列表开头的分支时，添加的行会处理这种情况 - 因此我们保持分支不变并继续从子树中删除编号。

也就是说，我想您可能想要删除节点，而不管列表中元素的顺序如何。您可以通过使用类似List.contains检查是否应删除分支的方法来做到这一点：

let rec remove (p :string list) (tree: Tree) :Tree =
  match tree with
  | Leaf(n) when List.contains n p -> Leaf("") 
  | Branch[(x, sub)] when List.contains x p ->  Branch[("",  remove p sub)]
  | Branch[(x, sub)] ->  Branch[(x, remove p sub)]

请注意，此代码仍然缺少具有多个子树的分支的情况，所以这是您需要添加的内容，但希望该示例为您指明正确的方向！

推荐阅读