Проблема с получением поддерева в SML
Я застрял в кодировании, где мне нужно получить поддерево для данного узла в 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) дать поддерево, или я должен правильно пройти по дереву, чтобы получить его.
Спасибо. Я исправил это с помощью nodeExist, но почему-то без него не могу. Я хочу сделать что-то вроде fun subtree(x,Empty) = Empty | поддерево (x, T как узел (y, слева, справа)) = если (x = y), то T иначе поддерево (x, слева) или другое поддерево (x, справа); Но orelse дает ошибку несоответствия типа.
Ответы 1
Начну с вашей попытки из комментариев, так как она очень близка:
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
(Это довольно окольный способ найти решение, но именно так шел ход моих мыслей, когда я пытался переработать вашу функцию.)
Спасибо за подробное объяснение.
Node (x,left,right)— это то же дерево, что иctree, но с заменой корневого элемента наx. Вам нужно пройти через дерево. (И вам не нужноnodeExist.)