Проблема в получении поддерева в SML - PullRequest
Новая
       23

Проблема в получении поддерева в SML

1 голос
/ 31 марта 2019

Я застрял в коде, где мне нужно получить поддерево для данного узла в SML.

Тип данных ниже. 

datatype ctree = Empty | Node of char*ctree*ctree

Теперь мне нужно написать функцию, которая будет возвращать поддерево с корнем в данном узле.

Я написал вспомогательную функцию 'nodeExist (n, tree)', которая проверит, существует ли узел на дереве. Затем я попробовал что-то вроде ниже - 

fun getSubtree(x,ctree) =
   case ctree of
         Empty => Empty
      | Node(y,left,right) => if(nodeExist (x,ctree)) = true then Node(x,left,right) else Empty;

Это не дает правильного вывода. Может узел (x, left, right) дать поддерево, или я должен пройти дерево должным образом, чтобы получить его.

1 Ответ

3 голосов
/ 01 апреля 2019

Я начну с вашей попытки из комментариев, так как она очень близка: 

fun subtree(x, Empty) = Empty 
  | subtree(x, T as Node(y, left, right)) = 
        if x = y 
        then T 
        else subtree(x, left) orelse subtree(x, right)

но есть проблема с типом, поскольку orelse хочет два значения истинности, а не два дерева.
Вам нужно сделать что-то логически похожее, но с деревьями вместо фактов.

Один из способов увидеть путь вперед - переписать orelse как эквивалентный анализ случая 

fun subtree(x, Empty) = Empty 
  | subtree(x, T as Node(y, left, right)) = 
        if x = y 
        then T 
        else let val l = subtree(x, left) in
             case l of
                 true => l
               | false => subtree(x, right)
             end

Здесь мы можем просто заменить логические случаи на древовидные: 

fun subtree(x, Empty) = Empty 
  | subtree(x, T as Node(y, left, right)) = 
        if x = y 
        then T 
        else let val l = subtree(x, left) in
             case l of
                 Node _ => l
               | Empty  => subtree(x, right)
             end

или его можно немного переставить, чтобы сделать его короче 

fun subtree(x, Empty) = Empty 
  | subtree(x, T as Node(y, left, right)) = 
        if x = y 
        then T 
        else case subtree(x, left) of
               Empty  => subtree(x, right)
             | t => t

(Это довольно окольный способ найти решение, но именно так у меня проходил ход мыслей, когда я пытался переделать вашу функцию.)

...