Очистка деревьем (есть код)

[freekyn]

Написал код для создания и отображения дерева (еле еле получилось)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct tree
{
    int data;
    struct tree *left;
    struct tree *right;
} tree_1;
void tree_go(struct tree *tree_1, int max_level, int current)
{
    tree_1=(struct tree*)malloc(sizeof(struct tree));
    tree_1->data=1+rand()%20;
    printf("\nlevel %d: %d", current, tree_1->data);
    if(current==max_level)
    {
        tree_1->left=0;
        tree_1->right=0;
    }
    else
    {
        tree_1->left=(struct tree*)malloc(sizeof(struct tree));
        tree_go(tree_1->left, max_level, current+1);
        tree_1->right=(struct tree*)malloc(sizeof(struct tree));
        tree_go(tree_1->right, max_level, current+1);
    }
}
void clear(struct tree *tree_1, int max_level, int current)
{
    
}
int main()
{
    srand(time(NULL));
    struct tree *data;
    int level=0;
    printf("\nPlease type max level your tree: ");
    scanf("%d", &level);
    
    data=(struct tree*)malloc(sizeof(struct tree));
    tree_go(data, level, 1);
    // clear tree
    printf("\n\nThe end");
    return 0;
}

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

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

если возможно напишите пример кода =/ на словах очень сложно понять

[Abstraction]

Да пожалуйста. Предположим, добрая фея пообещала нам, что после вызова функции clean(struct tree* t) дерево t будет удалено. Тогда... напишем функцию clean:

void clean(struct tree* t){
  if(t==NULL) return; //А чего чистить-то тогда?

  clean(t->left);//Фея пообещала: дерево t->left удалено
  clean(t->right);
  //Поддеревья t удалены, осталось освободить сам t
  free(t); 
}

Легко видеть, что эта функция очищает дерево глубины 0 (невелика работа).
Также, если эта функция очищает дерево глубины n, то её вызов для дерева глубины n+1 очистит её поддеревья (глубины n) и удалит само дерево; таким образом, если функция очищает дерево глубины n, то она очищает дерево глубины n+1.
Если Вы знакомы с принципом математической индукции, то всё должно быть уже понятно. Если ещё незнакомы - это он:

Если верно R(0) и ( R(n) => R(n+1) для любого натурального n ), то для любого натурального k, R(k) верно.

В нашем случае, функция clean() очищает дерево произвольной глубины.

[freekyn]

Сообщение от Abstraction

Да пожалуйста. Предположим, добрая фея пообещала нам, что после вызова функции clean(struct tree* t) дерево t будет удалено. Тогда... напишем функцию clean:

void clean(struct tree* t){
  if(t==NULL) return; //А чего чистить-то тогда?

  clean(t->left);//Фея пообещала: дерево t->left удалено
  clean(t->right);
  //Поддеревья t удалены, осталось освободить сам t
  free(t); 
}

Легко видеть, что эта функция очищает дерево глубины 0 (невелика работа).
Также, если эта функция очищает дерево глубины n, то её вызов для дерева глубины n+1 очистит её поддеревья (глубины n) и удалит само дерево; таким образом, если функция очищает дерево глубины n, то она очищает дерево глубины n+1.
Если Вы знакомы с принципом математической индукции, то всё должно быть уже понятно. Если ещё незнакомы - это он:

Если верно R(0) и ( R(n) => R(n+1) для любого натурального n ), то для любого натурального k, R(k) верно.

В нашем случае, функция clean() очищает дерево произвольной глубины.

спасибо,
теперь вопрос, который меня интересует:

разве приведённый вами код не оставит висеть где-то в памяти неочищенные элементы?
Или всё таки проход будет совершённ до конца? А там, если элемент не 0, то произойдёт очищение

[freekyn]

И ешё вопрос:

итоговый код

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int i=0;
struct tree
{
    int data;
    struct tree *left;
    struct tree *right;
} tree_1;
void tree_go(struct tree *tree_1, int max_level, int current, int summ)
{
    tree_1=(struct tree*)malloc(sizeof(struct tree));
   // i++;
    tree_1->data=1+rand()%20;
    printf("\nlevel %d: %d", current, tree_1->data);
    if(current==max_level)
    {
        tree_1->left=NULL;
        tree_1->right=NULL;
    }
    else
    {
        tree_1->left=(struct tree*)malloc(sizeof(struct tree));
        tree_go(tree_1->left, max_level, current+1, summ);
        tree_1->right=(struct tree*)malloc(sizeof(struct tree));
        tree_go(tree_1->right, max_level, current+1, summ);
    }
   // printf("\ni1=%d", i);
}
void clean(struct tree* tree_1){
    if(tree_1==NULL) return;
    
    clean(tree_1->left);
    clean(tree_1->right);
    free(tree_1);
}
int main()
{
    srand(time(NULL));
    struct tree *data;
    int level=0, summ=0;
    printf("\nPlease type max level your tree: "),
    scanf("%d", &level);
    //printf("\nWhat level summ:");
    data=(struct tree*)malloc(sizeof(struct tree));
    tree_go(data, level, 1, summ);
    clean(data);
    free(data);
    printf("\n\nThe end");
    return 0;
}

в main() я выделял память для элемента data
=> я должен её очистить, но если я пишу free(data); xcode пишет в конце рабочего программы вот такие строчки:

alloc: *** error for object 0x100103bc0: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug

Я так понимаю, что она ругается, что под data ничего выделенно не было, но это же не так

[Abstraction]

в main() я выделял память для элемента data
=> я должен её очистить, но если я пишу free(data);

clean(), как она написана, удаляет переданное дерево целиком, включая корень. Посмотрите на код: вызовется clean(data->left), clean(data->right), free(data).

