时间戳

首页 > 解决方案 > C语言中红黑树的简单结构定义

c - C语言中红黑树的简单结构定义

问题描述

多年来我不使用 C 语言，现在我又需要它了。我正在尝试构建一棵红黑树，但我一开始就卡住了，因为我错过了一些关于“结构”的东西。

请看一下我的“结构”声明，它们很简单。这是 Red_black_tree.c 中包含的头文件

 #define BLACK 0 //defalut color
#define RED 1 //

struct Node {  //create a black node by default, to have a red one look at "create_red_node"
    struct Node *left = NULL;
    struct Node *right= NULL;
    int key = 0;
    int value = 0;
    char color = BLACK;
};

struct Root_t {
    struct Node* Root;
};

struct Node* create_node () {
    struct Node* black = (Node*) malloc (sizeof(Node));
    return black;
}

struct Node* create_red_node () {
    struct Node* red = create_node ();
    red->color=RED;
    return red;
}

Root_t* create_tree () {
    struct Root_t* fake=(Root_t*) malloc (sizeof(Root_t));
    struct fake->Root->left=create_red_node ();
    struct fake->Root->right=create_red_node ();
    return fake;
}

我用“gcc Red_black_tree.c -o RBTree”编译。GCC 说类似：“预期的';' 在声明列表的末尾”7 次，或者“必须使用 'struct' 标签来引用类型...”、“预期的标识符...”。你怎么看，创建RBTree好不好？

标签： cstructbinary-search-treered-black-tree

解决方案

在 C 中，您不能在定义 a 的成员时进行分配struct

代替

struct T {
    int a = 1;
    int b = 2;
};

你需要类似的东西

struct T {
    int a;
    int b;
};
...
struct T t = {.a = 1, .b = 2};

另外，你所有的成员都设置为0（NULL是的别名(void *)0），当你想同时分配内存和初始化全部为零的时候可以使用calloc

struct Node* black = calloc(1, sizeof(*black)); // Dont cast malloc and friends

和这里：

struct fake->Root->left=create_red_node();

，您不需要struct关键字，而是：

fake->Root->left=create_red_node();

另一个建议：不要在结构中硬编码红黑树的数据，（int key, value;）即使它有效，你最终会得到一个不可重用的容器，而是使用指向void（void *data;）的通用指针和比较函数的回调在实施中。

struct Node *insert(struct Node *root, int (*comparer)(const void *, const void *)) ...

推荐阅读