在 SML 中获取子树的问题

Question

我被困在编码中，我必须在 SML 中获取给定节点的子树。

数据类型如下。

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

现在我必须编写函数，它将 return 以给定节点为根的子树。

我写了一个辅助函数 'nodeExist(n,tree)' 它将检查节点是否存在于 tree.Then 我尝试了下面的某种方式-

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;

它没有给出正确的 output.Can Node(x,left,right) 给出子树，或者我应该正确地遍历树来得到它。

Answer 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

（这是一种非常迂回的寻找解决方案的方式，但这是我尝试修改您的函数时的思路。）

在 SML 中获取子树的问题

Issue in getting subtree in SML

functional-programming

sml

smlnj