Рекурсия и статические переменные.

@emilen · Регистрация: 25.05.2010

Author24 — интернет-сервис помощи студентам

Что - то я запутался. Пытаюсь написать деструктор для своего бинарного дерева поиска, но мне не понятно поведение статических переменных. У меня не заходит в левую ветвь дерева, удаление происходит только правых элементов. Отсюда утечки памяти. Если убрать static у переменных то все правильно удаляется (выводиться, в моем примере). Я правильно понимаю то, что это не хорошо использовать в рекурсивных функциях «обычные» переменные, так как выделяется слишком много памяти под них? Помогите, пожалуйста, разобраться.

C++

template <class Item>
void delete_tree(Node<Item> item[])
{
    if (item != 0) {
        static Node<Item> *right, *left;
        right = item->right;
        left = item->left;
        cout << item->item << " ";
    //  delete item;
        delete_tree(right);
        delete_tree(left);
    }
}

@Thinker · 17.09.2011, 11:06

Удалять надо правильно (с нижних уровней):

delete_tree(right);
delete_tree(left);
delete item;

либо

delete_tree(left);
delete_tree(right);
delete item;

@emilen · 17.09.2011, 11:11 **[ТС]**

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

Удалять надо правильно

С чего вы взяли, что у вас правильно, а у меня не правильно? Вы сначала проверяйте, что пишете, перед тем как выкладывать.

@Thinker · 17.09.2011, 11:15

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

С чего вы взяли, что у вас правильно, а у меня не правильно? Вы сначала проверяйте, что пишете, перед тем как выкладывать.

Не по теме:

Вообще то давно уже проверено временем...

@emilen · 17.09.2011, 11:24 **[ТС]**

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

@easybudda · 17.09.2011, 11:39

emilen, просто из любопытства: а зачем в рекурсивно вызываемой функции удаления узлов дерева статические переменные?

@emilen · 17.09.2011, 11:51 **[ТС]**

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

@Net_Wanderer · 17.09.2011, 12:01

При первом вызове delete_tree (на верхнем уровне рекурсии), right и left присваиваются значения и после того как выполнится строка delete_tree(right); т.е. будет удаленно правое поддрево, переменная left уже не будет содержать прежнего значения и здесь: delete_tree(left); left будет указывать не на левое поддрево, а на что-то другое.

@emilen · 17.09.2011, 12:08 **[ТС]**

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

переменная left уже не будет содержать прежнего значения

Вот, а почему оно не будет содержать значения? Это мне и не понятно.

@Net_Wanderer · 17.09.2011, 12:11

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

Вот, а почему оно не будет содержать значения? Это мне и не понятно.

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

@emilen · 17.09.2011, 12:15 **[ТС]**

Net_Wanderer, большое спасибо, наконец то до меня дошло. А можете предложить свой вариант решения проблемы? Использовать локальные переменные?

@Net_Wanderer · 17.09.2011, 12:39

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

Net_Wanderer, большое спасибо, наконец то до меня дошло. А можете предложить свой вариант решения проблемы? Использовать локальные переменные?

Да, вот ещё не плохая статья про деревья http://algolist.manual.ru/ds/btree.php.

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	17.09.2011, 11:06	2
	Удалять надо правильно (с нижних уровней): delete_tree(right); delete_tree(left); delete item; либо delete_tree(left); delete_tree(right); delete item; 0

@emilen 10 / 10 / 2 Регистрация: 25.05.2010 Сообщений: 52
	17.09.2011, 11:11 [ТС]	3
	Сообщение от Thinker Удалять надо правильно С чего вы взяли, что у вас правильно, а у меня не правильно? Вы сначала проверяйте, что пишете, перед тем как выкладывать. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	17.09.2011, 11:15	4
	Сообщение от emilen С чего вы взяли, что у вас правильно, а у меня не правильно? Вы сначала проверяйте, что пишете, перед тем как выкладывать. Не по теме: Вообще то давно уже проверено временем... 0

@emilen 10 / 10 / 2 Регистрация: 25.05.2010 Сообщений: 52
	17.09.2011, 11:24 [ТС]	5
	Thinker, ваш вариант, такой же как и мой, только дерево выводиться(удаляется) немного иначе и он так же не работоспособен со статическими переменными. 0

@easybudda Модератор 12458 / 7482 / 1753 Регистрация: 25.07.2009 Сообщений: 13,762
	17.09.2011, 11:39	6
	emilen, просто из любопытства: а зачем в рекурсивно вызываемой функции удаления узлов дерева статические переменные? 0

@emilen 10 / 10 / 2 Регистрация: 25.05.2010 Сообщений: 52
	17.09.2011, 11:51 [ТС]	7
	easybudda, потому что используя не статические переменные при большой глубине рекурсии будет выделено много памяти и возможно переполнение стека, статические переменные должны исправить эту проблему, я правильно понимаю? 0

@Net_Wanderer 237 / 210 / 29 Регистрация: 08.06.2011 Сообщений: 467
	17.09.2011, 12:01	8
	При первом вызове delete_tree (на верхнем уровне рекурсии), right и left присваиваются значения и после того как выполнится строка delete_tree(right); т.е. будет удаленно правое поддрево, переменная left уже не будет содержать прежнего значения и здесь: delete_tree(left); left будет указывать не на левое поддрево, а на что-то другое. 0

@emilen 10 / 10 / 2 Регистрация: 25.05.2010 Сообщений: 52
	17.09.2011, 12:08 [ТС]	9
	Сообщение от Net_Wanderer переменная left уже не будет содержать прежнего значения Вот, а почему оно не будет содержать значения? Это мне и не понятно. 0

@Net_Wanderer 237 / 210 / 29 Регистрация: 08.06.2011 Сообщений: 467
	17.09.2011, 12:11	10
	Сообщение от emilen Вот, а почему оно не будет содержать значения? Это мне и не понятно. Потому что переменные статические, и все рекурсивные вызовы delete_tree работают с одними и теми же переменными. 1

@emilen 10 / 10 / 2 Регистрация: 25.05.2010 Сообщений: 52
	17.09.2011, 12:15 [ТС]	11
	Net_Wanderer, большое спасибо, наконец то до меня дошло. А можете предложить свой вариант решения проблемы? Использовать локальные переменные? 0

	17.09.2011, 12:39

@Net_Wanderer 237 / 210 / 29 Регистрация: 08.06.2011 Сообщений: 467
	17.09.2011, 12:39	12
	Сообщение от emilen Net_Wanderer, большое спасибо, наконец то до меня дошло. А можете предложить свой вариант решения проблемы? Использовать локальные переменные? Да, вот ещё не плохая статья про деревья http://algolist.manual.ru/ds/btree.php. 1