разве приведённый вами код не оставит висеть где-то в памяти неочищенные элементы?
Или всё таки проход будет совершённ до конца? А там, если элемент не 0, то произойдёт очищение

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

[freekyn]

Сообщение от Abstraction

clean(), как она написана, удаляет переданное дерево целиком, включая корень. Посмотрите на код: вызовется clean(data->left), clean(data->right), free(data).

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

Всё, я вас понял. Спасибо за объяснение и пример

Ещё такой вопрос:
В моём коде вывод элементов дерева происходит в функции их создания.
Я бы хотел отделить их, но я не знаю как совершить проход в новой функции. Ведь если я напишу в ней:

void show_tree(struct tree *tree_1, int max_level, int current)
{
   if(tree_1->data=0) printf("\nend); 
   else 
   {
    тут вывод элемента и рекурсивный вызов фунции
   }
}

то при вызове функции выведется end. Потому что последнее значение tree->data равно 0

А мне вообще нужно сделать вот такой вывод:

1 (первый уровень)
3 6 (второй уровень
5 7 6 7 (третий уровень)
и так далее

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

подскажите, что можно предпринять и как это реализовать =/

[Abstraction]

А мне вообще нужно сделать вот такой вывод:

1 (первый уровень)
3 6 (второй уровень
5 7 6 7 (третий уровень)

Это проблема. Обратите внимание, что вывод правого поддерева "перемешан" с выводом левого поддерева, так что одним вызовом тут не обойдёшься. Введём функцию вычисления глубины дерева (она очень похожа на clear()) :

int tree_depth(const struct tree* t){
  if(t == NULL) return 0;
  return max(tree_depth(t->left), tree_depth(t->right)) + 1;
}

И введём функцию вывода только заданного уровня дерева:

void ouput_tree_level(const struct tree* t, int level){
  if(t == NULL) return;
  if(level == 1){
    printf("%d ", t->data);
    return;
  }

  output_tree_level(t->left, level-1);
  output_tree_level(t->right, level-1);
}

И теперь можно написать функцию output_tree, которая посчитает число уровней и выведет сначала первый уровень, потом второй и т.д.

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

[freekyn]

Сообщение от Abstraction

Введём функцию вычисления глубины дерева (она очень похожа на clear()) :

int tree_depth(const struct tree* t){
  if(t == NULL) return 0;
  return max(tree_depth(t->left), tree_depth(t->right)) + 1;
}

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

И теперь можно написать функцию output_tree, которая посчитает число уровней и выведет сначала первый уровень, потом второй и т.д

да, это посилу.
Но для начала я попробовал вывести допустим третий уровень, (а входные данные были для 4 уровневого дерева). Поробовал проверить, не отображает.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
int i=0;
struct tree
{
    int data;
    struct tree *left;
    struct tree *right;
} tree_1;
void tree_go(struct tree *tree_1, int max_level, int current, int summ)
{
    tree_1=(struct tree*)malloc(sizeof(struct tree));
    //i++;
    tree_1->data=1+rand()%40;
    printf("\nlevel %d: %d", current, tree_1->data);
    if(current==max_level)
    {
        tree_1->left=NULL;
        tree_1->right=NULL;
    }
    else
    {
        tree_1->left=(struct tree*)malloc(sizeof(struct tree));
        tree_go(tree_1->left, max_level, current+1, summ);
        tree_1->right=(struct tree*)malloc(sizeof(struct tree));
        tree_go(tree_1->right, max_level, current+1, summ);
    }
    //printf("\ni1=%d", i);
}
void clean(struct tree* tree_1){
    if(tree_1==NULL) return;
    
    clean(tree_1->left);
    clean(tree_1->right);
    free(tree_1);
}
int tree_depth(const struct tree* tree_1){
    if(tree_1 == NULL) return 0;
    return fmax(tree_depth(tree_1->left), tree_depth(tree_1->right)) + 1;
}
void output_tree_level(const struct tree* tree_1, int level){
    if(tree_1 == NULL) return;
    if(level==1){
        printf("\n ->%d ", tree_1->data);
        return;
    }
    output_tree_level(tree_1->left, level-1);
    output_tree_level(tree_1->right, level-1);
}
int main()
{
    srand(time(NULL));
    struct tree *data;
    int level=0, summ=0;
    printf("\nPlease type max level your tree: "),
    scanf("%d", &level);
    //printf("\nWhat level summ:");
    data=(struct tree*)malloc(sizeof(struct tree));
    tree_go(data, level, 1, summ);
    printf("\nUROVEN 2:");
    output_tree_level(data, 2);
    clean(data);
    printf("\n\nThe end");
    return 0;
}

грустно, ничего не происходит =/

и ещё, если вывести допустим только первый уровень, то выходит, что вершина равна 0:



Вот если примитивным образом вывести 3 уровня (дерева высотой = 3)

[Abstraction]

мне кажется в функции void output_tree_level(const struct tree* tree_1, int level) не хватает вывода на экран? потому что ничего не происходит после рекурсии

Нет, его там хватает.

и ещё, если вывести допустим только первый уровень, то выходит, что вершина равна 0:

Логично, чёрт возьми. Программа выводит всё абсолютно правильно, дерево в Вашем коде будет состоять из одного элемента, и его поле data имеет произвольное значение.
А вот почему это так - подумайте пять минут самостоятельно. Подсказка: при передаче аргумента в функцию по значению, любые изменения аргумента функции не изменят оригинала.

[freekyn]

ну в прочем подсказка это и есть ответ. Начальное значение у меня же 0

Только почему не отображаются все остальные уровни ё-маё?