Разве здесь не будет утечки памяти? Вы рекурсивно вызываете push, при этом в начале вызова выделяете память в куче, но если мы продолжаем вызов рекурсивно, то передаём не созданный объект на куче а просто данные, т.е. заново создаём объект на куче, при этом старый объект остаётся и не освобождается.
Да, действительно, вы правы. Спасибо за замечание. Тогда нужно убрать строку Node_t *newNode = createNode(...); и ниже вместо newNode подставить createNode(...)
@@depdoprogramming2750 Как вариант просто передавать указатель на новую ноду сразу в функцию. типа такого void push(t_tree** root, t_tree* node); ..... int main() .... push(&root, create_node(10)); ....
немного не понимаю, почему когда вы вызываете функцию push, вы передаете указатель на указатель (**), а когда обходите дерево в ширину передаете просто указатель(* )?
Когда мы передаем в функцию аргумент, значение этого аргумента копируется. Тобишь в функцию передается не оригинальный аргумент, а его копия: void incrementA(int a) {a++;} => функция incrementA будет инкрементировать переменную а локально: int a = 1; incrementA(a); print(a) => а по прежнему = 1 Поэтому для того, чтобы изменять значение переменной а вне функции incrementA, в функцию incrementA нужно передавать указатель на a: incrementA(int *a) {*a += 1}. В таком случае: int a = 1; incrementA(&a); print(a); => теперь a=2 ----- Из этого следует: Когда мы передаем в функцию указатель - берется не его оригинальное значение, а его копия. Тобишь: int a = 1; int ptrA = &a; => пускай ptrA имеет условный адресс 0x01 incrementA(&ptrA); => сюда передается копия указателя ptrA. тобишь у указателя в функции incrementA будет уже другой адресc (например 0x01). Несмотря на это и ptrA(0x01) и его копия (0x02) будут указывать на один и тот же обьект в памяти: int ptrA = &a; print(a); // выдаст какой то адресс (например 0x01) void incrementA(int &a) { print(a); // тут уже будет другой адресс (например 0x02) } Несмотря на это и ptrA(0х01) и его копия(0х02) будут указывать на один и тот же адресс в памяти(например 0х03) Вообщем нужно понимать разницу между адрессом самого указателя и адрессом на который указывает укащатель. ----- А теперь: 1. в функции push(BinaryTree **node) нам нужно изменить адресс(именно адресс на который указывает tree, а не значение) внешнего указателя, а не его копии, которая передается в функцию push. Если мы передадим просто указатель BinaryTree *tree = тут_созданное_дерево; // пускай у адресс tree = 0x01, который указывает на обьект Node с адрессом 0х100 push(tree) { // push(BinaryTree *node) print(node) // в переменную node передалась копия указателя tree(0x01) и теперь у этой копии другой адресс (0х02) node = Node с адрессом 0x101 // таким образом мы говорим, указатель node(0x02) = Node(0x101) // Однако node(0x02) это всего лишь копия. Оригинальный указатель tree(0x01) не изменится в таком случае и будет по прежнему указывать на Node(0x100) } // !!!!! нам нужно изменить сам адресс, на который указывает tree, а не значение по адрессу tree. Именно поэтому **tree 2. В функциях обхода дерева нам не нужно изменять значения, которые хранит указатель, поэтому можно обойтись просто копией.
По поводу удаления элемента - я просто создавал новое дерево и добавлял в него все элементы старого дерева, кроме того, что нужно было удалить. Потом старое дерево зачищал. Наверное это не самый эффективный способ и есть алгоритмы получше. www.cyberforum.ru/c-beginners/thread273988.html - вот тут вроде описано как это сделать
Это прикольно. Но я пока не вижу идеи, данных, при которой нужно такое хранение данных :) Ибо в основном есть данные, которые нужно хранить не меняя последовательность. Или это высшая математика? И ..... даже варианта нет для чего бинарное дерево?
Например в с++ контейнер std::map реализован с помощью бинарного дерева. + бинарного дерева в том, что скорость поиска элемента в нем O(logN), что достаточно быстро. Если элементы хранить в обычном списке, то скорость поиска элементов там - O(n). Короче, бинарное дерево еффективно для поиска элементов в нем.
Ситуация в которой используется бинарное дерево: когда ты добавляешь элементы нечасто, но обращаешся к элементам бинарного дерева часто. Например ты создал какую-то условную базу даных в динамиеской памяти и потом постоянно обращаешся к ее элементам. В таком случае бинарное дерево будет эффективным. куда более еффективным чем обычный список
+ это же структура даних и она уже скорее всего реализована во многих языках программирования. навряд ли тебе прийдется создавать бинарное дерево для каких то практических задач.
@@depdoprogramming2750 В примере с цифрами до меня это не донеслось ;) Таким образом данные делятся для поиска, хотя бы пополам. Хотя я до конца еще не понял схему ;) но интересно.
Разве здесь не будет утечки памяти? Вы рекурсивно вызываете push, при этом в начале вызова выделяете память в куче, но если мы продолжаем вызов рекурсивно, то передаём не созданный объект на куче а просто данные, т.е. заново создаём объект на куче, при этом старый объект остаётся и не освобождается.
Да, действительно, вы правы. Спасибо за замечание.
Тогда нужно убрать строку Node_t *newNode = createNode(...);
и ниже вместо newNode подставить createNode(...)
@@depdoprogramming2750 Как вариант просто передавать указатель на новую ноду сразу в функцию.
типа такого void push(t_tree** root, t_tree* node);
.....
int main()
....
push(&root, create_node(10));
....
А будет видео про графы? Список смежности, обход в ширину в глубину с использованием очереди? Алгоритм Прима и Краскала?
Пока ничего не планировал. Возможно
немного не понимаю, почему когда вы вызываете функцию push, вы передаете указатель на указатель (**), а когда обходите дерево в ширину передаете просто указатель(* )?
Когда мы передаем в функцию аргумент, значение этого аргумента копируется. Тобишь в функцию передается не оригинальный аргумент, а его копия: void incrementA(int a) {a++;} => функция incrementA будет инкрементировать переменную а локально:
int a = 1;
incrementA(a);
print(a) => а по прежнему = 1
Поэтому для того, чтобы изменять значение переменной а вне функции incrementA, в функцию incrementA нужно передавать указатель на a: incrementA(int *a) {*a += 1}. В таком случае:
int a = 1;
incrementA(&a);
print(a); => теперь a=2
-----
Из этого следует:
Когда мы передаем в функцию указатель - берется не его оригинальное значение, а его копия. Тобишь:
int a = 1;
int ptrA = &a; => пускай ptrA имеет условный адресс 0x01
incrementA(&ptrA); => сюда передается копия указателя ptrA. тобишь у указателя в функции incrementA будет уже другой адресc (например 0x01). Несмотря на это и ptrA(0x01) и его копия (0x02) будут указывать на один и тот же обьект в памяти:
int ptrA = &a;
print(a); // выдаст какой то адресс (например 0x01)
void incrementA(int &a) {
print(a); // тут уже будет другой адресс (например 0x02)
}
Несмотря на это и ptrA(0х01) и его копия(0х02) будут указывать на один и тот же адресс в памяти(например 0х03)
Вообщем нужно понимать разницу между адрессом самого указателя и адрессом на который указывает укащатель.
-----
А теперь:
1. в функции push(BinaryTree **node) нам нужно изменить адресс(именно адресс на который указывает tree, а не значение) внешнего указателя, а не его копии, которая передается в функцию push.
Если мы передадим просто указатель
BinaryTree *tree = тут_созданное_дерево; // пускай у адресс tree = 0x01, который указывает на обьект Node с адрессом 0х100
push(tree) { // push(BinaryTree *node)
print(node) // в переменную node передалась копия указателя tree(0x01) и теперь у этой копии другой адресс (0х02)
node = Node с адрессом 0x101 // таким образом мы говорим, указатель node(0x02) = Node(0x101)
// Однако node(0x02) это всего лишь копия. Оригинальный указатель tree(0x01) не изменится в таком случае и будет по прежнему указывать на Node(0x100)
}
// !!!!! нам нужно изменить сам адресс, на который указывает tree, а не значение по адрессу tree. Именно поэтому **tree
2. В функциях обхода дерева нам не нужно изменять значения, которые хранит указатель, поэтому можно обойтись просто копией.
@@depdoprogramming2750 Спасибо Вам за ответ! Теперь все понятно
А вы можете еще, пожалуйста, написать функции удаления элемента без балансировки и очищение дерева?
Вот очистка дерева:
void deleteTree(bTree_t **tree) {
if (*tree != NULL) {
if ((*tree)->left != NULL) {
deleteTree(&(*tree)->left);
}
if ((*tree)->right != NULL) {
deleteTree(&(*tree)->right);
}
free(*tree);
*tree = NULL;
}
}
По поводу удаления элемента - я просто создавал новое дерево и добавлял в него все элементы старого дерева, кроме того, что нужно было удалить. Потом старое дерево зачищал. Наверное это не самый эффективный способ и есть алгоритмы получше.
www.cyberforum.ru/c-beginners/thread273988.html - вот тут вроде описано как это сделать
@@depdoprogramming2750 спасибо большое))
Спасибо, было интересно, надеюсь видео про стек тоже будет
Здравствуй уважаемый подписчик! Видео о стеке уже есть у меня на канале:
ruclips.net/video/iUG7G1B_bhQ/видео.html
Приятного просмотра.
@@depdoprogramming2750 вот это поворот, уже ушел смотреть
Это прикольно.
Но я пока не вижу идеи, данных, при которой нужно такое хранение данных :)
Ибо в основном есть данные, которые нужно хранить не меняя последовательность.
Или это высшая математика? И ..... даже варианта нет для чего бинарное дерево?
Например в с++ контейнер std::map реализован с помощью бинарного дерева. + бинарного дерева в том, что скорость поиска элемента в нем O(logN), что достаточно быстро. Если элементы хранить в обычном списке, то скорость поиска элементов там - O(n).
Короче, бинарное дерево еффективно для поиска элементов в нем.
Ситуация в которой используется бинарное дерево: когда ты добавляешь элементы нечасто, но обращаешся к элементам бинарного дерева часто.
Например ты создал какую-то условную базу даных в динамиеской памяти и потом постоянно обращаешся к ее элементам. В таком случае бинарное дерево будет эффективным. куда более еффективным чем обычный список
+ это же структура даних и она уже скорее всего реализована во многих языках программирования. навряд ли тебе прийдется создавать бинарное дерево для каких то практических задач.
@@depdoprogramming2750 В примере с цифрами до меня это не донеслось ;)
Таким образом данные делятся для поиска, хотя бы пополам.
Хотя я до конца еще не понял схему ;)
но интересно.
бинарное дерево поиска !
Прикол с индусом 10/10
ну не пишут так на Си. это какойто Си++ стиль. для Си++ код ну более мене норм.
Но на Си... За такое сразу увольнение с волчьим билетом.
та не страшно, на сво берут и с волчьими билетами и с петушиными. без работы не останусь😌
@@depdoprogramming2750 Да не не надо так мрасно
Си++ сейчас в поочёте.. Деньги будете грести лопатой