Что означает !temp->left в C?
Я сейчас изучаю бинарные деревья поиска и наткнулся на этот код
void free_tree(Node* root) {
// Deallocates memory corresponding
// to every node in the tree.
Node* temp = root;
if (!temp)
return;
free_tree(temp->left);
free_tree(temp->right);
if (!temp->left && !temp->right) {
free(temp);
return;
}
}
что означает !temp в этом контексте? Означает ли это if temp == NULL? и означает ли это !temp->left или !temp->right означает «если право временного == NULL»? Я немного запутался с этим кодом в целом.
Я пытался искать связанные вопросы, но пока не получил ответов.
Если это полный код для освобождения дерева, я подозреваю, что он не может освободить большую часть дерева и утечек памяти, как сумасшедший. Как сообщается в настоящее время, единственные узлы, которые он действительно освобождает, — это те, у которых нет детей.
Кстати, я не знаю, ваша ли это функция или нет, но она не освободит все дерево, только его листья (нижние узлы) и их родительские узлы будут продолжать указывать на них и могут привести к тому, что ваша программа получит ошибку сегментации. вы можете исправить это, отменив оператор «if (!temp->left && !temp->right)» и освободив узел после вызовов free_tree для левого и правого узлов.
Ответы 2
что означает !temp в этом контексте? Это значит
if temp == NULL?
Здесь ...
Node* temp = root; if (!temp) return;
... да, это означает именно это. В логическом контексте значение типа указателя оценивается как истинное тогда и только тогда, когда оно не равно NULL. То есть pointer != NULL. Оператор ! вычисляет логическое отрицание, поэтому !pointer эквивалентен pointer == NULL.
и означает ли это, что
!temp->leftили!temp->rightозначает «если право на временную == NULL»?
Нет. Оператор -> имеет более высокий приоритет, чем оператор !, поэтому выражение в форме !x->y эквивалентно !(x->y). Из контекста мы можем определить, что temp->left и temp->right обозначают указатели, поэтому !temp->left и !temp->right означают temp->left == NULL и temp->right == NULL соответственно.
Из стандарта C (6.5.3.3 Унарные арифметические операторы)
5 Результат оператора логического отрицания ! равен 0, если значение его операнд сравнивается с неравным 0, 1, если значение его операнда сравнивает равным 0. Результат имеет тип int. Выражение !E эквивалентно (0==E).
и (6.3.2.3 Указатели)
3 Целочисленное константное выражение со значением 0 или подобное выражение, приведенное к типу void *, называется константой нулевого указателя. 66) Если константа нулевого указателя преобразуется в тип указателя, результирующий указатель, называемый нулевым указателем, гарантированно сравнивается неравно указателю на любой объект или функцию.
Итак, эти операторы if
if (!temp)
и
if (!temp->left && !temp->right) {
эквивалентно
if ( temp == NULL )
и
if ( temp->left == NULL && temp->right == NULL ) {
Обратите внимание на то, что ваша функция неверна. Он освобождает память только для членов данных узлов left и right, которые являются нулевыми указателями.
Правильная функция может выглядеть, например, следующим образом.
void free_tree( Node *root )
{
// Deallocates memory corresponding
// to every node in the tree.
if ( root != NULL )
{
free_tree( root->left );
free_tree( root->right );
free( root );
}
}
Хотя будет лучше объявить и определить его следующим образом
void free_tree( Node **root )
{
// Deallocates memory corresponding
// to every node in the tree.
if ( *root != NULL )
{
free_tree( &( *root )->left );
free_tree( &( *root )->right );
free( *root );
*root = NULL;
}
}
После вызова функции исходный указатель на корневой узел, переданный функции по ссылке через указатель на него, будет равен NULL.
Проверка !temp связана с тем, что функции free_tree(temp->left) не проверяют, являются ли значения temp->left нулевыми. Я бы предложил попробовать написать с нуля самостоятельно, потому что реализация кода C у всех сильно отличается друг от друга.