Дерево - это граф, который характеризуется следующими свойствами: существует единственный элемент (узел или вершина), на который не ссылается никакой другой и который называется корнем; начиная с корня и следуя по определенной цепочке указателей, можно осуществить доступ к любому элементу структуры; на каждый элемент, кроме корня, имеется единственная ссылка. Бинарное дерево – это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев: в левом поддереве содержатся ключи, имеющие значения, меньшие, чем значение данного узла, в правом поддереве содержатся ключи, имеющие значения, большие, чем значение данного узла.
| Задание
| Краткие теоретические сведения
|
| 1. Изучить работу с бинарным деревом, выполнив программу, записанную в правой части. В программе осуществляется добавление элемента в дерево и вывод на экран.
| | # include <iostream>
# include<conio.h>
using namespace std;
struct node
{ int info;//Информационное поле
node *L, *R; };//Левая и правая часть дерева
node* tree= NULL;
void push(int a, node **t)//Добавл. элемента a
{ if ((*t)== NULL)//Если дерева нет
{ (*t)=new node;
(*t)->info = a;
(*t)->L = (*t) ->R =NULL;//Очистка памяти
return; }
if (a>(*t)->info)//Если а больше текущего push(a, &(*t)->R);//то помещается вправо
else push(a, &(*t)->L); }//Иначе - влево
| void Vyvod (node *t, int u)//Вывод на экран
{ if (t == NULL) return; else
{Vyvod(t->L, ++u);//Левое поддерево
for (int i = 0; i < u; ++i) cout<<"|";
cout<<t->info<<endl; u--; }
Vyvod(t->R, ++u); }// Правое поддерево
void main ()
{ setlocale (LC_CTYPE, "Russian");
int n; int s;
cout<<"Введите количество элементов ";
cin>>n;
for (int i = 0; i<n; ++i)
{ cout<<"Введите число "; cin>>s;
push(s, &tree); }
cout<<"ваше дерево\n";
Vyvod(tree, 0); getch(); }
| |
| 2. В правой части приведена программа, которая осуществляет построение бинарного дерева, добавление звена, поиск звена, поиск вершины с ключом и вывод дерева на экран. При вводе ключей вершин признак окончания - ввод 0.
Выполнить программу и написать комментарии к операторам.
| | #include <iostream>
#define TRUE 1
#define FALSE 0
using namespace std;
struct node
{ int Key; int Count;
node *Left; node *Right;
};
node *Tree;//Указатель на корень дерева
node *Res;//Указатель на найденную вершину
int B;//Признак нахождения вершины в дереве
node** GetTree()
{return &Tree; }
void Search (int x, node **p)//Поиск звена x
{ if (*p==NULL)//*p - указатель на вершину
{ *p = new(node);
(**p).Key = x;
(**p).Count = 1;
(**p).Left = (**p).Right = NULL; }
else
if (x<(**p).Key) Search (x, &((**p).Left));
else
if (x>(**p).Key) Search (x,&((**p).Right));
else (**p).Count += 1;
}
void BuildTree ()//Построение бинарного дерева
{
int el;
cout<<"Введите ключи вершин дерева: \n";
cin>>el;
while (el!=0)
{ Search (el, &Tree);
cin>>el;
}
}
void Vyvod (node **w, int l) //Вывод на экран
{
int i;
if (*w!=NULL)//*w - указатель на корень
{
Vyvod (&((**w).Right), l + 1);
for (i = 1; i <= l; i++)
cout<<" ";
cout<<(**w).Key<<endl;
Vyvod (&((**w).Left), l + 1);
}
}
| int Poisk (int k)//Поиск вершины с ключом k
{ node *p,*q; B = FALSE; p = Tree;
if (Tree!=NULL)
do
{ q = p; if ((*p).Key==k) B = TRUE;
else
{q = p;
if (k<(*p).Key) p = (*p).Left;
else p = (*p).Right; }
}
while (!B && p!= NULL);
Res = q;
return B;
}
void Addition (int k)//Добавление звена k
{ node *s; Poisk (k);
if (!B)
{ s = new(node);
(*s).Key = k; (*s).Count = 1;
(*s).Left = (*s).Right = NULL;
if (Tree == NULL) Tree = s;
else
if (k<(*Res).Key) (*Res).Left = s;
else (*Res).Right = s; }
else (*Res).Count += 1;
}
void main ()
{
setlocale (LC_CTYPE, "Russian");
int el;
BuildTree ();
Vyvod(GetTree(), 0);
cout<<"Введите ключ вершины, которую нужно найти в дереве: ";
cin>>el;
if (Poisk (el))
cout<<"В дереве есть такая вершина!\n";
else
cout<<"В дереве нет такой вершины!\n";
cout<<"Введите ключ добавляемой вершины: ";
cin>>el;
Addition (el);
Vyvod (GetTree(), 0);
}
|
|
| 3. Дополнить программу, приведенную в п. 2 функцией удаления вершины (Delete).
Изменить функцию поиска вершины с ключом k так, чтобы она стала рекурсивной.
В главной функции написать операторы, с помощью которых можно продемонстрировать работу новых функций.
| Ниже приведены фрагменты функций, которые нужно дописать, чтобы выполнить задание данного пункта.
| node *Poisk_1 (int k, node **p) //Поиск вершины с ключом k
{ if (*p == NULL) …
else
if ((**p).Key == k) …
else
if (k<(**p).Key) return Poisk_1 (…);
else return …;
}
void Delete_1 (node **r, node **q)//Удаление вершины k из бинарного дерева
{ node *s;
if ((**r).Right == NULL)
{ (**q).Key =…;
(**q).Count = (**r).Count;
*q = …; s = …;
*r = …;
delete s; }
else Delete_1 (&((**r).Right), q);
}
| void Delete (node **p, int k)//Удаление вершины k
{node *q;
if (*p==NULL)
cout<<"Вершина с заданным ключом не найдена!\n";
else
if (k<(**p).Key)
Delete (&((**p).Left), k);
else
if (k>(**p).Key)
…
else
{ q = *p;
if ((*q).Right==NULL)
{*p = (*q).Left;
delete …;}
else
if ((*q).Left == NULL)
{ *p = (*q).Right;
delete …; }
else Delete_1 (&((*q).Left), &q);
}
}
|
|
4. Разработать программу работы с бинарным деревом, в которую включить основные функции манипуляции данными и функцию в соответствии со своим вариантом из таблицы, представленной ниже.
| № варианта
| Задание для выполнения
|
| 1, 4
| Вершина бинарного дерева содержит ключ, N целых значений и два указателя на потомков. Написать функцию удаления вершины с минимальной суммой N целых значений узла.
|
| 2, 3
| Вершина бинарного дерева содержит ключ и два указателя на потомков. Вычислить среднее арифметическое всех элементов дерева.
|
| 5, 7
| Вершина бинарного дерева содержит ключ, строку и два указателя на потомков. Написать функцию вывода всех элементов дерева по уровням: корень дерева, вершины 1-го уровня, вершины 2-го уровня,...
|
| 6, 12
| Вершина бинарного дерева содержит ключ, строку и два указателя на потомков. Написать функцию, которая подсчитывает число ветвей от корня до ближайшей вершины с заданным ключом, и выводит их.
|
| 9, 11
| Вершина бинарного дерева содержит ключ, строку и два указателя на потомков. Написать функцию определения числа ветвей n-го уровня этого дерева и вывода этих элементов на экран.
|
| 10, 16
| В текстовом файле построчно записаны целые числа. Написать функцию, которая по файлу F, все элементы которого различны, строит соответствующее бинарное дерево поиска T, и вторую функцию, которая записывает в файл G элементы дерева поиска Т в порядке их возрастания.
|
| 13, 15
| Вершина бинарного дерева содержит ключ, строку и два указателя на потомков. Описать рекурсивную функцию, которая печатает элементы из всех листьев дерева.
|
| 14, 8
| Вершина бинарного дерева содержит ключ, N целых значений и два указателя на потомков. Написать функцию удаления вершины с максимальной суммой N целых значений узла.
|
В начало практикума
