Работа сбинарным деревом
Контрольные вопросы:
I. Что такое дерево?
Дерево – это логический способ организации данных.
II. Какое дерево называют бинарным?
Бинарным называется такое дерево, в котором каждый элемент имеет по два указателя – на правого и левого потомков.
III. Какое дерево называют упорядоченным?
Дерево, в котором определен порядок следования поддеревьев, называется упорядоченным.
IV. Какие элементы дерева называются узлами?
Узлами называются все элементы дерева.
V. Как определяется высота дерева?
Высота дерева - есть количество ветвей от корня дерева до наивысшего листа. Также высота дерева характеризуется количеством уровней.
VI. Чем отличается бинарное дерево от двусвязного списка?
Бинарное дерево отличается от двусвязного списка тем что в последнем каждый узел ссылается на предыдущий и последующие элементы. В бинарном дереве же каждый элемент имеет ссылки на потомков и не имеет указателя на предшествующий родительский элемент. + В бинарном дереве существует логика определения места для каждого нового элемента. Так элементы с большим ключом идет вправо от текущего, а с меньшим влево.
VII. Опишите организацию связей в двоичном дереве.
Первый элемент дерева становится узлом. Правый его указатель указывает на элемент больший или равный по ключу, а левый – на элемент меньший по ключу. Оба эти элемента образуют каждый свое поддерево и находятся на первом уровне (т.к. счет уровней дерева ведется от нуля). Каждый из элементов первого уровня указывают на два своих потомка, находящиеся на втором уровне. И так далее. Элементы не имеющие потомков называются листами.
VIII. Что такое обход дерева? Какие бывают виды обхода дерева?
Обход дерева это поочередный доступ каждому элементу дерева.
· Preorder (нисходящий): операция, влево, вправо.
· Inorder (последовательный): влево, операция, вправо.
· Postorder (восходящий): влево, вправо, операция.
*Применяются рекурсивные функции.
IX. Опишите особенности каждого способа обхода дерева.
Создается специальная рекурсивная функция, получающая в качестве параметра адрес корневого элемента дерева. Производится проверка текущего элемента на NULL. После, в зависимости от выбранного метода, с элементом производится определенная последовательность действий:
· Preorder (нисходящий)
Выполняется операция (н.п. вывод).
Рекурсивно вызывается эта же функция и передается адрес левого потомка.
Рекурсивно вызывается эта же функция и передается адрес правого потомка.
Постановка задачи
Построить бинарное дерево одного из типов данных:
1. строкового;
2. целочисленного;
3. символьного.
4. Для бинарного дерева осуществить операции:
Ø добавление вершины дерева;
Ø обход дерева всеми способами*;
Ø вывод дерева на экран;
Ø уничтожение дерева.
* Выполнить обход дерева рекурсивным способом
1. Нисходящим способом
2. Восходящим способом
3. Смешанным способом
Дополнительные задания для работы с бинарным деревом
Ø удаление вершины поддерева;
Ø поиск вершины дерева по ключу
Описание входных и выходных данных
Исходные данные:
node – структура для хранения элементовдерева;
Входные данные: выбор действия, ключ нового элемента, ключ элемента подлежащего удалению или поиску.
Выходные данные:
Дерево (все методы обхода + визуализация); кол-во записей; кол-во уровней.
Описание алгоритма
В главной функции создается указатель на корень дерева, который будет передаваться другим функциям.
Функция добавления (Insert):
Вводитсяключ и вызывается функция Insert (перегруженная ф-я), которой передаются корень и ключ.
В другой функции поступивший указатель проверяется на NULL, и если истина, то создается новый элемент и переданный указатель направляется на него.В ином случае, если ключ совпадает по значению со значением текущего узла, происходит выход из функции. Иначе, если введенный ключ больше текущего, то происходит рекурсивный вызов функции, и ей передаются ключ и адрес правого потомка текущего элемента, в противном случае передается адрес левого потомка.
Функция удаления (Dlt):
Если у удаляемого элемента нет детей, то он просто удаляется. Если один потомок, то удаляем элемент и возвращаем потомка. Если же потомков два, то в правой стороне находится минимальный по значению ключ (ф-я Min). И если минимальный элемент находится сразу после удаляемого назначаем левым потомком минимального левого потомка удаляемого. Если же минимальный элемент находится дальше, то мы находим предыдущий от минимального (ф-я Previous). Теперь левым сыном предыдущего будет правый сын минимального. Указателям на потомков минимального присваивается значение указателей на потомков удаляемого элемента. Элемент удаляется, а минимальный возвращается.
Блоксхемы
Листинг
#include<iostream>
#include<string>
#include<iomanip>
usingnamespace std;
structnode {
string data;
node *left, *right;
};
//----------------------------------------
int Menu(node *, int&, bool);
void Insert(node *&, string);
void PrintPreOrder(node *);
void PrintInOrder(node *);
void PrintPostOrder(node *);
bool Search(node *, string, bool&, int);
node *Dlt(node *&, string);
node *Min(node *);
int Height(node *);
int max(int, int);
int NodesNumber(node *);
node *Previous(node *,node *&);
void Show(node *);
void Search(node *);
void Delete(node *&);
void Destroy(node *&);
void Draw(node *, int);
void Insert(node *&);
//----------------------------------------
int main() {
node *Root = nullptr;
int act; bool cmd = false;
do {
int b = -1;
act = Menu(Root, b, cmd);
switch (act) {
case 1: Insert(Root); break;
case 2: Show(Root); break;
case 3: Search(Root); break;
case 4: Delete(Root); break;
case 5: Destroy(Root); break;
}
system("pause"); system("cls");
} while (act);
Destroy(Root);
return 0;
}
void Insert(node *&Root) {
string data; cin >> data;
Insert(Root, data);
}
void Draw(node *Root, intindent){
if (Root){
Draw(Root->right, indent + 4);
cout << setw(indent) <<" "<<Root->data << endl;
Draw(Root->left, indent + 4);
}
}
int NodesNumber(node *Root) {
if (Root)
return NodesNumber(Root->left) + NodesNumber(Root->right) + 1;
else
return 0;
}
int max(inta, intb) {
if (a>b) returna;
elsereturnb;
}
int Height(node *Root) {
if (Root) {
return max(Height(Root->left), Height(Root->right)) + 1;
}
else
return 0;
}
node *Dlt(node *&Root, stringdel) {
if (del<Root->data)
Root->left = Dlt(Root->left, del);
elseif (del>Root->data)
Root->right = Dlt(Root->right, del);
else {
if (!Root->left &&!Root->right) { // No child
deleteRoot;
Root = nullptr;
returnRoot;
}
else { // One or more chidls
if (Root->right &&Root->left) { // Two children
node *min = Min(Root->right);
node *prev;
if (Root->right == min) {
min->left = Root->left;
}
else {
prev = Previous(Root->right, min);
prev->left = min->right;
min->right = Root->right;
min->left = Root->left;
}
deleteRoot;
return min;
}
if (!Root->right) { // One left child
node *tmp = Root->left;
deleteRoot;
return tmp;
}
else{ // One right child
node *tmp = Root->right;
deleteRoot;
return tmp;
}
}
}
returnRoot;
}
node *Previous(node *Root, node *&src) {
if (Root) {
if (Root->left == src) {
returnRoot;
}
Root = Previous(Root->left, src);
}
}
node *Min(node *Root) {
if (Root->left)
Root = Min(Root->left);
returnRoot;
}
void Delete(node *&Root) {
if (Root) {
string d; std::cin >> d; bool b = false;
if (Search(Root, d, b, 1))
Root = Dlt(Root, d);
else {
cout <<"Not found\n\n"; return;
}
}
else
cout <<"The tree is empty\n\n";
}
void Destroy(node *&Root) {
if (Root) {
Destroy(Root->left);
Destroy(Root->right);
deleteRoot;
Root = nullptr;
}
}
bool Search(node *Root, stringsrch,bool&b, intfloor) {
if (Root) {
Search(Root->left, srch,b,floor+1);
Search(Root->right, srch,b,floor+1);
if (Root->data ==srch) {
cout <<"\nThe entry was found on "<<floor<<" level\n\n";
b = true;
}
returnb;
}
}
void Search(node *Root) {
if (Root) {
string srch; cin >> srch; bool b = false; int floor = 1;
if (!Search(Root, srch,b, floor))
cout <<"Not found\n\n";
}
else
cout <<"The tree is empty\n\n";
}
int Menu(node *Root, int&b, boolcmd) {
string a;
int ident = 1;
do {
system("cls");
cout <<"\t\t\t\ Ayupov Azizjan\n\n";
Draw(Root, ident);
cout <<"\nHeight: "<< Height(Root) <<" levels\tNodes: "<< NodesNumber(Root) <<"\n";
if (cmd)
cout <<"\n| Commads\n"
<<"|\tpush................Push an entry to the tree\n"
<<"|\tshow................Show the tree\n"
<<"|\tsearch..............Search an entry in the tree\n"
<<"|\tdelete..............Delete an entry from the tree\n"
<<"|\tdestroy.............Destroy the tree\n"
<<"|\texit................Exit from programm\n";
cout <<"\nDo: "; cin >> a; cout << endl;
if (a =="exit") b = 0;
elseif (a =="push") b = 1;
elseif (a =="show") b = 2;
elseif (a =="search") b = 3;
elseif (a =="delete") b = 4;
elseif (a =="destroy") b = 5;
elseif (a =="menu") Menu(Root, b, true);
else
b = -1;
} while (b<0);
returnb;
}
void Show(node *Root) {
if (Root) {
string var; bool v = false; int indent = 1;
do {
cout <<"\n| Type\n"
<<"|\tpre.................Preorder\n"
<<"|\tin..................Inorder\n"
<<"|\tpost................Postorder\n\n";
std::cin >> var;
if (var =="pre" || var =="in" || var =="post")
v = true;
} while (!v);
cout << endl;
if (var =="pre") PrintPreOrder(Root);
elseif (var =="in") PrintInOrder(Root);
else PrintPostOrder(Root);
cout <<"\n\n\n";
}
else
cout <<"Tree is empty\n\n";
}
void PrintPreOrder(node *Root) {
if (Root) {
cout <<Root->data <<" ";
PrintPreOrder(Root->left);
PrintPreOrder(Root->right);
}
}
void PrintInOrder(node *Root) {
if (Root) {
PrintInOrder(Root->left);
cout <<Root->data <<" ";
PrintInOrder(Root->right);
}
}
void PrintPostOrder(node *Root) {
if (Root) {
PrintPostOrder(Root->left);
PrintPostOrder(Root->right);
cout <<Root->data <<" ";
}
}
void Insert(node *&Root, stringdata) {
if (!Root) {
Root = newnode;
Root->data =data;
Root->left = Root->right = nullptr;
}
else {
if (data==Root->data)
return;
elseif (data>Root->data)
Insert(Root->right, data);
else
Insert(Root->left, data);
}
}
Анализ результатов и выводы
В итоге получилась программа, занимающая 13 800 байт.
К достоинствам создания поисковой системы подобным образом могу отнести простоту реализации и высокую надежность.
Недостатков не найдено.