C++ для начинающих Динамические деревья Обходы
Дерево, дерево, дерево… Что за деревья такие, как же понять. Я на такое вообще способен? Такие мысли могут появляться у начинающих программистов. Хорошо когда знаешь английский, а когда не знаешь, то программистам труднее. Я вот не знаю и мне приходится крупицами искать материалы. Но эти крупицы есть! Так с миру по нитке получаются статьи этого блога.
Первый мой шаг по изучению динамических деревьев попал на бинарное дерево. Но бинарное дерево — это такое дерево по определению, в котором все элементы упорядочены. А ведь не обязательно динамическое дерево заполняется с условием, что слева должны быть меньшие, справа большие элементы. Иногда можно видеть разные картинки, на которых нарисованы графы. При этом описание может быть одно и то же, а сама логика на картинках разная. Например при описании обхода дерева меня сначала запутало то что при моем выводе на экран, значения не совпадали с теми, которые на картинке.
Оказалось, что мое дерево бинарное, а на картинке динамическое дерево и просто заполнено по другому (такими же числами как и у меня, просто другой порядок записи данных в звенья)
Вот например так: 
Сейчас я чуть более подробно опишу понятие дерево. Дерево может строится по разному. Например, можно искать первое пустое место и в это самое пустое место записывать элемент. Чтобы зря не городить огород, я опишу только функцию добавления элемента в дерево. На протяжении всей статьи я буду говорить об одном и том же коде, который я приведу целиком чуть позже
Код C++ Создание динамического дерева
|
1 2 3 4 5 6 7 8 9 10 11 12 |
void add(int x,Node *&tree) //В функцию принимается записываемый элемент и указатель на ссылку на структуру. { if (NULL==tree) //если ничего нет { tree=new Node; //выделяем память (как на огороде грядку вскопали почти) tree->l=tree->r=NULL; //очищаем участки для роста tree->x=x; //записали в звено данные } else if (NULL==tree->l) add(x,tree->l); //если слева участок не занят, создаем там подзвено else add(x,tree->r); //если занят, создаем подзвено справа } |
В таком случае дерево будет разрастаться равномерно. На первом уровне один узел, на втором два, на третьем четыре, четвертом восемь и так далее. При этом информация не будет иметь каких-то признаков обработки. Мы инструктировали компилятор, чтобы он писал так, как мы пишем в тетрадках слева направо по чистым местам листов. Это проиллюстрировано рисунком выше.
Вот другой вариант — это создание бинарного дерева, там элементы записываются в совершенно другом порядке. Создание функции добавления я описал в статье Бинарное дерево – проще чем кажется
Код С++ Бинарное дерево
|
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 |
void add_node(int x,Node *&MyTree) //Функция добавления звена в дерево { if (NULL==MyTree) //То, о чем я в самом начале писал. Если дерева нет, то сеем семечко { MyTree=new Node; //Выделяем память под звено дерева MyTree->x=x; //Записываем данные в звено MyTree->l=MyTree->r=NULL; //Подзвенья инициализируем пустотой во избежание ошибок } if (x<MyTree->x) //Если нововведенный элемент x меньше чем элемент x из семечка дерева, уходим влево { if (MyTree->l!=NULL) add_node(x,MyTree->l); //При помощи рекурсии заталкиваем элемент на свободный участок else //Если элемент получил свой участок, то { MyTree->l=new Node; //Выделяем память левому подзвену. Именно подзвену, а не просто звену MyTree->l->l=MyTree->l->r=NULL; //У левого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой MyTree->l->x=x; //Записываем в левое подзвено записываемый элемент } } if (x>MyTree->x) //Если нововведенный элемент x больше чем элемент x из семечка дерева, уходим вправо { if (MyTree->r!=NULL) add_node(x,MyTree->r); //При помощи рекурсии заталкиваем элемент на свободный участок else //Если элемент получил свой участок, то { MyTree->r=new Node; //Выделяем память правому подзвену. Именно подзвену, а не просто звену MyTree->r->l=MyTree->r->r=NULL; //У правого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой MyTree->r->x=x; //Записываем в правое подзвено записываемый элемент } } } |
В бинарном дереве элементы по определению упорядочены, причем слева идут меньшие, справа большие. Конечно это легко поменять, но в таком случае дерево перестанет быть бинарным.
С помощью рекурсии в бинарном дереве происходит выталкивание записываемого элемента из занятых участков на свободный. Когда элемент находит свободный участок, под звено дерева выделяется память и расчищаются участи под дальнейший рост. В свежеиспеченное звено записывается элемент.
С добавлением информации в динамические деревья более менее разобрались. Кроме ввода данных, существуют разные алгоритмы обработки деревьев. Среди таких алгоритмов часто встречаются понятия обхода деревьев. Это первое, что должно вас интересовать, потому что на первых порах вам будет нужно выводить данные дерева на экран и это то, оно самое. Алгоритмы обхода деревьев используют по разным причинам и в разных целях, но независимо от этого вы должны понимать как обходы работают.
Для того чтоб описать функции обхода деревьев, я покажу их кодом. Предполагается, что обход дерева — это функция отображения дерева, поэтому опишу внутри функции.
|
1 2 3 4 5 6 7 8 9 |
/*ОБХОД В ПРЯМОМ ПОРЯДКЕ*/ void Show(Node *&tree) { if (NULL==tree) return; //Если дерева нет, выходим cout<<tree->x<<endl; //Посетили узел Show(tree->l); //Обошли левое поддерево Show(tree->r); //Обошли правое поддерево } |
|
1 2 3 4 5 6 7 8 9 |
/*СИММЕТРИЧНЫЙ ОБХОД*/ void Show(Node *&tree) { if (NULL==tree) return; //Если дерева нет, выходим Show(tree->l); //Обошли левое поддерево cout<<tree->x<<endl; //Посетили узел Show(tree->r); //Обошли правое поддерево } |
|
1 2 3 4 5 6 7 8 9 10 |
/*ОБРАТНЫЙ ОБХОД*/ void Show(Node *&tree) { if (NULL==tree) return; //Если дерева нет, выходим Show(tree->l); //Обошли левое поддерево Show(tree->r); //Обошли правое поддерево cout<<tree->x<<endl; //Посетили узел } |
Нетрудно увидеть и понять разницу.
Есть еще обход в ширину, в котором узлы посещаются уровень за уровнем(N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.
Для реализации используется структура queue — очередь с методами (поставить в очередь, взять из очереди, проверка очереди на пустоту)
Иногда могут потребовать описать восемь методов обхода деревьев. Знаете почему? Потому что кроме использования рекурсии, для поиска пустого узла и записи в него элемента, можно использовать обычные циклы. Их написать чуть сложнее чем написать код с рекурсивным вызовом, но вы должны знать чем отличается использование рекурсии от использования обычных циклов. При хорошем понимании построения деревьев, их обходов использовать обычные циклы должно стать несложной задачей. Но я все-таки сконцентрирую внимание на том что понять попроще
Код С++ Создание бинарного дерева Обход в прямом порядке
|
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 |
#include <iostream.h> //=====НАША СТРУКТУРА======== struct Node { Node *l,*r; //левое и правое поддерево int x; //Некоторые данные }; /*ФУНКЦИЯ ДОБАВЛЕНИЯ ЗВЕНА В ДЕРЕВО*/ void add(int x,Node *&MyTree) //Функция добавления звена в дерево { if (NULL==MyTree) //То, о чем я в самом начале писал. Если дерева нет, то сеем семечко { MyTree=new Node; //Выделяем память под звено дерева MyTree->x=x; //Записываем данные в звено MyTree->l=MyTree->r=NULL; //Подзвенья инициализируем пустотой во избежание ошибок } if (x<MyTree->x) //Если нововведенный элемент x меньше чем элемент x из семечка дерева, уходим влево { if (MyTree->l!=NULL) add(x,MyTree->l); //При помощи рекурсии заталкиваем элемент на свободный участок else //Если элемент получил свой участок, то { MyTree->l=new Node; //Выделяем память левому подзвену. Именно подзвену, а не просто звену MyTree->l->l=MyTree->l->r=NULL; //У левого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой MyTree->l->x=x; //Записываем в левое подзвено записываемый элемент } } if (x>MyTree->x) //Если нововведенный элемент x больше чем элемент x из семечка дерева, уходим вправо { if (MyTree->r!=NULL) add(x,MyTree->r); //При помощи рекурсии заталкиваем элемент на свободный участок else //Если элемент получил свой участок, то { MyTree->r=new Node; //Выделяем память правому подзвену. Именно подзвену, а не просто звену MyTree->r->l=MyTree->r->r=NULL; //У правого подзвена будут свои левое и правое подзвенья, инициализируем их пустотой MyTree->r->x=x; //Записываем в правое подзвено записываемый элемент } } } /*ОБХОД В ПРЯМОМ ПОРЯДКЕ*/ void Show(Node *&tree) { if (NULL==tree) return; //Если дерева нет, выходим cout<<tree->x<<endl; //Посетили узел Show(tree->l); //Обошли левое поддерево Show(tree->r); //Обошли правое поддерево } void main() { int x; //Некоторые данные Node *MyTree=NULL; //Указатель на нашу структуру. Инициализируем во избежание ошибок for (int i=0;i<7;i++) //В дереве будет 7 узлов { cout<<"X = "; cin>>x; //Ввели X с клавиатуры add(x,MyTree); //Добавили X в дерево } Show(MyTree); //Обошли дерево и показали его звенья в линейном порядке } |
============
Звенья будут отображены не в том порядке, который похож на самую первую анимацию, это потому что последним было создано бинарное дерево, а у бинарного дерева звенья заполняются по своим правилам, совсем не таким как на первой анимации.
===========
Возможно я нарисую рисунок для бинарного дерева и допишу все, что написано, но обещать этого не стану. Вроде и мелочь, но отнимает много времени очень. Пока что материал не полноценен.
Код исправлен и рабочий. Если видите, что ошибки у меня, наверное лучше меня в мои ошибки и тыкать носом. Я за всеми своими огрехами уследить физически не могу.
Случайная книга в электронном формате
Добавить комментарий