Удалить все бинарное дерево

Реализация двоичного дерева поиска

В ссылочных реализациях структур данных данные хранятся в виде отдельных элементов, связанных между собой указателями. Элементы организованы либо в виде последовательности (списка), либо в виде дерева. Рассмотрим организацию ссылочной структуры данных на основе двоичного дерева поиска.

В двоичном дереве поиска хранятся элементы, которые можно сравнивать между собой при помощи операций «меньше» и «больше», например, это могут быть числа или строки.

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

Пример правильно построенного двоичного дерева поиска:

Благодаря такому представлению, все операции с деревом (поиск элемента, добавление элемента, удаление элемента) выполняются за время, пропорциональное высоте дерева, а не его размеру. Это позволяет (используя специальные алгоритмы балансировки дерева) реализовать эффективные структуры данных типа «множество», в которых все операции осуществляются за $O(\log n)$, где $n$ — количество элементов в множестве.

Объявление классов tree_elem и binary_tree

Для представления одной вершины (узла) двоичного дерева поиска создадим класс tree_elem . У элементов этого класса будут следующие поля:

m_data — данные (число), которые хранятся в этой вершине.

m_left — указатель на левого потомка данной вершины.

m_right — указатель на правого потомка данной вершины.

class tree_elem
public:
int m_data;
tree_elem * m_left;
tree_elem * m_right;
tree_elem(int val)
m_left = NULL; // В С++11 лучше использовать nullptr
m_right = NULL;
m_data = val;
>
>;

Конструктор для данного класса создает элемент, записывает в него переданные данные, левые и правые поддеревья инициализирует нулевыми указателями.

Рассмотрим описание класса binary_tree .

class binary_tree
private:
tree_elem * m_root;
int m_size;
void print_tree(tree_elem *);
void delete_tree(tree_elem *);

public:
binary_tree(int);
~binary_tree();
void print();
bool find(int);
void insert(int);
void erase(int);
int size();
>;

m_root — указатель на корень дерева.

m_size хранит в себе количество элементов в дереве.

Метод find() проверяет, содержится ли данный элемент в дереве, метод print() выводит все элементы поддерева, метод insert() добавляет новый элемент в дерево, метод erase() удаляет значение из дерева, метод size() возвращает значение.

Вспомогательные методы print_tree() и delete_tree() используются в рекурсивных алгоритмах обхода дерева и удаления дерева.

Конструктор

Конструктор класса binary_tree создает дерево из одного элемента. Для простоты будем считать, что в дереве всегда должен быть хотя бы один элемент.

Деструктор

Деструктор должен удалить все элементы дерева, для каждого из них вызвав оператор delete . Для этого реализована рекурсивная процедура delete_tree . Она рекурсивно вызывает себя для удаления левого поддерева, правого поддерева, затем удаляет сам элемент.

Сам деструктор просто вызывает рекурсивную процедуру delete_tree начиная от корня.

void binary_tree::delete_tree(tree_elem * curr)
if (curr)
delete_tree(curr->m_left);
delete_tree(curr->m_right);
delete curr;
>
>

Обход дерева

Обход дерева также реализуется рекурсивной процедурой — сначала зайдем в левое поддерево, потом в правое поддерево.

Метод print() рекурсивно обходит дерево и выводит его элементы в порядке возрастания.

void binary_tree::print()
print_tree(m_root);
cout >

void binary_tree::print_tree(tree_elem * curr)
if (curr) // Проверка на ненулевой указатель
print_tree(curr->m_left);
cout m_data print_tree(curr->m_right);
>
>

Поиск элемента в дереве

Метод find проверяет, содержится ли в дереве элемент со значением key и возвращает true или false . Поиск начинается от корня. Если key меньше того, что хранится в корне — спускаемся в левое поддерево, если больше — то в правое поддерево. Продолжаем до тех пор, пока не найдем нужный элемент, или не дойдем до пустого поддерева.

Добавление элемента в дерево

Метод добавления элемента в дерево аналогичен методу поиска элемента — ищется позиция, где может находиться данный элемент. Если элемент не найден, то нужно создать новый элемент дерева в том месте, где он должен находиться.

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

Удаление элемента из дерева — наиболее сложный из методов. Сначала найдем элемент, который нужно удалить (указатель curr ), указатель parent указывает на его предка.

Если у curr нет левого поддерева (условие curr->m_left == NULL ), то вместо curr можно подвесить его правое поддерево целиком, то есть элемент curr удаляется, а на его место становится его правое поддерево curr->m_right .

Аналогично, если у curr нет правого поддерева, то вместо него можно подвесить целиком левое поддерево.

Самый сложный случай — если у curr есть и левое, и правое поддерево. В этом случае на место элемента curr поставим наименьший элемент, который больше него. Для этого нужно спуститься в правое поддерево элемента curr , и в этом поддереве найти наименьший элемент — для этого будем двигаться указателем всегда в левого потомка текущего элемента, пока не найдем элемент, у которого нет левого потомка. Этот элемент можно удалить той же самой процедурой (т.к. у него нет левого потомка, то это простой случай удаления), а его значение записать на место элемента curr .

void binary_tree::erase(int key)
tree_elem * curr = m_root;
tree_elem * parent = NULL;
while (curr && curr->m_data != key)
parent = curr;
if (curr->m_data > key)
curr = curr->m_left;
>
else
curr = curr->m_right;
>
>
if (!curr)
return;
if (curr->m_left == NULL)
// Вместо curr подвешивается его правое поддерево
if (parent && parent->m_left == curr)
parent->m_left = curr->m_right;
if (parent && parent->m_right == curr)
parent->m_right = curr->m_right;
—m_size;
delete curr;
return;
>
if (curr->m_right == NULL)
// Вместо curr подвешивается его левое поддерево
if (parent && parent->m_left == curr)
parent->m_left = curr->m_left;
if (parent && parent->m_right == curr)
parent->m_right = curr->m_left;
—m_size;
delete curr;
return;
>
// У элемента есть два потомка, тогда на место элемента поставим
// наименьший элемент из его правого поддерева
tree_elem * replace = curr->m_right;
while (replace->m_left)
replace = replace->m_left;
int replace_value = replace->m_data;
erase(replace_value);
curr->m_data = replace_value;
>

Источник

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

Добрый день.
Написал программу, которая ищет в файле неиспользуемые переменные, т.е. те, которые объявлены. Всё в общем-то работает, но препод говорит, что нужно освободить память. Поставил обнуление локальных переменных в конце функций и в 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 минут
Люди добрые, подкиньте мысль, пожалуйста, «автомат» горит!

Источник