Дерево без каких-либо нулевых листьев в C

Question

Мне нужно создать дерево BNF с узлами, которые имеют 3 дочерних элемента, 2 дочерних элемента, 1 дочерний элемент и 0 дочерних элементов, и я должен создать различные структуры для каждого из них, потому что не должно быть какого-либо ребра, указывающего на нуль, но не могу gr asp концепцию на самом деле, потому что я делал все это только с одной структурой и указывал неиспользованный лист, чтобы обнулить любую идею, подсказку, руководство будет оценено.

Answer 1

Одним из возможных решений может быть использование теговой структуры с объединением.

Что-то вроде

enum NodeType
{
    NODE_LEAF, // A leaf node, no children
    NODE_1,    // One child
    NODE_2,    // Two children
    NODE_3     // Three children
};

struct Node
{
    enum NodeType type;

    union
    {
        struct
        {
            // TODO: Data for leaf nodes
        } leaf;

        struct
        {
            struct Node *child;  // One and only child
        } node_1;

        struct
        {
            struct Node *children[2];  // Two children
        } node_2;

        struct
        {
            struct Node *children[3];  // Three children
        } node_3;
    };
};

Затем, в зависимости от значения type, вы используете leaf, node_1, node_2 или node_3 членов профсоюза.

Answer 2

Как и в другом ответе, вам нужно перечислить, чтобы определить тип каждого узла.

enum NodeType
{
    NODE_LEAF, // A leaf node, no children
    NODE_1,    // One child
    NODE_2,    // Two children
    NODE_3     // Three children
};

Затем определите структуры для каждого типа узла, которые имеют общий префикс:

struct NodeLeaf {
    NodeType type;
    ...
};
struct Node1 {
    NodeType type;
    NodeType *child[1];
};
struct Node2 {
    NodeType type;
    NodeType *child[2];
};
struct Node3 {
    NodeType type;
    NodeType *child[3];
};

Дочерние указатели указывают на одну из структур, которые все начинаются с NodeType. Для удобства я уже дал им NodeType * в качестве типа вместо void *, чтобы было легче читать тип. Затем вы можете привести каждого дочернего элемента к правильной структуре в зависимости от того, что находится в * child [n]. И чтобы присвоить потомку приведение соответствующей структуры к NodeType* или используйте foo.child[0] = &bar.type;.