c - 将结构数组转换为二叉搜索树

Question

所以我有一个结构数组，我想把它变成一个二叉搜索树。这是我的代码的样子。

typedef struct Student{
    char name[25];
    char surname[25];
    char Id[8];
    double grade;
}Student;

struct TNode
{
    struct TNode* data;
    struct TNode* left;
    struct TNode* right;
};

struct TNode* newNode(struct TNode* data);

/* A function that constructs Balanced Binary Search Tree from a sorted array             
*/
struct TNode* sortedArrayToBST(struct Student** students, int start, int end)
{
    /* Base Case */
    if (start > end)
      return NULL;

    /* Get the middle element and make it root */
    int mid = (start + end)/2;
    struct TNode *root = newNode(students[mid]);

    /* Recursively construct the left subtree and make it
       left child of root */
    root->left =  sortedArrayToBST(students, start, mid-1);

    /* Recursively construct the right subtree and make it
       right child of root */
    root->right = sortedArrayToBST(students, mid+1, end);

    return root;
}

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct TNode* newNode(struct TNode * data)
{
    struct TNode* node = (struct TNode*)
                     malloc(sizeof(struct TNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
}

/* A utility function to print preorder traversal of BST */
void preOrder(struct TNode* node)
{
    if (node == NULL)
        return;
    printf("%s %s %s %.2f ", node->data);
    preOrder(node->left);
    preOrder(node->right);
}

下面是我在 main 中调用函数的方式。

struct TNode *root = sortedArrayToBST(&students, 0, n-1); 

尽管结构数组在我的主函数中工作正常，但出于某种原因这似乎不起作用。在调用 sortedArraytoBST 函数之前，我总是在 main 中对我的结构数组进行排序。请帮助我。

Answer 1

我无法确定这个答案是否完整，因为您的代码不完整，所以我无法对其进行测试。

还有一个“明显”的错误:你声明

struct TNode* newNode(struct TNode* data);

但是你调用它

struct TNode *root = newNode(students[mid]);

其中 students[mid] 是一个 struct Student *。

指向不同类型的指针在 C 中不兼容。我猜想您想要的是一些“通用”B 树。 C中有一个解决方案:generic指针是void *。您不能取消引用它，但是您可以将它隐式地与任何其他(数据)指针类型相互转换。

所以你至少应该做的是改变你的struct:

struct TNode
{
    void *data;
    struct TNode *left;
    struct TNode *right;
};

和你的函数原型(prototype):

struct TNode* newNode(void *data);

---

在您的 preOrder 函数中，您尝试 printf() 整个结构 -> 这是不可能的，printf() 需要每个转换说明符只有一个参数!所以改变它，例如为此(如果您知道 data 总是指向 struct Student):

void preOrder(struct TNode* node)
{
    if (node == NULL)
        return;
    struct Student *stud = node->data;
    printf("%s %s %s %.2f ", stud->name, stud->surname, stud->id, stud->grade);
    preOrder(node->left);
    preOrder(node->right);
}