1

Работаю с бинарным деревом поиска.Создал простую структуру а также объявил тип указателя на структуру:

struct Node {int key;int data;
Node *Left, *Right;};
typedef Node *PNode;

Также я создал глобальную переменную корня этого бинарного дерева PNode koren=NULL;.

Я отладил добавление узлов в дерево и т.д,но возникла проблема с удалением дерева и освобождением памяти.Я не понимаю,что надо посылать в качестве параметра в функцию удаления!Переменную koren типа PNode или адрес переменной koren типа PNode?

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

void udalenie( PNode &koren) {
 if(koren->Left) udalenie(koren->Left);
 if(koren->Right) udalenie(koren->Right); 
 koren=NULL;

} Почему мы должны посылать именно ссылку на участок памяти, где хранится корень?

1
  • В C нет ссылок. Данное объявление функции, представленное вами, не будет компилироваться в C. 15 апр 2019 в 14:48

1 ответ 1

0

Во-первых, в C нет ссылочных типов. Передача по ссылке в C означает передачу через указатель. Поэтому данный код, как C-код, совершенно некорректный.

void udalenie( PNode &koren) {
 if(koren->Left) udalenie(koren->Left);
 if(koren->Right) udalenie(koren->Right); 
 koren=NULL;

Если вы имеете в виду действительно C, то объявление структуры и функция могут выглядеть следующим образом

struct Node 
{
    int key;
    int data;
    struct Node *Left, *Right;
};
typedef struct Node *PNode;

void udalenie( PNode *koren )
{
    if ( *koren )
    {
        if ( ( *koren )->Left ) udalenie( &( *koren )->Left );
        if ( ( *koren )->Right ) udalenie( &( * koren )->Right ); 
        *koren = NULL;
    }
}

Какой смысл передавать корневой узел по ссылке ( то есть в данном случае через указатель)? В этом случае вы можете удалять часть поддерева, и тогда узел, ниже которого было удалено поддерево, будет корректно содержать нуль-указатель в своем соответствующем поле (либо Right, либо Left).

struct Node 
{
    int key;
    int data;
    Node *Left, *Right;
};
typedef Node *PNode;

void udalenie( PNode &koren )
{
    if ( koren )
    {
        if ( koren->Left ) udalenie( koren->Left );
        if ( koren->Right ) udalenie( koren->Right ); 
        koren = NULL;
    }
}

Дело в том, что если не передавать корневой узел по ссылке, то он будет передан по значению. То есть функция будет иметь дело с копией значения корневого узла Если же вы имеете в виду C++, то объявление структуры и функции могут выглядеть как

Поэтому данное предложение в функции

koren = NULL;

не изменит значение исходной переменной корневого узла, переданного в функцию, а изменит лишь значение копии переменной.

Параметры функций являются их локальными переменными.

Вы можете представить объявление функции и ее вызов следующим образом

int x = 10;
int *px = &x;

f( px );

//...

void f( /* int *p */ )
{
    p = px;
    int y = 20;

    p = &y;
    // ...
}

То есть внутри функции изменяется ее локальная переменная (параметр) p. Исходный указатель px после вызова функции останется неизменным. Поэтому чтобы изменить именно его, то есть сам указатель px, его следует передавать в функцию по ссылке.

2
  • Благодарю.Хотелось бы задать еще один вопрос.В функции добавления узла к дереву я также подаю в функцию корень не по ссылке,а по значению,но все работает корректно.Возможно я не до конца понимаю суть указателей,но в эту функцию также надо подавать корень по ссылке или нет? 15 апр 2019 в 17:47
  • @ТимурНазаров Это зависит, как вы создаете корень и возвращаете ли вы его из функции или нет. Выц можете задать новый вопрос, разместив вашу функцию добавления элемента и задать соответствующий вопрос. 16 апр 2019 в 13:19

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.