Удаление дерева из памяти

• Var proot,p:Ptree; //

Ввиду своеобразной организации эффективность поиска информации в такой динамической структуре данных сравнима

с эффективностью двоичного поиска в массиве, т.е. имеет оценку эффективности О(log 2 n) . Заметим что двоичный поиск в линейном связанном списке организовать невозможно, а эффективность линейного поиска имеет порядок О(n) . Конечно, оценка О(log 2 n) справедлива для сбалансированного дерева , т.е. такого у которого узлы, имеющие только одну дочь, имеют глубину равную или на единицу меньшую глубины дерева .

Сбалансированное и несбалансированное деревья

Основные операции с бинарным деревом поиска

обход дерева; вставка информации с новым значением ключа не изменяя свойств дерева поиска; формирование сбалансированного дерева поиска; поиск заданного ключа; поиск минимального (максимального) ключа; удаление информации с заданным ключом; удаление дерева .

Класс для работы с деревом

• Type • Ttree=^Tree

•	Tree=Record
•	Inf:TInf;
•	A1,A2:Ttree;

• end; • TBtr=Class(tobject)

•	proot,p,q,v,w : Ttree ;
•	Constructor Create ;
•	Procedure Wrt1 ;
•	Procedure Add (Inf:TInf);
•	Function poisk (k:Tkey):TInf;
•	Procedure Make (a:Tms;n:word);
•	. . . . . . . . . . . .
•	Destructor Free ;

• end;

Работа с деревом

• Var tr:TBtr; • Begin • . . . . • tr:=TBtr. Create ; • tr. Add (inf); • tr. Wrt1; • . . . . • tr. Free ;

Создать дерево

Источник

Освобождение памяти, удаление бинарного дерева

Добрый день.
Написал программу, которая ищет в файле неиспользуемые переменные, т.е. те, которые объявлены. Всё в общем-то работает, но препод говорит, что нужно освободить память. Поставил обнуление локальных переменных в конце функций и в main, но этого не достаточно. Со слов препода: «После каждого вызова функции дерево разрушается, затем строится с нуля, затем передаётся в следующую функцию».
Код прилагаю

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195

