Как написать функцию удаления для дерева, используя заданный список строк в F #? - PullRequest
Новая
       70

Как написать функцию удаления для дерева, используя заданный список строк в F #?

0 голосов
/ 29 ноября 2018

Я пытаюсь написать функцию «удалить», которая может удалять тип дерева на основе значения данного списка строк, но я не получаю что-то правильное, когда использую функцию, пример:

Код: 

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 " ")])])])])

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

1 Ответ

0 голосов
/ 29 ноября 2018

То, как вы это делаете, заключается в том, что вы перебираете список и дерево одновременно.Это означает, что ваш код может работать, только если числа появляются в дереве в том же порядке, в котором они появляются в списке элементов, которые нужно удалить.

Если это то, что вы на самом деле хотите, вы можете добавить один случай в вашу функцию, чтобы она заработала: 

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)]

Обратите внимание, что в этом коде все еще отсутствует случай для ветки с несколькими поддеревьями, так что это что-товам нужно добавить, но, надеюсь, пример укажет вам правильное направление!

...