19 Август 2010, 12:09
Задание. Построение и обработка двоичных деревьев поиска. Реализовать программу, выполняющую следующий набор операций с деревьями поиска:
- поиск вершины с заданным значением ключа с выводом счетчика числа появлений данного ключа добавление новой вершины в соответствии со значением ее ключа или увеличение счетчика числа появлений построчный вывод дерева в наглядном виде с помощью обратно-симметричного обхода вывод всех вершин в одну строку по порядку следования ключей с указанием для каждой вершины значения ее счетчика появлений удаление вершины с заданным значением ключа
Рекомендации:
- Объявить и реализовать подпрограмму поиска. Поиск начинается с корня дерева и в цикле для каждой вершины сравнивается ее ключ с заданным значением. При совпадении ключей поиска заканчивается с выводом значения счетчика числа появлений данного ключа. При несовпадении поиск продолжается в левом или правом поддереве текущей вершины Объявить и реализовать рекурсивную подпрограмму добавления новой вершины в дерево. Подпрограмма использует один параметр-переменную, определяющую адрес текущей вершины. Если при очередном вызове подпрограммы этот адрес равен NULL, то производится добавление нового элемента с установкой всех необходимых полей. В противном случае продолжается поиск подходящего места для новой вершины за счет рекурсивного вызова подпрограммы с адресом левого или правого поддерева. При совпадении ключей надо просто увеличить значение счетчика появлений Объявить и реализовать нерекурсивный вариант подпрограммы добавления новой вершины в дерево. Необходимы две ссылочные переменные – адрес текущей вершины и адрес ее родителя. Сначала в цикле ищется подходящее место за счет сравнения ключей и перехода влево или вправо. Поиск заканчивается либо по пустому значению текущего адреса, либо в случае совпадения ключей (здесь просто увеличивается счетчик числа появлений). После окончания поиска либо создается корневая вершина, либо добавляется новая вершина как левый или правый потомок родительской вершины. Объявить и реализовать рекурсивную подпрограмму для построчного вывода дерева в обратно-симметричном порядке. Эту подпрограмму без каких-либо изменений можно взять из предыдущей работы. Объявить и реализовать рекурсивную подпрограмму для вывода всех вершин в одну строку в соответствии с возрастанием их ключей. Основа – обход в симметричном порядке. Дополнительно рядом со значением ключа в скобках должно выводится значение счетчика повторений данного ключа. Например:
5(1) 11(2) 19(5) 33(1) 34(4) … Объявить и реализовать подпрограмму удаления вершины: запрашивается ключ вершины, организуется ее поиск, при отсутствии вершины выводится сообщение, при нахождении вершины проверяется число ее потомков и при необходимости выполняется поиск вершины-заменителя
Главная программа должна предоставлять следующие возможности:
- создание дерева с заданным числом вершин со случайными ключами добавление в дерево одной вершины с заданным пользователем значением ключа поиск в дереве вершины с заданным ключом построчный вывод дерева в наглядном виде вывод всех вершин в порядке возрастания их ключей удаление вершины с заданным ключом
Листинг программы
#include <iostream>
#include <cstdlib>
using namespace std;
struct TREE {
int info, count;
TREE *left, *right;
};
TREE *root=NULL;
int flag=0;
int count=0;
TREE *Search(int info)
{
TREE *current=root;
flag=0;
while(current!=NULL && flag==0)
{
if(info<current->info)
current=current->left;
else if(info>current->info)
current=current->right;
else
flag=1;
}
return current;
}
void Add(TREE **current, int info)
{
if(*current!=NULL)
{
if(info<(*current)->info)
Add(&(*current)->left, info);
else if(info>(*current)->info)
Add(&(*current)->right, info);
else
(*current)->count++;
}
else
{
*current=new TREE;
(*current)->info=info;
(*current)->left=NULL;
(*current)->right=NULL;
(*current)->count=1;
count++;
}
}
void AddLoop(int info)
{
if(root==NULL)
{
root=new TREE;
root->info=info;
root->right=NULL;
root->left=NULL;
root->count=1;
count++;
}
else
{
TREE *current=root;
TREE *parent;
while(current!=NULL)
{
parent=current;
if(info<current->info)
current=current->left;
else if(info>current->info)
current=current->right;
else
{
current->count++;
current=NULL;
}
}
if(info<parent->info)
{
current=new TREE;
current->left=NULL;
current->right=NULL;
current->info=info;
current->count=1;
parent->left=current;
count++;
}
else if(info>parent->info)
{
current=new TREE;
current->left=NULL;
current->right=NULL;
current->info=info;
current->count=1;
parent->right=current;
count++;
}
}
}
void Changer(TREE **current, TREE **tmp)
{
if((*current)->right!=NULL)
Changer(&(*current)->right, &(*tmp));
else
{
(*tmp)->info=(*current)->info;
*tmp=*current;
*current=(*current)->left;
}
}
int Delete (TREE **current, int info)
{
int r=0;
if(*current!=NULL)
{
if(info<(*current)->info)
r=Delete(&(*current)->left, info);
else if(info>(*current)->info)
r=Delete(&(*current)->right, info);
else
{
TREE *tmp=*current;
if(tmp->right==NULL)
*current=tmp->left;
else if(tmp->left==NULL)
*current=tmp->right;
else
Changer(&(*current)->left, &tmp);
delete tmp;
count--;
r=1;
}
}
return r;
}
void ShowBackSymmetric(TREE *current, int l)
{
if(current!=NULL)
{
ShowBackSymmetric(current->right, l+1);
for(int i=0; i<l; i++)
cout << "\t";
cout << current->info << endl;
ShowBackSymmetric(current->left, l+1);
}
}
void Show(TREE *current)
{
if(current!=NULL)
{
Show(current->left);
cout << current->info << "(" << current->count << ")" << "";
Show(current->right);
}
}
void Clear(TREE **current)
{
if(*current!=NULL)
{
Clear(&(*current)->left);
Clear(&(*current)->right);
delete *current;
count--;
if(count==0)
*current=NULL;
}
}
int main()
{
setlocale(LC_ALL,"Russian");
int n, num;
char otv;
do
{
cout << endl << "1. Создать"
<< endl << "2. Добавить"
<< endl << "3. Добавить (цикл)"
<< endl << "4. Удалить"
<< endl << "5. Обратно-симметричный обход"
<< endl << "6. Вывод со счетчиком"
<< endl << "7. Очистить"
<< endl << "0. Выход"
<< endl << " = ";
cin >> otv;
switch(otv)
{
case '1':
cout << endl << "Кол-во элементов = ";
cin >> n;
for (int i=0; i<n; i++)
{
num=rand()%100;
Add(&root, num);
}
cout << endl << "Элементы добавлены" << endl;
break;
case '2':
cout << endl << "Введите элемент = ";
cin >> num;
Add(&root, num);
cout << endl << "Элемент добавлен" << endl;
break;
case '3':
cout << endl << "Введите элемент = ";
cin >> num;
AddLoop(num);
cout << endl << "Элемент добавлен" << endl;
break;
case '4':
if(root!=NULL)
{
cout << endl << "Удаляемый элемент = ";
cin >> num;
if(Delete(&root, num)==1)
cout << endl << "Элемент удален" << endl;
else
cout << endl << "Элемент не найден" << endl;
}
else
cout << endl << "Дерево пустое" << endl;
break;
case '5':
if(root!=NULL)
{
ShowBackSymmetric(root,0);
}
else
cout << endl << "Дерево пустое" << endl;
break;
case '6':
if(root!=NULL)
{
Show(root);
}
else
cout << endl << "Дерево пустое" << endl;
break;
case '7':
Clear(&root);
cout << endl << "Дерево очищено" << endl;
break;
case '0':
break;
default:
cout << endl << "Ошибка" << endl;
break;
}
}while(otv!='0');
cin. get();
}
