Free бинарного дерева без рекурсии

Question

ссылается на вопрос Deallocating binary-tree structure in C

struct Node{ 
    Node *parent; 
    Node *next; 
    Node *child; 
} 

Я попытался освободить бинарное дерево. Проблема, которую я имею, это выделенные объекты: 5520, а количество вызовов бесплатных функций - 2747. Я не знаю, почему, он должен действительно освобождать и повторять все узлы в дереве, вот код, который я использую

int number_of_iterations =0; 
int number_of_deletions =0; 
    void removetree(Node *node) 
    { 
     number_of_iterations++; 
     while(node != NULL) 
     { 
      Node *temp = node; 

      if(node->child != NULL) 
      { 
       node = node->child; 
       temp->child = node->next; 
       node->next = temp; 
      } 
      else 
      { 
       node = node->next; 
       remove(temp); 
       number_of_deletions++ 
      } 
     } 
    } 

Количество итерации 5440, а число удалений является 2747.

Новый Фиксированный код является то, что код правильно?

const Node *next(const Node *node) 
    { 
     if (node == NULL) return NULL; 
     if (node->child) return node->child; 

     while (node && node->next == NULL) { 
      node = node->parent; 
     } 

     if (node) return node->next; 
     return NULL; 
    } 

for (p= ctx->obj_root; p; p = next(p)) { 
     free(p); 
    } 

Answer 1

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

void removetree(Node *node) 
{ 
    while (node != NULL) 
    { 
    Node *next = node->child; 

    /* If child subtree exists, we have to delete that child subtree 
     first. Once the child subtree is gone, we'll be able to delete 
     this node. At this moment, if child subtree exists, don't delete 
     anything yet - just descend into the child subtree */ 

    node->child = NULL; 
    /* Setting child pointer to null at this early stage ensures that 
     when we emerge from child subtree back to this node again, we will 
     be aware of the fact that child subtree is gone */ 

    if (next == NULL) 
    { /* Child subtree does not exist - delete the current node, 
     and proceed to sibling node. If no sibling, the current 
     subtree is fully deleted - ascend to parent */ 
     next = node->next != NULL ? node->next : node->parent; 
     remove(node); // or `free(node)` 
    } 

    node = next; 
    } 
} 

Answer 2

Я бы

void removeTree(Node *node){ 
    Node *temp; 
    while (node !=NULL){ 
     if (node->child != NULL) { 
      removeTree(node->child); 
     } 
     temp = node; 
     node = node->next; 
     free(temp); 
    } 
} 

Non-рекурсивная версия:

void removeTree(Node *node){ 
    Node *temp; 
    while (node !=NULL){ 
     temp = node; 
     while(temp != node) { 
      for(;temp->child == NULL; temp = temp->child); //Go to the leaf 
      if (temp->next == NULL) 
       free(temp); //free the leaf 
      else { // If there is a next move it to the child an repeat 
       temp->child = temp->next; 
       temp->next = temp->next->next; 
      } 
     } 
     node = temp->next; // Move to the next 
     free(temp) 
    } 
} 

Я думаю, что это должно работать

Answer 3

Почему бы просто не сделать это recurisively?

void removetree(Node *node) { 
    if (node == NULL) { 
    return; 
    } 
    number_of_iterations++; 
    removetree(node->next); 
    removetree(node->child); 
    free(node); 
    number_of_deletions++; 
} 

Answer 4

Реализация не работает для дерева с корнем 1, который имеет одного ребенка 2.

NodeOne.parent = null 
NodeOne.next = null 
NodeOne.child = NodeTwo 

NodeTwo.parent = null 
NodeTwo.next = null 
NodeTwo.child = null 

Выполнение Removetree(NodeOne) не будет вызывать remove на NodeOne.

Answer 5

Вы освобождаете только поддеревья, а не родительские узлы. Предположим, что child представляет собой дочерний элемент left узла, а next - это ребенок right. Тогда ваш код становится:

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

int number_of_iterations =0; 
int number_of_deletions =0; 
    void removetree(Node *node) 
    { 
     number_of_iterations++; 
     while(node != NULL) 
     { 
      Node *temp = node; 

      if(node->left != NULL) 
      { 
       node = node->left; 
       temp->left = node->right; 
       node->right = temp; 
      } 
      else 
      { 
       node = node->right; 
       remove(temp); 
       number_of_deletions++ 
      } 
     } 
    } 

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

   1 
    2    3 
