在 SML 中向树添加节点

Question

有人建议我把这个作为一个单独的问题来问，这样我就会这样做。

我有一棵人树，就像家谱一样。它从一个人开始，然后分支到父母、祖父母等。我希望能够将一个人插入到树上的某个位置（基本上替换那里的任何人）。

这些数据类型很重要：

datatype year    = Year of int | UnkYear | Irrelevant
datatype name    = Name of string | UnkName
datatype sex     = Man | Woman | UnkSex
datatype person  = Person of name * sex * year * year
datatype parents = Dad | Mom
datatype tree    = Unspec | Info of person * tree * tree

分配如下： 声明一个函数插入：树*父母列表*人->树，因此调用 insert(t, pos, p) 会将人 p 插入到树 i 中的位置 pos 中 - 假设该位置存在于树中。如果没有，它应该返回 t。

因此，我需要能够在我的树中选取一个人（比如说妈妈）并将她替换为露西（妈妈和露西都是使用数据类型 person 预先声明的值）。

到目前为止，我有这样的：

fun insert (Info(n,mf,ft) , Mom::xs , p) = Info(p, mf, insert(ft,xs,p))
  | insert (Info(n,mf,ft) , Dad::xs , p) = Info(p, insert(mf,xs,p), ft)
  | insert (Info(n,mf,ft) , [] , p)      = Unspec

似乎要做的就是删除 t 的 pos 中的任何人，并用 p 替换根 - 不完全是我想要的：S 另外，模式匹配尚未完成。

有什么想法可以让我搬到这里吗？

Answer 1

好的，当你到达给定的位置时，你想用给定的人替换树中该点的人。您所做的是，您将在每一步中替换该人，除非您到达目的地，在这种情况下，您只需删除那里的节点即可。

所以你需要做的是：

在parents-list还不为空的情况下，不要将person n替换为p - 只需遍历到适当的子树。

如果父母列表为空并且您当前位于信息节点，请将该节点中的人员替换为 p。

如果父母列表为空并且您当前位于 Unspec 节点，请将 Unspec 替换为包含 p 和两个空子树（即 Unspec< /代码>s）。

如果您到达 Unspec 节点，尽管parents-list 尚未为空，则只需返回 Unspec，按照分配保持树不变。