2

我正在研究创建一个通用的 BST。没有什么喜欢没有 COTS，但我正在尝试确定跟踪 void* 类型的最佳方法。这是节点的接口：

typedef struct
{
   void *data;
   struct TreeNode *left;
   struct TreeNode *right;  
} TreeNode;

但是，当我编写添加/删除时，我需要进行比较，因此我需要跟踪“数据”指向的数据类型，对吧？

基本思想是有一个枚举 Node_Type 和一个函数 compareTreeNodes，它接收两个 TreeNode 和枚举作为第三个参数。这将允许函数确定将 void* 转换为什么。

还有其他/更好的想法吗？

4

2 回答 2

4

但是，当我编写添加/删除时，我需要进行比较，因此我需要跟踪“数据”指向的数据类型，对吧？

看看如何qsort()解决这个问题。它也需要处理任意数据类型。基本上，您通过函数指针将比较委托给用户。

于 2010-10-14T13:38:32.900 回答
3

我假设单个 BST 中只有一种类型的数据。在这种情况下，我将进行封装struct，其中包含指向根节点的指针和指向比较函数的指针。BST 的用户必须在初始化时提供合适的功能。

typedef struct {
    TreeNode *root;
    int (*compar)(const void *, const void *);
} Tree;

顺便说一句，您的第一行可能应该是typedef struct TreeNode {. 您有一个 typdef'd anonymous struct，但在内部引用了一个不存在的标记结构。这两个版本可以工作：

typedef struct TreeNode {
    void *data;
    struct TreeNode *left, *right;
} TreeNode;

typedef struct TreeNode TreeNode;
struct TreeNode {
    void *data;
    TreeNode *left, *right;
};

您不能将自引用设为匿名structs。

于 2010-10-14T13:42:30.100 回答