4  5  6   7 

Когда node является корневым узлом, происходит следующее

• node указывает на «1»
• temp указывает на «1»
• node теперь указывает на '2'
• temp->left теперь указывает на '5'
• node->right теперь указывает на «1»

В следующей итерации, вы начинаете с node указывая на «2» и temp также. Как вы можете видеть, вы не удалили узел «1». Это повторится.

Чтобы исправить это, вы можете захотеть использовать BFS и структуру в виде очереди, чтобы удалить все узлы, если вы хотите избежать рекурсии.

Редактировать BFS путь:

1. Создание структуры очереди Q
2. Добавить корневой узел node в Q
3. Добавить левый узел node в Q
4. Добавить правый узел node до Q
5. Free node и удалить его из Q
6. Набора node = первого элемента Q
7. Повторите шаги 3-6 до Q пустеет

Это использует тот факт, что очередь является FIFO структурой.

Answer 6

является бинарное дерево! Это путает людей из-за названий, которые вы выбрали, next распространен в связанном списке, но типы имеют значение, и у вас есть один узел, ссылающийся на два одинаковых типа узлов, и это все, что имеет значение.

Взято отсюда: https://codegolf.stackexchange.com/a/489/15982, с которым вы связались. И я переименовал left в child и right к next :)

void removetree(Node *root) { 
    struct Node * node = root; 
    struct Node * up = NULL; 

    while (node != NULL) { 
     if (node->child != NULL) { 
      struct Node * child = node->child; 
      node->child = up; 
      up = node; 
      node = child; 
     } else if (node->next != NULL) { 
      struct Node * next = node->next; 
      node->child = up; 
      node->next = NULL; 
      up = node; 
      node = next; 
     } else { 
      if (up == NULL) { 
       free(node); 
       node = NULL; 
      } 
      while (up != NULL) { 
       free(node); 
       if (up->next != NULL) { 
        node = up->next; 
        up->next = NULL; 
        break; 
       } else { 
        node = up; 
        up = up->child; 
       } 
      } 
     } 
    } 
} 

Answer 7

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

Я видел неправильный ответ, выбранный как хороший друг, поэтому я попытаюсь показать свой подход:

Начнет с помощью ссылки указателей вместо простых указателей, так как передать ссылку корневого указателя делает его легче обнаружить (и обновить) указатели на корневой узел. Таким образом, интерфейс к подпрограмме будет следующим:

void delete_tree(struct node * * const ref); 

Он представляет ссылку на указатель, указывающий на корневой узел. Я спускаюсь к узлу, и если один из child или next равен NULL, то этот узел можно свободно исключить, просто указав указатель ссылки на другую ссылку (чтобы я не потерял его).Если узел имеет двух детей (child и next оба являются != NULL), то я не могу удалить этот узел до тех пор, пока одна из ветвей не рухнула, а затем я выберу одну из ветвей и переместим ссылку (я объявил параметр refconst, чтобы обеспечить I не изменять его, поэтому я использую другие перемещение ссылки для этого)

struct node **moving_reference; 

Затем алгоритм следует:

void tree_delete(struct node ** const static_ref) 
{ 
    while (*static_ref) { 
     struct node **moving_ref = static_ref; 

     while (*moving_ref) { 
      struct node *to_be_deleted = NULL; 

      if ((*moving_ref)->child && (*moving_ref)->next) { 
       /* we have both children, we cannot delete until 
       * ulterior pass. Just move the reference. */ 
       moving_ref = &(*moving_ref)->child; 
      } else if ((*moving_ref)->child) { 
       /* not both != NULL and child != NULL, 
       * so next == NULL */ 
       to_be_deleted = *moving_ref; 
       *moving_ref = to_be_deleted->child; 
      } else { 
       /* not both != NULL and child == NULL, 
       * so follow next */ 
       to_be_deleted = *moving_ref; 
       *moving_ref = to_be_deleted->next; 
      } /* if, else if */ 
      /* now, delete the unlinked node, if available */ 
      if (to_be_deleted) node_delete(to_be_deleted); 
     } /* while (*moving_ref) */ 
    } /* while (*static_ref) */ 
} /* delete_tree */ 

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

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

#define N 100 

#define D(x) __FILE__":%d:%s: " x, __LINE__, __func__ 

