Бесплатно бинарное дерево

13

Итак, прежде чем читать некоторые основные концепции информатики.

  1. Бинарное дерево - это динамически размещаемая структура (обычно используется для упорядоченного хранения).
  2. Из-за своей природы обход бинарных деревьев обычно рекурсивен;
    Это потому, что линейный обход (через цикл) не является естественным, когда есть два пути цикла.
    • Рекурсивный: это означает функцию, которая вызывает себя.
  3. В старомодных языках управление памятью требует ручного управления памятью.
    • Руководство: означает, что вы должны сделать это самостоятельно.
  4. Когда вы выполняете ручное управление памятью, вам нужно попросить базовую систему освободить каждого члена дерева.
    • Свободно: восстановить память в глобальных poos, чтобы ее можно было использовать повторно, и вам не хватит памяти.
    • Освобождение: это делается путем вызова функции free() и передачи ей указателя, который вы хотите восстановить.
    • Указатель: это как виртуальная палка. В конце это память. Когда вы запрашиваете память, вам дается указатель (виртуальная флешка), который имеет память. Когда вы закончите, вы вернете указатель (виртуальная флешка).

Рекурсивное решение:

freeTree(Node* node)
{
    freeTree(node->left);  
    freeTree(node->right);
    free(node);
}

Проблема в том, что рекурсия означает, что вы неоднократно вызываете одну и ту же функцию. Это увеличивает стек. Растущий стек использует больше памяти. Причина, по которой вы освобождаете дерево, заключается в том, что вы хотите вернуть память, используя больше памяти, контрпродуктивно (даже если вы вернете оба бита памяти назад).

Напоследок вопрос:

Так что проблема заключается в преобразовании приведенной выше рекурсивной версии в линейное решение (чтобы вам не приходилось использовать память).

Дайте тип узла

typedef struct Node Node;
struct Node
{
    Node* left;
    Node* right;
};

Напишите функцию, чтобы освободить дерево этих узлов.

Ограничения:

  • Не может использовать рекурсию (даже косвенно)
  • Невозможно выделить динамическое пространство для отслеживания.

  • Обратите внимание, что есть решение O (n)

Победитель:

  1. Лучшая сложность.
  2. Tie Break 1: Первая отправка
  3. Tie Break 2: Наименьшее количество персонажей.
Мартин Йорк
источник

Ответы:

7

Кажется, очень близко к O (N) для меня:

Это делает ->leftобход дерева в глубину и использует указатель пройденных узлов для отслеживания родителя.

struct Node * node = root;
struct Node * up = NULL;

while (node != NULL) {
    if (node->left != NULL) {
        struct Node * left = node->left;
        node->left = up;
        up = node;
        node = left;
    } else if (node->right != NULL) {
        struct Node * right = node->right;
        node->left = up;
        node->right = NULL;
        up = node;
        node = right;
    } else {
        if (up == NULL) {
            free(node);
            node = NULL;
        }
        while (up != NULL) {
            free(node);
            if (up->right != NULL) {
                node = up->right;
                up->right = NULL;
                break;
            } else {
                node = up;
                up = up->left;
            }
        }
    }
}
Арно Ле Блан
источник
+1 Добавьте галочку для единственного ответа. Это немного сложнее, чем решение, которое я представляю ниже, но очень хорошо.
Мартин Йорк,
4

C99, 94, O (n)

Изменить: все, кажется, относятся к struct Nodeтак же, Nodeкак если бы typedefон это сделал, так что я тоже.

это на самом деле мой первый C гольф. много сегфо.

в любом случае, это требует C99, потому что он использует объявление внутри первого оператора цикла for.

void f(Node*n){for(Node*q;n;n=q)(q=n->left)?n->left=q->right,q->right=n:(q=n->right,free(n));}

даже не используя #define!

этот алгоритм работает, преобразовывая дерево так, чтобы у верхнего узла не было левого потомка, а затем удаляя его и переходя к правому потомку.

например, если мы начнем с дерева

 1
/ \
2 3
 \
 4

алгоритм изменяет указатели так, что дерево будет

2
 \
 1
/ \
4 3

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

гордый хаскеллер
источник
Я не использовал typedef, потому что мой был на C ++ (вы забыли эти небольшие различия между языками). Я обновил вопрос, чтобы он работал одинаково в C и C ++.
Мартин Йорк,
@LokiAstari Я на самом деле не знаю c ++, и я только недавно начал изучать C. Но я знал достаточно, чтобы ответить на это :-)
гордый haskeller
1
Я собираюсь сделать +1 сейчас. Но я до сих пор не понял, как это работает, поэтому я вернусь после Турции. :-)
Мартин Йорк
@LokiAstari в основном использует тот факт, что C смешивает выражения и операторы вместе, чтобы делать вещи, используя только выражения
гордый haskeller
1

C / C ++ / Objective-C 126 символов (включая обязательный завершающий перевод строки)

#define b(t)(t->left||t->right)
void f(Node*r){while(r&&b(r)){Node**p=&r,*c=b(r);while(c)p=&c,c=b(c);free(*p);*p=0;}free(r);}

Не запускается за O (n) время. Но OP не требует этого, так что вот мое решение O (n 2 ).

Алгоритм: спуститься к листу от корня. Отпусти это. Повторяйте, пока нет листьев. Выпустить рут.

Ungolfed:

void freeTree (Node * root) {
    while (root && (root->left || root->right)) {
        Node ** prev = &root;
        Node * curr = root->left || root->right;
        while (curr != 0) {
            prev = &curr;
            curr = curr->left || curr->right;
        }
        free(*prev);
        *prev = 0;
    }
    free(root);
}
Томас Эдинг
источник
К сожалению, это не сработает. Вы не устанавливаете указатель на лист в NULL перед его освобождением. Таким образом, вы будете бесконечно освобождать один и тот же листовой узел и никогда не доберетесь до точки, где вы освободите дерево.
Мартин Йорк,
@LokiAstari: Спасибо, что заметили ошибку. Это должно быть исправлено сейчас (хотя я не проверял код).
Томас Эдинг
1

с ++ 99 O (n)

Циклы здесь отлично подходят для цепочки по списку, но не для иерархии вверх и вниз. user300 справился с этим (я впечатлен), но код трудно читать.

Решение состоит в том, чтобы преобразовать дерево в список.
Хитрость заключается в том, чтобы сделать это одновременно с удалением узлов.

void freeNode(Node* t)
{
    if (t == NULL)
    {   return;
    }

    // Points at the bottom left node.
    // Any right nodes are added to the bottom left as we go down
    // this progressively flattens the tree into a list as we go.    
    Node* bottomLeft    = findBottomLeft(t);


    while(t != NULL)
    {
        // Technically we don't need the if (it works fine without)
        // But it makes the code easier to reason about with it here.
        if (t->right != NULL)
        {
            bottomLeft->left = t->right;
            bottomLeft = findBottomLeft(bottomLeft);
        }
        // Now just free the curent node
        Node*   old = t;
        t = t->left;
        free(old);
    }
}

Node* findBottomLeft(Node* t)
{
    while(t->left != NULL)
    {
        t = t->left;
    }
    return t;
}

Версия для гольфа

void f(Node*t){Node*o,*l=t;for(;t;free(o)){for(;l->left;l=l->left);l->left=t->right;o=t;t=t->left;}}

Гольф Расширенный

void f(Node* t)
{
        Node*o,*l    = t;

        for(;t;free(o))
        {
            for(;l->left;l = l->left);
            l->left = t->right;
            o = t;
            t = t->left;
        }
}
Мартин Йорк
источник