在SML中获取子树的问题

Question

我陷入了编码的困境，我必须在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，左，右）给出子树，或者我应该正确地遍历树以获得它。

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

（这是找到解决方案的一种非常迂回的方式，但是当我尝试重写你的功能时，这是我的思路。）