按字母顺序排序BST，并将其作为SML中的列表返回

Question

我有这个树

datatype 'a newarbolbin =
Vacio 
| Nodo of 'a newarbolbin * 'a * 'a newarbolbin;

这个功能可以按我想的方式订购：

fun preOrden2 (Vacio) = []
| preOrden2 (Nodo(L, r, R)) = [r] @ preOrden2(L) @ preOrden2(R);
fun inOrden2 (Vacio) = []
| inOrden2 (Nodo(L, r, R)) = inOrden2(L) @ [r] @ inOrden2(R);
fun postOrden2 (Vacio) = []
| postOrden2 (Nodo(L, r, R)) = postOrden2(L) @ postOrden2(R) @ [r];

我必须排序的树如下：

val diccionario : (string * string) newarbolbin = Vacio

第一个字符串是西班牙语单词，第二个字符串是翻译成英语的单词，我必须按照西班牙语单词的字母顺序对其进行排序，英语单词并不重要，我为此做的功能显然不起作用，因为我可能又想得太多了，如下所示：

fun listar_orden_alfabetico (Vacio) = []
| listar_orden_alfabetico (Nodo(L, (esp, ing), R)) = 
if esp < listar_orden_alfabetico(L) then 
(if listar_orden_alfabetico(L) < listar_orden_alfabetico(R) then 
preOrden2(Nodo(L, (esp, ing), R)) 
else 
preOrden2(Nodo(R, (esp, ing), L)))
else 
(if listar_orden_alfabetico(R) < listar_orden_alfabetico(L) then 
postOrden2(Nodo(L, (esp, ing), R)) 
else 
postOrden2(Nodo(R, (esp, ing), L)))

以防万一，这就是我的错误：

stdIn:44.53-48.132 Error: operator and operand do not agree [overload - bad instantiation]
operator domain: 'Z[OL(<)] * 'Z[OL(<)]
operand:         'Z[OL(<)] * 'Y list
in expression:
esp < listar_orden_alfabetico L
stdIn:45.59-46.129 Error: operator and operand do not agree [overload - bad instantiation]
operator domain: 'Z[OL(<)] * 'Z[OL(<)]
operand:         'Y list * 'Y list
in expression:
listar_orden_alfabetico L < listar_orden_alfabetico R
stdIn:47.59-48.131 Error: operator and operand do not agree [overload - bad instantiation]
operator domain: 'Z[OL(<)] * 'Z[OL(<)]
operand:         'Y list * 'Y list
in expression:
listar_orden_alfabetico R < listar_orden_alfabetico L

我知道这意味着我用错了函数，但我真的不知道该怎么办

---

经过一些更改，我添加了一个新功能，我想出了这个：

fun stringdend (Vacio) = "zzzzzzzzzzzzzzzzz"
| stringdend (Nodo (L,(esp,ing),R)) = esp;
fun listar_orden_alfabetico (Vacio) = []
| listar_orden_alfabetico (Nodo(L,(esp,ing),R)) = if esp<stringdend(L) 
then (if stringdend(L)<stringdend(R) 
then preOrden2(Nodo(L,(esp,ing),R)) 
else preOrden2(Nodo(R,(esp,ing),L)))
else (if stringdend(R)<stringdend(L)
then postOrden2(Nodo(L,(esp,ing),R)) 
else postOrden2(Nodo(R,(esp,ing),L)));
val diccionario = Nodo(Nodo(Nodo(Vacio,("hola","hi"),Vacio),("comer","eat"),Nodo(Vacio,("agucate","eggplant"),Vacio)),("agua","water"),Nodo(Vacio,("sadico","sadistic"),Vacio));

结果不太正确，我仍然不知道为什么

val it =
[("agua","water"),("comer","eat"),("hola","hi"),("agucate","eggplant"),
("sadico","sadistic")] : (string * string) list

Answer 1

问题是您的"二进制搜索树"；输入是而不是二进制搜索树；其节点没有排序
(节点的顺序使其成为"搜索"树。(

如果您使用正确构建的搜索树，例如

val diccionario =
Nodo(
Nodo(
Nodo(Vacio,("agua","water"),Vacio),
("agucate","eggplant"),
Nodo(Vacio,("comer","eat"),Vacio)),
("hola","hi"),
Nodo(Vacio,("sadico","sadistic"),Vacio));

有序遍历给出了字母顺序：

- inOrden2 diccionario;
val it =
[("agua","water"),("agucate","eggplant"),("comer","eat"),("hola","hi"),
("sadico","sadistic")] : (string * string) list

(你真的应该实现正确构建BST的功能，而不是手工完成。(

Answer 2

您希望函数listar_orden_alfabetico返回一个list。如果是，这种比较应该如何进行？

esp < listar_orden_alfabetico(L)

esp是string，而listar_orden_alfabetico(L)意味着是list。没有<运算符可以比较这两种数据类型。