#include #include #include #include #include #define N 200 using namespace std; // описываем дерево struct btree { char name[N]; int count; // число использований переменной struct btree *left, *right; }; // описываем список типов данных struct list { char type[N]; struct list *next; }; //работа со списком list *Ins_first(list *head, char *str) { list *q=new list, *t; strcpy(q->type,str); q->next=NULL; if (head!=NULL) q->next=head; return q; } void Print_list(list *head) { list *t = head; if (head==NULL) {cout"Empty List"endl;} cout"TYPES:"endl; while (t->next!=NULL) { coutt->typeendl; t=t->next; } coutt->typeendl; } list *Create_list() { int i=0; char *Types[] = {"char","define","double","float", "int","long", "FILE"}; list *first=NULL; while (i7) { first=Ins_first(first, Types[i]);Print_list(first); i++; } return first; } //проверка на принадлежность к буквам int Letter(char ch) { if (isalpha(ch)>0) return 1; if (ch=='_') return 1; return 0; } //разбиение на слова int Words (char *String, char w[][N]) { int i=0, j=0, k=0, key=0, n=strlen(String);//i-буквы k-слово if(strstr(String, "(")!=0) {while(String[j]!='(') j++;} // если есть скобки, то всё что до них отсекается, например, если строка - объявление функции for (; jn; j++)//пока j меньше длины строки if (Letter(String[j]) or (String[j]>='0' && String[j]'9' && Letter(String[j-1]))) {w[k][i]=String[j]; i++; key=1; } /*если элемент-слово/почёркивание, формируем массив, с этим словом, плюсуем кол-во букв, счётчик=1*/ else //иначе, если ключ есть, заканчиваем слово if (key) {w[k][i]='\0'; i=0; k++; key=0; } return k; } // Функция проверяет, является ли слово типом данных int Type_Word(char *s, list *head) { list *p=head; while(p!=NULL) { if (strcmp(s,p->type)==0)return 1; p=p->next; } delete p; return 0; } // вставка в дерево void Ins_Btree (char *w, btree **q) { if(*q == NULL) { *q=new btree; (*q)->left=(*q)->right=NULL; strcpy ((*q)->name, w); (*q)->count=1; q=NULL; return; } if (strcmp((*q)->name,w)==0)//строки равны { (*q)->count++; return; } if (strcmp((*q)->name,w)>0) //строка меньше Ins_Btree (w, &(*q)->left); else //строка больше Ins_Btree (w, &(*q)->right); } //Функция выводит всё дерево void Print_Btree (btree *p) { if (p==NULL) return; Print_Btree (p->left); coutp->name" "p->countendl; Print_Btree(p->right); p=NULL; } // Функция выводит только те эл-ты дерева, значение count которых = 1 void Print_Result (btree *p) { if (p==NULL) return; Print_Result (p->left); if(p->count==1) coutp->name" "p->countendl; Print_Result(p->right); p=NULL; } // сравнение с уже имеющимися элементами дерева int Compare (char *key, btree **node) // Функция определяет, является ли слово элементом дерева (по сути, укороченная и переделанная функция удаления из дерева) { //cout if(*node == NULL) return 0; if(strcmp((*node)->name,key)==0) {(*node)->count++; return 0;} // если слово является элементом дерева, то счётчик увеличивается, потому что данная переменная где-то использовалась if(strcmp((*node)->name,key)0) {if((*node)->right == NULL) return 0; else return Compare (key, &(*node)->right);} if(strcmp((*node)->name,key)>0) {if((*node)->left == NULL) return 0; else return Compare (key, &(*node)->left);} node = NULL; } // Формирование дерева void Build_tree(FILE *in) { list *L=NULL; // список типов данных L=Create_list(); //cout char str1[N]; // строка для считывания и пр. операций int i=0; btree *q=NULL; // дерево переменных char w[N][N]; int k=0; while(!feof(in)) // цикл по файлу { fgets (str1, N, in); // чтение строки // cout /*разбиение на слова*/ if(strstr(str1, "/*")==0 && strstr(str1, "//")==0) k=Words(str1, w); // если строка не закомментирована, то работаем с ней i=0; while(i!=k) { if(strcmp(w[i], "struct")==0) {L=Ins_first(L, w[i+1]); i++;} // если нашли пользовательский тип данных (слово после struct), добавляем его в список типов /*если первое слово - тип данных, то последующие слова заносятся в дерево*/ if (Type_Word(w[0], L)==1) { /*cout i=1; while(ik) {if(Type_Word(w[i], L)==0 && isalpha(w[i][0])) Ins_Btree(w[i], &q); i++;}} else {while(ik) {if (Type_Word(w[i], L)==1) Ins_Btree(w[i+1], &q); Compare(w[i], &q); i++;}} /*если в "середине" строки нашли тип данных, то следующее слово заносится в дерево а также идёт сравнение слов с элементами дерева*/ } } cout"Tree is: "endl; Print_Btree(q); // вывод всего дерева cout"Result is:"endl; Print_Result(q); // вывод результата q=NULL; L=NULL; return; } int main() {//system( "color 17" ); cout"**************************SEARCH NON USABLE VARIABLES***************************"endl; FILE *f1; btree *root; char filename[N]; while(1) { cout"Enter name of file"endl; gets(filename); f1=fopen(filename, "r"); if(f1==NULL) printf ("Error!"); else break; } Build_tree(f1); root=NULL; fclose(f1); getch(); }

Вообще, основные манипуляции проходят в цикле в функции Build_tree, значит там следует «разрушать и перестраивать» дерево?
Заранее спасибо.

Добавлено через 9 часов 46 минут
Люди добрые, подкиньте мысль, пожалуйста, «автомат» горит!

Источник

Удаление бинарного дерева поиска и освобождение памяти

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

struct Node ; 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 ответ 1

Во-первых, в 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++, то объявление структуры и функции могут выглядеть как

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

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

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

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

int x = 10; int *px = &x; f( px ); //. void f( /* int *p */ ) < p = px; int y = 20; p = &y; // . >

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

Источник