按字母顺序排序 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

您想要函数 listar_orden_alfabetico 到 return 一个 list。如果是这样，这种比较应该如何进行？

esp < listar_orden_alfabetico(L)

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

Answer 2

问题是您的“二叉搜索树”输入不是二叉搜索树；它的节点没有排序。
（节点的顺序使其成为“搜索”树。）

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

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 的函数，而不是手动完成。）

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

Ordering a BST in alphabetic order and returning it as a list in SML

sml