2015-02-14
485
#include <iostream>
#include <conio.h>
#include <windows.h>
#include <fstream>
using namespace std;
// Вспомогательный класс, описывающий один узел:
class TreeNode
{
friend class Tree; /* Основной класс должен быть объявлен дружественным, чтобы он имел доступ к элементам узла */
// Элементы данных:
int data;
TreeNode* lPtr;
TreeNode* rPtr;
public:
// Конструктор:
TreeNode(int d)
{data = d; lPtr = NULL; rPtr = NULL;}
};
// Основной класс:
class Tree
{
TreeNode* rootPtr; // указатель на корневой узел (элемент данных)
// закрытые функции:
void Add(TreeNode*&,int); // добавляет новый элемент
void preOrder(TreeNode*); // Обход в ширину
void inOrder(TreeNode*); // Последовательный обход
void postOrder(TreeNode*); // Обратный обход
public:
// Конструктор:
Tree() {rootPtr = NULL;}
// открытые функции, которые будет использовать главная программа:
void Add(int);
void preOrder();
void inOrder();
void postOrder();
};
// Определение функций:
//Функция, которая добавляет узел к дереву:
void Tree:: Add(int m)
{
Add(rootPtr, m);
/* Здесь и далее перегрузка функций требуется, поскольку главная программа не имеет доступа к корневому узлу дерева, поэтому единственное назначение этого вызова функции Add() – передать адрес корневого узла. */
|
|
|
}
/* Основная функция, которая обходит дерево и привязывает новый узел к дереву: */
void Tree:: Add(TreeNode*& ptr, int m)
{
if (!ptr)
/* Если текущий указатель равен 0, к нему подвязываем новый узел
или создаем корневой */
ptr = new TreeNode(m);
/* благодаря тому, что параметр ptr объявлен как ссылка на указатель, устанавливается значение указателя на корневой узел или изменяется значение указателя в том узле, к которому привязывается новый */
else
{
if (m < ptr->data) Add(ptr->lPtr, m);
// если новый элемент меньше значения в текущем узле, идем налево
else if (m > ptr->data) Add(ptr->rPtr, m);
// в противном случае - направо
// если встречается повторяющееся значение, то оно игнорируется, благодаря этому все элементы дерева будут различны
}
}
/* три нижеследующие функции отличаются только последовательностью выполнения операторов и благодаря этому позволяют выводить элементы дерева на экран в различном порядке */
void Tree:: preOrder()
{
preOrder(rootPtr);
}
// обход дерева “по ширине”:
void Tree:: preOrder(TreeNode* ptr)
{
if (ptr)
{
cout << ptr->data << " "; // выводим элемент
preOrder(ptr->lPtr); // спускаемся влево
preOrder(ptr->rPtr); // спускаемся вправо
}
}
// Последовательный обход
void Tree:: inOrder()
{
inOrder(rootPtr);
}
// обход в порядке возрастания:
void Tree:: inOrder(TreeNode* ptr)
{
if (ptr)
{
inOrder(ptr->lPtr);
cout << ptr->data << " ";
inOrder(ptr->rPtr);
}
}
// Обход в обратном направлении:
void Tree:: postOrder()
{
postOrder(rootPtr);
}
void Tree:: postOrder(TreeNode* ptr)
{
if (ptr)
{
postOrder(ptr->lPtr);
postOrder(ptr->rPtr);
cout << ptr->data << " ";
}
}
// Пример использования класса:
int main()
{
//Настройки шрифтов и региональных стандартов:
|
|
|
if(SetConsoleCP(1251)==0)
//проверка правильности установки кодировки символов для ввода
{
cerr<<"Fialed to set codepage!"<<endl;
}
if(SetConsoleOutputCP(1251)==0)//тоже самое для вывода
{
cerr<<"Failed to set OUTPUT page!"<<endl;
}
Tree tree; // Объявляем объект
double x;
// Открываем файл с данными:
ifstream file("numbers.txt");
if (file)
{
cout << "Прочитана последовательность: \n";
do
{
file>>x;
if (!file.eof())
{
cout << x << " ";
tree.Add(x); // добавляем элемент к дереву
}
} while (!file.eof());
cout<<endl;
cout <<"Обход в ширину: \n";
tree.preOrder();
cout<<endl;
cout <<"Отсортированная последовательность: \n";
tree.inOrder();
cout<<endl;
cout <<"Обратная последовательность: \n";
tree.postOrder();
cout<<endl;
}
else cout << "Файл не найден\n";
_getch();
return 0;
}
Пример набора данных:
65 34 77 25 38 70 83 21 33 38 88 15 11 14 90 83 99
Схема дерева для этого набора данных:
 |
Результат работы программы:
Прочитана последовательность:
65 34 77 25 38 70 83 21 33 38 88 15 11 14 90 83 99
Обход в ширину:
65 34 25 21 15 11 14 33 38 77 70 83 88 90 99
Отсортированная последовательность:
11 14 15 21 25 33 34 38 65 70 77 83 88 90 99
Обратная последовательность:
14 11 15 21 33 25 38 34 70 99 90 88 83 77 65
