С++ для начинающих. Бинарное дерево. Первое знакомство
- Тем, кому очень нужно понять, советую прочитать тему Бинарное дерево – проще чем кажется. Там описано мало, но я считаю, что там описано лучше чем здесь.
Моё знакомство с бинарными деревьями начиналось, вероятно, как и у многих из вас: приблизтельно на таком примере, который демонстрируется в этой статье.
Как правило, у начинающих много вопросов и поначалу, но с появлением необходимости программировать динамические структуры вопросов становится значитильно больше, чем было. На момент написания этой темы я изучал С++ в одиночку, и при первых моих попытках понять, что такое бинарное дерево, у меня определённо возникли сложности. Особенно отпугивало слово рекурсия. Мало того, что оказалось достаточно проблематично отыскать простой код с объяснениями, так в большинстве случаев нарисован рисунок и дан код без комментариев.
Я считаю, что для первого знакомства значения в бинарное дерево достаточно вводить посредством клавиатуры и выводить значения на экран. Остальные функции лучше оставить на после изучения такого фундамента. Вполне может быть, что вы намного умнее меня и быстро схватываете, но есть такие люди, которые медленно развиваются, и им избираемый мной подход очень нужен.
Помимо всего только что сказанного, могу добавить, что для меня найденный код (абсолютно без пояснений) оказался подобием удара кулачного бойца для кулачного бойца. Иногда ведь говорят, что такие бойцы разговаривают кулаками; программисты, значит, должны разговаривать исходным кодом.
|
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 |
//Листинг #1 Бинарное дерево, представление Borland C++ 3.1 #include <iostream.h> #include <conio.h> //Наша структура struct node { int info; //Информационное поле node *l, *r; //Левая и Правая часть дерева }; node *tree = NULL; //Объявляем переменную, тип которой структура Дерево /*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/ void push(int a, node **t) { if ((*t) == NULL) //Если дерева не существует { (*t) = new node; //Выделяем память (*t)->info = a; //Кладем в выделенное место аргумент a (*t)->l = (*t)->r = NULL; //Очищаем память для следующего роста return; //Заложили семечко, выходим } //Дерево есть if (a > (*t)->info) push(a, &(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо else push(a, &(*t)->l); //Иначе кладем его влево } /*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/ void print (node *t, int u) { if (t == NULL) return; //Если дерево пустое, то отображать нечего, выходим else //Иначе { print(t->l, ++u); //С помощью рекурсивного посещаем левое поддерево for (int i=0; i<u; ++i) cout << "|"; cout << t->info << endl; //И показываем элемент u--; } print(t->r, ++u); //С помощью рекурсии посещаем правое поддерево } int main () { int n; //Количество элементов int s; //Число, передаваемое в дерево cout << "введите количество элементов "; cin >> n; //Вводим количество элементов for (int i=0; i<n; ++i) { cout << "ведите число "; cin >> s; //Считываем элемент за элементом push(s, &tree); //И каждый кладем в дерево } cout << "ваше дерево\n"; print(tree, 0); cin.ignore().get(); } |
Первое, на что обращаю внимание, это сама структура Node, которая представляет одно звено нашего будущего дерева. В структуре объявлен информационный элемент и указатели на самую правую и на самую левую часть будущего дерева. Объявляем указатель на нашу структуру (на звено дерева) и во избежание непредвиденных ошибок сразу инициализируем этот указатель указыванием вникуда.
После описания структуры-звена бинарного дерева и объявления на неё указателя, в функции main() пишем стандартные строчки (сколько элементов ввести) и выполняем цикл, на каждом витке которого вводим элемент. Цикл выполняется указанное число раз. При этом нам нужно каждый новый элемент сразу записывать в дерево. С этой целью (записи в дерево) пишем отдельную функцию. В приведенном мной коде написанная функция принимает два параметра. Первый — записываемое значение (сейчас значение — число), второй — указатель на {указатель звена дерева}.
В начале занесения информации двоичное дерево или содержит информацию или еще не заполнялось, поэтому первый шаг — проверка на наличие данных в дереве.
- Если дерево пустое, то надо создать первый элемент. Этот элемент будет корнем дерева. После создания первого элемента надо выделить память для возможных ветвей.
- Если дерево что-то содержит, то проверяется условие, согласно которому мы размещаем в дереве элементы.
Вспомним основное определение бинарного дерева:
- Бинарное дерево — это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причём для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.
При всём этом, если элемент, который мы хотим поместить в дерево, больше чем корневой, то с помощью рекурсивного вызова функции происходит последовательное перемещение элемента в правую часть. Наш элемент прыгает через один как через скакалку пока не найдет своё место. А его место — это то место, где справа элемент или больше чем он сам, или если прыгать больше не через кого. Одним словом "Чехарда". Если записываемый элемент меньше чем корневой, то выполняется такая же "Чехарда", только в левую сторону.
Для того, чтобы отобразить наше бинарное дерево на экране, сначала проверяем, вообще есть ли оно. Если мы не заполним дерево значениями и не заложим семечко (не создадим корень), то дерева в принципе существовать не может, и поэтому отображать будет нечего, но если создали, то используя рекурсивный вызов функции последовательно отображаем все элементы. Кроме того, эта первая проверка будет и сигналом для завершения рекурсивного вызова функции. Ведь если встретится нулевое звено, то произойдёт return, а мы после создания каждого звена очищали память для следующего роста.
Может, кому-то непонятно, зачем использован параметр u. При выводе на экран вы будете видеть палочки, которые выводятся с помощью цикла. Найти в коде это место не трудно. Эти палочки символически обозначают количество узлов. Я пока не писал, но узел дерева, не имеющий потомков, называется лист. В нашем случае у дерева два листа. 0 и 9.
Если кому мало всё это понятно, то чуть ниж моё личное художество. Предположительно пользователь вводит числа и из них строится дерево. То что вводит пользователь появляется поочередно и ищет своё место. Когда число находит свою позицию, то бронирует найденную позицию. Правую часть я не принял во внимание, но там всё заполняется точно также. После заполнения дерева пройтись по нему не составит труда. Каждый шаг прохода обозначен в конце красной цифрой. Если встречаются равные элементы, то они создают что-то похожее на ветку, и эта ветка с каждым элементом увеличивается (в конце обозначено стрелками). При считывании информации с дерева сначала всё собирается с одной ветки, потом со следующей, и так пока "ветки" не закончатся. Присмотритесь к рисунку, может вам получится понять ещё какие-то моменты.
(Пример на рисунке) красные 2 и 3 напутаны местами:
Для визуального восприятия можно посмотреть один из примеров. Достаточно просто использовать код из листинга #2 и посмотреть, как и что получается с бинарным деревом. (автор кода не я). В Borland C++ 3.1 пример работает. Особо сильно в код этого примера можно и не вникать, важнее, чтобы увидели, что же это за чудо такое — бинарное дерево. В принципе, понять как с программой работать — несложно.
|
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 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 |
//Листинг #2 Бинарное дерево, представление Borland C++ 3.1 /*************************************************************************** Vse prava zashisheni :) avtor DEmoN e-mail: tiger_85@bk.ru Nagljadnoe predstavlenie osnovnih operacii nad dvoichnimi derevjami, ispol'zovalas' graficheskaja biblioteka egavga.bgi Realisovano derevo poiska!! Ypravlenie: '+3' dobavit'element v derevo s vesom 3 '-3' ydaljaem is dereva element c vesom 3 **************************************************************************** */ #include <stdlib.h> #include <stdio.h> #include <graphics.h> #include <conio.h> // getch #include <ctype.h> struct tree { char info; //pole dannih struct tree *left; //ykazatel' na levoe podderevo struct tree *right; //ykazatel' na pravoe podderevo }; struct tree *root; // ykazatel' na koren' vsego dereva struct tree *stree (struct tree *root, // ykazatel' na koren' vsego dereva struct tree *r, // ykazatel' na koren' novogo poddereva char info) // pole dannih { if (!r){ r = (struct tree *) malloc(sizeof(struct tree)); if (!r){ printf("Error in memory (1)\n"); exit(0); } r->left = NULL; r->right = NULL; r->info = info; if (!root) return r; if (info<root->info) root->left = r; else root->right = r; return r; } if (info < r->info) stree(r, r->left, info); else stree(r, r->right, info); return root; } void print_tree2(struct tree *r, int x1, // levaja gran X int x2, // pravaja gran X int y0 ) // coord y { int x0, wrkx1, wrkx2, wrky; char buf[20]; int oldcolor; int dy; dy = 50; if (!r) return; x0 = (x1+x2)/2; wrky = y0+dy; if(r->left != NULL){ wrkx1=x1; wrkx2=x0; line(x0,y0,(wrkx1+wrkx2)/2,wrky); print_tree2(r->left,wrkx1,wrkx2,wrky); } if(r->right != NULL){ wrkx1=x0; wrkx2=x2; line(x0,y0,(wrkx1+wrkx2)/2,wrky); print_tree2(r->right,wrkx1,wrkx2,wrky); } //narisovat' uzel oldcolor=getcolor(); setcolor(6); circle(x0,y0,10); setcolor(oldcolor); //nadpisat' uzel sprintf(buf,"%d",r->info); settextjustify(CENTER_TEXT, CENTER_TEXT); outtextxy(x0,y0,buf); } /* realizaciya funkcii poiska */ struct tree *search_tree(struct tree *root, char key){ if(!root) return root; //pustoe derevo while(root->info !=key){ if (key<root->info) root=root->left; else root=root->right; if(root==NULL) break; } return root; } struct tree *dtree(struct tree *root, char key){ struct tree *p, *p2; if(!root) return root; //vershina ne naidena if(root->info==key){ //ydaleniye kornya //pystoe derevo if(root->left == root->right){ free(root); return NULL; }else if(root->left == NULL){ //esli odno iz podderev'ev pusto p = root->right; free(root); return p; }else if(root->right == NULL){ p = root->left; free(root); return p; }else{ // est' oba poddereva p2 = root->right; p = root->right; while(p->left) p=p->left; p->left = root->left; free(root); return p2; } } if(root->info < key) root->right = dtree(root->right,key); else root->left = dtree(root->left,key); return root; } int main (void){ int i; int ch; int num,num2; char buf[20]; int gdriver = DETECT, gmode, errorcode; char s[] = {32, 16,48, 8,24,40,56, 4,12,20,28,36,44,52,60, 2,6,10,14,18,22,26,30,34,38,42,46,50,54,58,62}; // initialize graphics and local variables initgraph(&gdriver, &gmode, ""); // read result of initialization errorcode = graphresult(); if (errorcode != grOk) // an error occurred { printf("Graphics error: %s\n", grapherrormsg(errorcode)); printf("Press any key to halt:"); getch(); exit(1); // terminate with an error code } root = NULL; //nachal'naya inicializaciya dereva //sozdaniye binarnogo dereva is massiva s[] for(i=0;i<sizeof(s)/sizeof(*s);i++) root = stree(root, root, s[i]); // sizeof(s)/sizeof(*s) - kol-vo elementov //pechat' ishodnogo massiva v vide binarnogo dereva (vizualiz.) print_tree2(root, 1, getmaxx(), 40); settextjustify(LEFT_TEXT, TOP_TEXT); outtextxy(100,350,"Vvedte operaciju(+-) i nomer. ESC-vyhod."); for(;;){ ch = getch(); if(ch==27) break; //ESC if(ch=='+'){ buf[0]='+'; num=0; i=1; settextjustify(LEFT_TEXT, TOP_TEXT); for(;;){ buf[i]='\0'; outtextxy(200,400,buf); ch = getch(); if(isdigit(ch)){ num2 = num*10+ch-'0'; if(num2>0 && num2<64){ num=num2; buf[i++]=ch; } }else if(ch==27){ //ESC cleardevice(); print_tree2(root, 1, getmaxx(), 40); settextjustify(LEFT_TEXT, TOP_TEXT); outtextxy(100,350,"Vvedte operaciju(+-) i nomer. ESC-vyhod."); break; }else if(i!=1 && ch=='\r'){ //proverit' otsutstvie i dobavit' v derevo if(search_tree(root, num)==NULL){ root = stree(root, root, num); cleardevice(); print_tree2(root, 1, getmaxx(), 40); settextjustify(LEFT_TEXT, TOP_TEXT); outtextxy(100,350,"Vvedte operaciju(+-) i nomer. ESC-vyhod."); break; }else{ cleardevice(); print_tree2(root, 1, getmaxx(), 40); settextjustify(LEFT_TEXT, TOP_TEXT); outtextxy(100,350,"Vvedte operaciju(+-) i nomer. ESC-vyhod."); break; } } } } if(ch=='-'){ buf[0]='-'; num=0; i=1; settextjustify(LEFT_TEXT, TOP_TEXT); for(;;){ buf[i]='\0'; outtextxy(200,400,buf); ch = getch(); if(isdigit(ch)){ num2 = num*10+ch-'0'; if(num2>0 && num2<64){ num=num2; buf[i++]=ch; } }else if(ch==27){ //ESC cleardevice(); print_tree2(root, 1, getmaxx(), 40); settextjustify(LEFT_TEXT, TOP_TEXT); outtextxy(100,350,"Vvedte operaciju(+-) i nomer. ESC-vyhod."); break; }else if(i!=1 && ch=='\r'){ if(search_tree(root, num)!=NULL){ root = dtree(root, num); cleardevice(); print_tree2(root, 1, getmaxx(), 40); settextjustify(LEFT_TEXT, TOP_TEXT); outtextxy(100,350,"Vvedte operaciju(+-) i nomer. ESC-vyhod."); break; }else{ cleardevice(); print_tree2(root, 1, getmaxx(), 40); settextjustify(LEFT_TEXT, TOP_TEXT); outtextxy(100,350,"Vvedte operaciju(+-) i nomer. ESC-vyhod."); break; } } } } } closegraph(); return 0; } |
23 комментария на «“С++ для начинающих. Бинарное дерево. Первое знакомство”»
Добавить комментарий
Случайная книга в электронном формате
Здравствуйте простите но вот возник вопрос о
print(tree,0);
почему здесь нужен 0, а не другое число потому что я подставлял разные числа и результат тот же. Объясните пожалуйста.
То есть если бы левая часть или правая делились на две ветки было бы 2 или больше узлов?
То мы начинаем отображение с начала древа которое только начинает создаваться и имеет 0 узлов потом 1 узел, 2 узла и более, и так далее?
Не так выразился.Сначала печатаеться елемент который имеет 1 узел (левый) то есть корень указывает на левый елемент получаеться 1 узел и делее идем подключаеться ищё один узел то есть второй и так далее? Я правильно понял?
Извените за то что запутал и за множество вопросов.
Как бы щитаеться количество узлов от корня к следующему елементу и все? И естествено беруться кратчайшие пути.
О функции печати понял. Вот еще один вопрос. Указатель на указатель позволяет менять елемент на который он указывает?
Большущее спасибо за помощ, и отличные ответы. Теперь вроде все понял.
😈
Совсем не понял про «|», не могли бы объяснить подробнее и понятнее?)
В комментариях написано уже, что это количество звеньев по кратчайшему пути. (отсчет от единицы)
Количество символов | = количество звеньев.
Смотрите на анимированный рисунок. Лучше всего сделайте из рисунка один скрин готового (полного) дерева.
Вообразите, что кружок с цифрой — это остановка.
Запустите воображаемый маршрутный автобус с точки, обозначеной красной цифрой 8, по кратчайшему пути до определенного места и посчитайте сколько он остановок проедет.
Количество символов | как раз и будет количеством таких остановок. до пункта назначения.
____________________________
некоторую путаницу может внести, что в примере есть одинаковые числа внутри дерева. При выводе на экран смотрите для каждого одинакового числа, а не только от первого попавшегося.
в примере всего остановок 8. ввод 5,4,0,1,2,5,1,3 (как появляются так и вводятся)
Добро деятель, прошу вашей помощи !
вот кусок кода , в нем непонятно как работает оператор ретёрн , он же должен делать выход из функции, а получается так , что есле условие
(Т == НУЛЛ) после вызова рекурсии( print(t->l); ) истинно , то выполняется оператор Cout , а не передача уравления в точку вызова функции , почему ??
вот код :
void print (node *t)
{
if (t == NULL) return; //Если дерево пустое, то отображать нечего, выходим
else //Иначе
{
print(t->l);//С помощью рекурсивного посещаем левое поддерево
cout<info<r); //С помощью рекурсии посещаем правое поддерево
}
вообще-то я не знаю что у вас за
и вопроса не понял.
return не может не делать выход из функции. тут он тоже делает только выход из функции и ничего другого.
================
если вы изначально не инициализируете первое звено дерева значением NULL, то при пустом дереве первый return выполнен не будет.
если вы инициализируете первое звено дерева значением NULL, Но не введете в дерево новых звеньев, то оператор return будет выполнен сразу, ибо ваш t==NULL (как пустое первое звено)
если вы внесете в первое звено дерева какие-то значения, то (согласно моему примеру) при помощи new первое звено дерева будет не NULL (t!=NULL), т.е. return для первого звена пропустится
это же относится ко всем последующим звеньям.
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print (node *t,int u)
{
if (t==NULL) return; //Если дерево пустое, то отображать нечего, выходим
else //Иначе
{
print(t->l,++u);//С помощью рекурсивного посещаем левое поддерево
for (int i=0;i<u;++i) cout<<"|";
cout<info<r,++u); //С помощью рекурсии посещаем правое поддерево
}
ну вот же ваш пример, который обходит дерево и печатает содержимое , я смотрел как работает ретёрн в дебагере , все не так как вы говорите.После того , как т== нулл выполняется цикл,потом сиаут,потом рекурсия на правое поддерево, потом проверка Т==нулл!!!опять кусок кода куда-то пропал , и сиаут битый , было так !!
void print (node *t,int u)
{
if (t==NULL) return; //Если дерево пустое, то отображать нечего, выходим
else //Иначе
{
print(t->l,++u);//С помощью рекурсивного посещаем левое поддерево
for (int i=0;i<u;++i) cout<<"|";
cout < info <r, ++u ); //С помощью рекурсии посещаем правое поддерево
}
понятия не имею что у вас с сайтом, но очень прошу вас помочь мне ! гляньте /*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/ в первом же вашем примере , я ту часть кода пытался скопировать .
чтобы код норм выглядел нужно использовать [phр][/рhp] (только теги руками пишите, а не копируйте отсюда)
это проблемы WordPress
и не знаю я как работает компилятор, что вы в дебаггере видите, что смотрите.
я что вижу, то и говорю. Попробую угадать (в прямом смысле без сарказмов и ироний)
если ниже cout<r написать cout<<"—-\n", а внутри main не добавлять в дерево ни одного элемента, то получим такой результат
потому как return сработает сразу.
Если введете 1 элемент в дерево, то из-за new первое звено дерева будет не NULL, поэтому при выводе на экран будет выведено и «—\n» (от вышенаписанного cout), т.е. return пропускается, т.к. проверка на NULL показывет, что это не NULL и выполняется рекурсивный вызов.
А т.к. при добавлении звена в дерева, подготавливается почва (я это где-то семечками называл), в которую сначала приписывается NULL, то при существующем единственном звене, в текущем вызове определится, что текущее звено пустое, и произойдет возврат в точку вызова без прописывания «—» (т.е. return опять сработает сразу)
Вопрос в том где именно точка вызова функции. Это ведь не простая функция, это куча рекурсивных вызовов. Следовательно возврат происходит не в функцию main, а в рекурсивную функцию, которая предшествовала текущей (вызов ведь оттуда шел, туда и управление отдавать).
——————————
как вот я еще скажу, я не знаю даже. я никогда дебаггером не пользовался.
я не буду отрицать, что я могу быть в чем-то не прав. я все-таки не спец.
Вопрос в том где именно точка вызова функции. Это ведь не простая функция, это куча рекурсивных вызовов. Следовательно возврат происходит не в функцию main, а в рекурсивную функцию, которая предшествовала текущей (вызов ведь оттуда шел, туда и управление отдавать).
—————————–
как вот я еще скажу, я не знаю даже. я никогда дебаггером не пользовался.
я не буду отрицать, что я могу быть в чем-то не прав. я все-таки не спец.
___________________________________________________________________________________
Спасибо большое вам , ретерн передавал управление именно в точку вызова ( вызов рекурсии) а не в мэин(как думал я) именно этого я не понимал , и именно это показывал дебагер. И , кстати, зря вы не пользуетесь дебагером , с помошью него , можно пошагово рассматривать выполнение программы , просматривать что лежит в переменной и как она изменяется при переходе на след. шаг . Это только то , что я умею .
я сейчас не занимаюсь и не изучаю C++, а когда писал темы, то там как-то дебаггер под руку не попался. Да и некоторые проблемы с дебагерами существуют (не везде они удобные).
неумение использовать деббагер я компенсировал тем, что максимально сокращал код и смотрел по выводу на экран. Это немного трудозатратнее чем с деббагером, но все же иногда проще получается и помогает при незнакомых языках.
умение использовать деббагер обязательно в арсенале программистов.
я не занимаюсь С++ и поэтому не использую деббагер. Отсюда следует, что не очень-то и зря я его сейчас не использую))
====================
рад, что смог вам помочь.
Почему?
Почему что?
Помогите пожалуйста с созданием функции по замене самого правого элемента самым левым.
Ох.. спасибо тебе огромное. Динамическое программирование только с помощью твоих статей и освоил. У меня единственный вопрос, который постоянно мучает. Почему в в ф-ю push мы передаем указатель на указатель дерева. В чем разница, если бы мы передали просто указатель?
Когда указатель на указатель передаем оригинал указателя на начало дерева.
Когда просто указатель — создаем копию указателя на начало дерева (другая переменная)
Та же история, что с обычной переменной и переменной по указателю.
Здравствуйте, очень интересная статья, в плане понимания бинарных деревьев.
Дабы ее улучшить предлагаю внести правки в первый листинг.
1. Все-таки такое смешивание plain C кода и C++ выглядит немного странно
2. Тут в комментариях люди пишут, что изучали динамическое выделение памяти по этой статье, тогда лучше будет добавить освобождение памяти.
3. использование приводит к привязке только к microsoft платформе.
4. все-таки передавать указатель на указатель — не обязательно( Ни в коем разе не хочу сказать, что это неправильно, но мне кажется, что так код читается несколько лучше)
5. такой код скомпилится на любой ОС, любой архитектуре(даже 8-битной). я это, например, компилил с помощью GCC на mac os x.
6. Если из этого кода выбросить еще и всю кирилицу, то получим чистый ANSI C89 код
#include <stdio.h> #include <stdlib.h> //Наша структура typedef struct node { int info; //Информационное поле struct node *l, *r; //Левая и Правая часть дерева }* nodeptr; /*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/ nodeptr push(int a, nodeptr t) { if (t==NULL) //Если дерева не существует { t = malloc(sizeof(struct node)); //Выделяем память t->info = a; //Кладем в выделенное место аргумент a t->l = t->r = NULL; //Очищаем память для следующего роста return t; //Заложили семечко, выходим } //Дерево есть if (a > t->info) t->r = push(a, t->r); //Если аргумент а больше чем текущий элемент, кладем его вправо else t->l = push(a, t->l); //Иначе кладем его влево return t; } /*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/ void print (nodeptr t,int u) { if (t == NULL) return; //Если дерево пустое, то отображать нечего, выходим else //Иначе: { int i; print(t->l, ++u); //С помощью рекурсивного посещаем левое поддерево for (i = 0; i < u; ++i) printf("|"); printf("%d\n", t->info); //И показываем элемент u--; } print(t->r, ++u); //С помощью рекурсии посещаем правое поддерево } /*ФУНКЦИЯ ОСВОБОЖДЕНИЯ ПАМЯТИ ДЕРЕВА НА ЭКРАНЕ*/ void freeTree(nodeptr t){ if (t == NULL) return; freeTree(t->l); freeTree(t->r); free(t); } int main (int argc, char** argv) { nodeptr tree = NULL; //Объявляем переменную, тип которой структура Дерево int i; //В ANSI C нельзя объявлять переменную в for int n; //Количество элементов int s; //Число, передаваемое в дерево printf("введите количество элементов "); scanf("%d", &n); //Вводим количество элементов for (i=0; i < n; ++i) { printf("ведите число "); scanf("%d", &s); //Считываем элемент за элементом tree = push(s,tree); //И каждый кладем в дерево } printf("ваше дерево\n"); print(tree,0); freeTree(tree); //Освободить память! return 0; }Привет
Огромное спасибо за код. Я его подробно не смотрел. Как увидел основную идею добавления элемента через рекурсию — сразу ясно все стало. Иногда нет времени писать, приходится брать чужие наработки.
Сайт толковый, по-спартански, ничего лишнего. Тоже, за это, спасибо огромное.
Реальные номера узлов дерева. Все узлы дерева вторичной алгоритма расчета арифметика и программного обеспечения
help????
Почему выполнение кода обрывается после первой итерации цикла в мейне?
Очень полезная информация. Наконец то я нашла то что искала. Спасибо.