c - 如何按名称(字符串)搜索和排序BST？按队列打印并缩进？

我必须编写一个程序，将一个.txt文件读入树中，然后允许它执行特定的操作。我卡在那里，我需要通过名称进行排序树，按名称搜索以及任何输入将是真棒的部分。
所以，我的输入文件的格式为：

3800 Lee, Victor; 2.8
3000 Brown, Joanne; 4.0

因此，我的二叉树的格式为：

 typedef struct
 {
 int   id;
 char  name[MAX_NAME_LEN];
 float gpa;
 } STUDENT;

typedef struct node
{
 STUDENT*        dataPtr;
 struct node* left;
 struct node* right;
} NODE;

typedef struct
{
 int   count;
 int  (*compare) (void* argu1, void* argu2); // Was provided by teacher, not really sure how this works
 NODE*  root;
} BST_TREE;

读取文件和插入功能都可以正常工作，但是我不知道如何通过名称（字符串）实现搜索。 strcmp可以工作吗？如果是这样，我将如何使用它？我有一个有效的搜索功能，但已针对ID（整数）进行了优化，并且不适用于字符串。
这是搜索功能的一部分：

/*  ===================== _retrieve =====================
Searches tree for node containing requested key
and returns its data to the calling function.
   Pre     _retrieve passes tree, dataPtr, root
           dataPtr is pointer to data structure
              containing key to be located
   Post    tree searched; data pointer returned
   Return  Address of data in matching node
           If not found, NULL returned
 */
 static void* _retrieve (BST_TREE* tree,
              void* dataPtr, NODE* root)
 {
if (root){
     if (tree->compare(dataPtr, root->dataPtr) < 0)
         return _retrieve(tree, dataPtr, root->left);
     else if (tree->compare(dataPtr, root->dataPtr) > 0)
         return _retrieve(tree, dataPtr, root->right);
     else
         // Found equal key
         return root;
}  // if root
else
    // Data not in tree
    return NULL;
 }// _retrieve

另外，如何对BST进行排序？特别是我该如何按名称对它进行排序，该名称是字符串，由两部分组成（名字和姓氏）？我是否应该仅按首字符排序？我正在考虑以某种方式删除姓氏部分，并使其更易于仅按名字查看，因为我的老师并没有真正说明她希望这样做的方式。她从未告诉过我们如何按非整数值对BST进行排序，因此我迷路了。

还有一件事是，该树将需要通过以下方式打印：level（queue），缩进列表和仅叶子。
缩排打印清单的示例：

对于执行这些任务的任何建议，我将非常感谢。

谢谢

最佳答案

不，strcmp()无法直接运行，因为比较器传递了两个STUDENT *值（伪装为void *。）因此，您必须编写一个将指针解包然后调用strcmp()的比较器：

int cmp_by_name(const void *v1, const void *v2)
{
    const STUDENT *s1 = (STUDENT *)v1;
    const STUDENT *s2 = (STUDENT *)v2;

    return strcmp(s1->name, s2->name);
}

会有人说演员不是绝对必要的。会有人观察到，在对strcmp()的调用中使用稍微复杂一些的表达式可以省略变量。但是，如果您决定也需要比较GPA或ID号，那么使用局部变量会更干净。无论如何，编译器都可能会作为常规优化来消除变量，因此以清晰为代价手动进行操作就是“过早优化”的情况。

因为要使用的模板在比较器类型的声明中不包含const，所以您可能必须在函数定义行中省略const。

您无需对BST进行排序；数据已按排序顺序存储。您可以按顺序遍历树，将其打印出来。

您只需将compare的BST_TREE元素设置为cmp_by_name：

BST_TREE root = { 0, cmp_by_name, 0 };

然后，以&root作为树的根调用函数。这代替了您提供的比较功能。您应该使用单个比较功能来构建和搜索树。在不同时间使用不同的比较器会造成混乱。

如果您使用的是ISO 8859代码集（例如8859-15）或使用Unicode，则无需换逗号。逗号比任何字母早排序，因此这些名称是按顺序排列的：

Lee, James
Lee, Kirk
Leeds, Shaw
Left, Right

您唯一遇到问题的是数据是否不一致：

Lee James
Lee, Brady

那是排序的顺序；您可能希望顺序颠倒。