#define ASSERT(x) do { \ 
     int res; \ 
     printf(D("ASSERT: (" #x ") ==> %s\n"), \ 
         (res = (int)(x)) ? "TRUE" : "FALSE"); \ 
     if (!res) exit(EXIT_FAILURE); \ 
} while (0) 

struct node { 
     int key; 
     struct node *child; 
     struct node *next; 
}; /* struct node */ 

struct node *node_alloc(void); 
void node_delete(struct node *n); 

/* This routine has been written recursively to show the simplicity 
* of traversing the tree when you can use recursive algorithms. */ 
void tree_traverse(struct node *n, struct node *p, int lvl) 
{ 
    while(n) { 
     printf(D("%*s[%d]\n"), lvl<<2, p && p == n ? ">" : "", n->key); 
     tree_traverse(n->child, p, lvl+1); 
     n = n->next; 
    } /* while */ 
} /* tree_traverse */ 

void tree_delete(struct node ** const static_ref) 
{ 
    int pass; 

    printf(D("BEGIN\n")); 

    for (pass = 1; *static_ref; pass++) { 
     struct node **moving_ref = static_ref; 

     printf(D("Pass #%d: Considering node %d:\n"), 
         pass, (*moving_ref)->key); 

     while (*moving_ref) { 
      struct node *to_be_deleted = NULL; 

      /* print the tree before deciding what to do. */ 
      tree_traverse(*static_ref, *moving_ref, 0); 

      if ((*moving_ref)->child && (*moving_ref)->next) { 
       printf(D("Cannot remove, Node [%d] has both children, " 
             "skip to 'child'\n"), 
           (*moving_ref)->key); 
       /* we have both children, we cannot delete until 
       * ulterior pass. Just move the reference. */ 
       moving_ref = &(*moving_ref)->child; 
      } else if ((*moving_ref)->child) { 
       /* not both != NULL and child != NULL, 
       * so next == NULL */ 
       to_be_deleted = *moving_ref; 
       printf(D("Deleting [%d], link through 'child' pointer\n"), 
           to_be_deleted->key); 
       *moving_ref = to_be_deleted->child; 
      } else { 
       /* not both != NULL and child != NULL, 
       * so follow next */ 
       to_be_deleted = *moving_ref; 
       printf(D("Deleting [%d], link through 'next' pointer\n"), 
           to_be_deleted->key); 
       *moving_ref = to_be_deleted->next; 
      } /* if, else if */ 

      /* now, delete the unlinked node, if available */ 
      if (to_be_deleted) node_delete(to_be_deleted); 
     } /* while (*moving_ref) */ 
     printf(D("Pass #%d end.\n"), pass); 
    } /* for */ 

    printf(D("END.\n")); 
} /* delete_tree */ 

struct node heap[N] = {0}; 
size_t allocated = 0; 
size_t deleted = 0; 

/* simple allocation/free routines, normally use malloc(3). */ 
struct node *node_alloc() 
{ 
     return heap + allocated++; 
} /* node_alloc */ 

void node_delete(struct node *n) 
{ 
     if (n->key == -1) { 
       fprintf(stderr, 
           D("doubly freed node %ld\n"), 
           (n - heap)); 
     } 
     n->key = -1; 
     n->child = n->next = NULL; 
     deleted++; 
} /* node_delete */ 

/* main simulation program. */ 
int main() 
{ 
     size_t i; 

     printf(D("Allocating %d nodes...\n"), N); 
     for (i = 0; i < N; i++) { 
       struct node *n; 

       n = node_alloc(); /* the node */ 
       n->key = i; 
       n->next = NULL; 
       n->child = NULL; 

       printf(D("Node %d"), n->key); 

       if (i) { /* when we have more than one node */ 
         /* get a parent for it. */ 
         struct node *p = heap + (rand() % i); 

         printf(", parent %d", p->key); 
         /* insert as a child of the parent */ 
         n->next = p->child; 
         p->child = n; 
       } /* if */ 
       printf("\n"); 
     } /* for */ 

     struct node *root = heap; 

     ASSERT(allocated == N); 
     ASSERT(deleted == 0); 

     printf(D("Complete tree:\n")); 
     tree_traverse(root, NULL, 0); 

     tree_delete(&root); 

     ASSERT(allocated == N); 
     ASSERT(deleted == N); 
} /* main */