Представление внутренних и внешних узлов в двоичном дереве в C

Question

Я читаю структуры данных в C и C ++ по Tannenbaum.Ниже приведен фрагмент текста из книги

Нелистовые узлы называются внутренними узлами, а листья называются внешними узлами.Эта терминология часто используется, когда определяется только один тип узла.Конечно, указатель сына во внутреннем узле должен быть идентифицирован как указывающий на внутренний и внешний узел.Это можно сделать двумя способами:

1. Один из методов - объявить два разных типа узлов и типов указателей и использовать объединение для внутренних узлов, где каждая альтернатива содержит один из двух типов указателей.
2. Другой метод состоит в том, чтобы сохранить один тип указателя и один тип узла, где узел является объединением, которое выполняет (если узел является внутренним узлом) или нет (если внешний узел) содержит левый иполя правого указателя.

Мои вопросы

(A) Что автор подразумевает указатель сына во внутреннем узле?

(B) можетМожно ли определить пример структуры для двух методов в C, чтобы понять операторы?

Спасибо!

Answer 1

Что автор означает указатель сына во внутреннем узле?

Полагаю, текст о структуре данных, называемой деревом. Одним из подходов к построению такой структуры является определение структуры C (sic!) Следующим образом:

struct Node {
    int someData;
    struct Node *left, *right;
};

Итак, сын ссылается на то, на что ссылается автор, это поля left и right, имеющие типы указателей. Их чаще называют дочерние указатели.

Может ли кто-нибудь определить пример структуры для двух методов в C, чтобы понять утверждения?

Вот они.

(1)

struct InternalNode;
struct ExternalNode;

union ChildPointer {
    struct InternalNode *asInternal;
    struct ExternalNode *asExternal;
};

struct InternalNode {
    // Some data here

    union ChildPointer left, right;
};

struct ExternalNode {
    // External node data here
};

Однако я не буду объяснять, как заранее узнать, является ли левый дочерний узел узла внутренним или внешним, возможно, он должен быть известен по внутреннему состоянию или, может быть, существует только один экземпляр структуры ExternalNode, чтобы который связывает все неконечные узлы и возможно прямое сравнение, может кто-то посоветует.

(2)

union Node;
struct InternalData {
    // Internal node data here

    union Node *left, *right;
};

struct ExternalData {
    // External node data here
};

union Node {
    struct InternalData internal;
    struct ExternalData external;
};

Это можно сделать намного удобнее, используя анонимные структуры / союзы, но это расширение MS на C.

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