Главная страница
Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Пример программы Бинарное дерево.
Для создания дерева будут использованы рекурсивные функции:
dob – для добавления элемента,
pech – для печати элемента дерева.
Элемент дерева будет иметь структуру
#include < iostream.h> struct DEREVO{int info; DEREVO * next_l; DEREVO * next_r; }; void dob (DEREVO * tek, int znach); // прототип функции dobvoid pech (DEREVO *tek); // прототип функции pech void main(){ int i; DEREVO *nach, *tek, *new_n; nach=0; cout < < " \n Вводите значения вершин дерева, 0 - признак окончания ввода "; do { cout < < " \nВведите значение вершины"; cin > > i; if (nach) { // Если дерево не пусто, вызывается функци dob dob(nach, i); } else { // Если дерево пусто создается корень дерева new_n=new DEREVO; new_n-> info=i; new_n-> next_l=0; new_n-> next_r=0; nach=new_n; } } while (i); pech(nach); // Печать} /* Рекурсивная функция dob tek - указатель на текущую вершину дерева, znach - значение, которое необходимо добавить в дерево. Функция dob определяет, в какую ветвь нужно добавить новое значение; если znach меньше текущего значения, то производиться добавление в левую ветвь, иначе - в правую ветвь. Если ветвь нельзя добавить (такая ветвь уже существует), то снова вызывается функция dob. */ void dob (DEREVO * tek, int znach){ int i1; DEREVO *new_n; i1=tek-> info; // Если значение текущего элемента дерева меньше нового элемента if (znach< i1) { if (tek-> next_l) dob (tek-> next_l, znach); else { new_n=new DEREVO; new_n-> info=znach; new_n-> next_l=0; new_n-> next_r=0; tek-> next_l=new_n; } } if (znach> i1) { if (tek-> next_r) dob (tek-> next_r, znach); else { new_n=new DEREVO; new_n-> info=znach; new_n-> next_l=0; new_n-> next_r=0; tek-> next_r=new_n; } }} // Рекурсивная функция pech. void pech (DEREVO *tek){if (tek) { pech(tek-> next_l); cout < < " \n\t" < < tek-> info; pech(tek-> next_r); }}
|