Вставка в бинарное дерево выражения с Гото


Я работаю на двоичный дерево разделов.

В настоящее время узлы только вставить в правый. Узел, который дети будут иметь 0 в качестве данных. Здесь представлены правила ввода.

Если узел ввода данных и ни один родитель, текущих данных становится левым потомком, а узел вставить справа.

1       0
^ ---> / \
      1   2

Если узел имеет родителя, является левым потомком родителя и данные, узел вставлен в правильный узел родительского элемента, и вставленный узел занимает свое место

  0          0
 / \        / \ 
1   2 ---> 3   0
^             / \
             2   1

Я хотел бы получить обратную связь на мой вставить функцию. Я положил goto заявление, чтобы не повторять код, но я хотел бы избежать этого, чтобы сделать функцию более ясно.

Жить на Coliru с подробного вывода

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

struct node
{
    int data;

    struct node* parent;
    struct node* left;
    struct node* right;
};

struct node* create_node(int i)
{
    struct node* n = calloc(1, sizeof(struct node));

    n->data = i;

    n->parent = NULL;
    n->left = NULL;
    n->right = NULL;

    return n;
}

void destroy_node(struct node* n)
{
    if (n->left != NULL)
    {
        destroy_node(n->left);
    }

    if (n->right != NULL)
    {
        destroy_node(n->right);
    }

    free(n);
}

void insert(struct node* i, struct node* n)
{
    printf("insert at %d node %d\n", i->data, n->data);
    // TODO : insert rightmost or leftmost
    if (i->parent != NULL)
    {
        if (i->parent->left == i)
        {
            // if insert node is left
            struct node* p = i->parent;
            i->parent = NULL;
            insert(p->right, i);
            p->left = n;
            n->parent = p;
            return;
        }
        else if (i->parent->right == i)
        {
            // if insert node is right
            if ((i->left == NULL) && (i->right == NULL))
            {
                // if insert node is rightmost
                goto insert;
            }

            if (i->right != NULL)
            {
                // if right node is not rightmost
                insert(i->right, n);
                return;
            }
        }
    }
    else if (i->parent == NULL)
    {
        // if insert node is root
        if ((i->left == NULL) && (i->right == NULL))
        {
            // if insert node has no children
            goto insert;
        }
        else if (i->right != NULL)
        {
            // if right child is not null
            insert(i->right, n);
            return;
        }
    }

insert: ;
    int value = i->data;
    i->data = 0;

    struct node* left = create_node(value);
    left->parent = i;

    n->parent = i;

    i->left = left;
    i->right = n;

    return;
}

int main()
{
    // A
    struct node* root = NULL;

    // B
    root = create_node(1);

    assert(root->data == 1);
    assert(root->left == NULL);
    assert(root->right == NULL);

    // C
    insert(root, create_node(2));

    assert(root->data == 0);
    assert(root->left->data == 1);
    assert(root->right->data == 2);

    // X
    insert(root->right, create_node(3));

    assert(root->right->data == 0);
    assert(root->right->left->data == 2);
    assert(root->right->right->data == 3);

    // Y
    insert(root->right->left, create_node(4));

    assert(root->right->left->data == 4);
    assert(root->right->right->data == 0);
    assert(root->right->right->left->data == 3);
    assert(root->right->right->right->data == 2);

    // Z
    insert(root->right->left, create_node(5));

    assert(root->right->left->data == 5);
    assert(root->right->right->left->data == 3);
    assert(root->right->right->right->left->data == 2);
    assert(root->right->right->right->right->data == 4);

    destroy_node(root);

    return 0;
}


226
5
задан 3 апреля 2018 в 12:04 Источник Поделиться
Комментарии
1 ответ

Ваши требования вставки очень странно, но я предполагаю, что у вас есть какая-то причина для них, поэтому я не буду комментировать это.


  • Одним из огромных преимуществ наличия родительского указателя в каждом узле является то, что вы можете полностью избавиться от рекурсии. В вашем случае, избавившись от рекурсии позволит существенно повысить производительность и потребление стека. Так как ваша рекурсия не хвостовая рекурсия, нет никакого разумного способа компилятор может оптимизировать его - так результат будет очень неэффективный код. Рекурсии следует избегать в целом, так как он медленный, памяти напряженных, опасных и иногда трудно читать.

    Вместо того, чтобы, используя рекурсию, можно просто петлю вниз списка узлов, пока вы не нажмете нуль в листок, проверяя, если каждый узел государств вставить условие на этом пути. Следить за текущим узлом, указывая на его локальный указатель, а не указатель, переданный в качестве параметра рекурсивной функции.

    Если вам нужно активизировать в дереве, вы делаете это, устанавливая текущий указатель на своего родителя, который затем эквивалентно возврата из рекурсивной функции.


  • Ваш Гото и несколько возвращает немного трудно читать и следовать. Избавившись от рекурсии, вы сможете избавиться от всех этих слишком. Ваша новая функция должна выглядеть как-то так псевдо:

    insert function
    if we are at root
    special case, handle it
    else
    loop looking for candidate to insert
    if candidate found, set pointer to it and break loop

    if candidate found
    create node
    insert node at candidate


  • Точно так же и ваши destroy_node функция может быть переписана с петлей вместо рекурсии, хотя производительность не является проблемой здесь.

  • В create_node функция-это в основном бессмысленно, это просто вызов malloc/с памятью и не много ценностей. Установить все указатели узла вручную в любом случае, поэтому установка их в null заранее ничего не добавляет. Вы можете пропустить эту функцию и просто вызываете malloc. (Также, обязательное замечание: вы должны проверить, если функция malloc возвращает NULL и добавить некоторые обработки ошибок.)

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

  • Имея пустой return ; В конце void функция заполняет никакой цели.

  • Функции printf, естественно, должны не быть частью вставить алгоритм, но я так понимаю, что это просто отладочный код, который будет удален позже(?).

  • Маленькое замечание: после инициализации всех членов структуры, нет никаких причин, чтобы использовать calloc. malloc будет немного быстрее.

  • int main() устаревший стиль в C. Вы должны использовать int main (void) (или переменной argc/argv в). Не путать с C++, где int main() это нормально и означает то же самое, что int main (void).

2
ответ дан 3 апреля 2018 в 01:04 Источник Поделиться