Программа для реализации упорядоченного двоичного дерева
Фрагмент программы для реализации стека
Задача.Создание стека из элементов 9, 10,... 16.
nach=0; // nach - вершина стекаfor (i=9; i<=16; i++) { // Создание очередного элемента new_n=new ELEM; new_n-> info=i;if (nach) { // Если стек не пуст, очередной элемент добавляется в вершину стека new_n-> next=nach; nach=new_n; } else { // иначе стек будет состоять из одного элемента new_n-> next=0; nach=new_n; }Двоичное (бинарное) дерево – это дерево, у каждой вершины которого может быть только два потомка.
Двоичное дерево является самым простым видом дерева. В упорядоченном дереве большее значение располагается справа от вершины, а меньшие значения слева от вершины.
Задача.Построить двоичное упорядоченное дерево из чисел 5, 7, 3, 1, 4.
Первый элемент (5) помещается в корень дерева:
Берем следующий элемент (7). Так как 7 больше 5, помещаем его в правую ветвь от 5:
Берем следующий элемент (3). Так как 3 меньше 5, помещаем его в левую ветвь от 5:
Берем следующий элемент (1). Так как 1 меньше 5 и левая ветвь уже существует (элемент 3), будем сравнивать 1 и 3. 1 меньше 3, поэтому помещаем 1 в левую ветвь от 3.
Берем следующий элемент (4). Так как 4 меньше 5 и левая ветвь уже существует (элемент 3), будем сравнивать 4 и 3. 4 больше 3, поэтому помещаем 4 в правую ветвь от 3. В результате получаем бинарное дерево:
Пример программы "Бинарное дерево".
Для создания дерева будут использованы рекурсивные функции:
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); }}