БИНАРНОЕ УПОРЯДОЧЕННОЕ ДЕРЕВО

Введение

Дерево является нелинейной динамической структурой хранения данных. Дерево состоит из узлов или вершин, которые содержат поля данных и указатели на другие узлы или вершины.

Бинарное дерево

Узел или вершина бинарного дерева содержит поле данных и два поля с указателями. Поля указателей называются левым указателем (left) и правым указателем (right), поскольку они указывают на левое и правое поддерево, соответственно. Значение NULL указателя является признаком пустого поддерева.

Корневой узел определяет входную точку дерева, а поле указателя – узел следующего уровня. Листовой узел (лист) содержит NULL в поле правого и левого указателей.

Класс TreeNode

Объекты класса TreeNode являются узлами бинарного дерева (рис.8.1).

class TreeNode

{

private:

// указатели левого и правого дочерних узлов

TreeNode* left;

TreeNode* right;

public:

// открытый элемент

int data;

// конструктор

TreeNode(const int& item, TreeNode* lptr=NULL,

TreeNode* rptr=NULL);

// функции-элементы доступа к полям указателей

TreeNode* Left() const;

TreeNode* Right() const;

};

Конструктор инициализирует поля данных и указателей. С помощью пустого указателя NULL узлы инициализируются как листья. Имея указатель P объекта класса TreeNode в качестве параметра, конструктор присоединяет P как левого или правого потомка нового узла. Функции-элементы Left() и Right() возвращают значения полей левого и правого указателей. Благодаря этому клиент класса имеет доступ к левому и правому потомкам узла.

Примеры

// указатели целочисленных узлов дерева

TreeNode*root, *lp, *rp;

TreeNode*p;

// создать листья, содержащие 20 и 30 в качестве данных

lp=new TreeNode (20);

rp=new TreeNode (30);

// создать корень, содержащий число 10 и двух потомков

root= new TreeNode (10, lp, rp);

Рис.8.1 – бинарное дерево

root->data=50;// присвоить корню 50

Переопределение конструктора

// конструктор инициализирует поля данных и указателей

// значение NULL соответствует пустому поддереву

TreeNode:: TreeNode (const int& item, TreeNode*lp,

TreeNode*rp):data(item), left(lp), right(rp)

{}

Бинарное упорядоченное дерево ( дерево поиска)

Бинарное дерево поиска – это структура (рис.8.2), которая упорядочивает элементы посредством отношения “<”. Чтобы сравнить узлы дерева, подразумевают, что часть или все поле данных определено в качестве ключа и операция “<” сравнивает ключи при размещении элемента на дереве.

Бинарное дерево поиска строится по следующему правилу:

Для каждого узла значения данных в левом поддереве меньше, чем в этом узле, а в правом поддереве – больше.

Дерево называется поисковым потому, что в поисках некоторого элемента (ключа) можно идти лишь по совершенно конкретному пути. Начав с корня, сканируют левое поддерево, если значение ключа меньше текущего узла. В противном случае сканируют правое поддерево. Метод создания дерева позволяет осуществлять поиск по кратчайшему пути от корня. Бинарные деревья поиска предназначены для быстрого доступа к данным. В идеале дерево является сбалансированным и имеет высоту и эффективность поиска порядка

Рис.8.2 – бинарное упорядоченное дерево

Для обработки данных, размещенных в дереве, применяют следующие методы прохождения дерева:

левое поддерево-узел-правое поддерево, или симметричный метод;

левое поддерево-правое поддерево-узел, или обратный метод;

правое поддерево-узел- левое поддерево, или справа-налево;

узел-левое поддерево-правое поддерево, или сверху-вниз.

Для реализации методов используют рекурсивные алгоритмы.

Класс BinSTree

Объектом этого класса является бинарное упорядоченное дерево (пример - на рис.8.2).

// класс - бинарное дерево

class BinSTree

{

public:

// конструкторы и деструктор

BinSTree();

//конструктор копирования

BinSTree(const BinSTree& tree);

~BinSTree();

// оператор присваивания

BinSTree& operator=(const BinSTree& rhs);

// функции-элементы обработки данных

int Find(int& item); // есть или нет узла с item

void Insert(const int& item); // вставить узел с item

void Delete(const int& item); // удалить узел с item

void ClearTree(); // уничтожить дерево

TreeNode *CopyTree(TreeNode *t); // копировать дерево

int Depth(TreeNode *t); // получить глубину дерева

// получить количество листьев в дереве

void CountLeaf(TreeNode *t,int& count);

// получить корень дерева

TreeNode *GetRoot() const {return root;}

// получить количество узлов в дереве

int GetSize() const {return size;}

private:

// указатель на корень

TreeNode *root;

// количество узлов в дереве

int size;

// выделить память под узел дерева

TreeNode *GetTreeNode(const int& item,

TreeNode *lptr, TreeNode *rptr);

// удалить все узлы дерева

void DeleteTree(TreeNode* t);

// получить указатели - на узел с item и его родителя

TreeNode *FindNode(const int& item,

TreeNode* &parent)const;

};

Конструктор инициализирует данные-элементы. Конструктор копирования и перегруженный оператор присваивания с помощью функции-элемента CopyTree создают новое бинарное дерево для текущего объекта.

Алгоритм удаления узлов дерева реализован функцией-элементом DeleteTree и используется функцией-элементом ClearTree, вызываемой как деструктором, так и перегруженной операцией присваивания.

Функции-элементы Find и Insert начинают с корня и используют определение бинарного дерева поиска. Алгоритм идет по правому поддереву, когда ключ или новый элемент больше значения текущего узла. В противном случае прохождение продолжается по левому поддереву. Функция-элемент Find использует закрытую функцию-элемент FindNode, принимающую в качестве параметра ключ и осуществляющую прохождение вниз по дереву. Функция возвращает указатель на совпавший узел и указатель на его родителя. Если совпадение происходит в корне, родительский указатель равен NULL.

Функция-элемент Delete удаляет из дерева узел с заданным ключом. Сначала с помощью функции-элемента FindNode устанавливается место этого узла на дереве и определяется указатель на его родителя. Если искомый узел отсутствует, операция удаления завершается.

Удаление узла из дерева требует ряда проверок, чтобы определить, куда присоединить сыновей удаляемого узла. Поддеревья должны быть заново присоединены таким образом, чтобы сохранилась структура бинарного упорядоченного дерева.

Функция FindNode возвращает указатель DNodePtr на узел D, подлежащий удалению. Второй указатель, PNodePtr, идентифицирует узел P – родителя удаляемого узла. Функция Delete ”пытается” подыскать заменяющий узел R, который будет присоединен к родителю и, следовательно, займет место удаленного узла. Заменяющий узел R идентифицируется указателем RNodePtr.

Функция Delete реализует алгоритм поиска заменяющего узла из четырех случаев, зависящих от числа и расположения сыновей удаляемого узла. Отметим, что если указатель на родителя равен NULL, то удаляется и обновляется корень. Эта ситуация учитывается алгоритмом.

Чтобы функции-элементы класса BinSTree получили доступ к закрытым данным-элементам left и right класса TreeNode, класс BinSTree объявляется другом класса TreeNode. Это объявление предваряется формальным объявлением класса BinSTree.

Целью данной лабораторной работы является изучение алгоритмов и функций работы с бинарным упорядоченным деревом на примере дерева из целых чисел.

Проектирование приложения.

Выбор, размещение и задание свойств компонентов.

Коды классов, функций и обработчиков событий

Сохраните модуль главной формы под именем LR_8, а проект – под именем PR_LR_8.

Для размещения классов в проекте использованы модули, не связанные с формой. Класс для узла дерева объявлен и определен в файле f_8_1, а класс для бинарного дерева – в модуле f_8_2. Ниже приведены заголовочные файлы и файлы реализации этих модулей.

Заголовочный файл f_8_1.h модуля f_8_1 (без формы)

//---------------------------------------------------------------------------

#ifndef f_8_1H

#define f_8_1H

#include <iostream.h> // для константы NULL

//---------------------------------------------------------------------------

//BinSTree зависит от TreeNode

class BinSTree;

// объявление класса для узла бинарного дерева

class TreeNode

{

// сделать класс BinSTree дружественным,

// поскольку функциям-элементам класса BinSTree

// необходим доступ к полям left и right класса TreeNode

friend class BinSTree;

public:

// открытый элемент

int data;

// конструктор

TreeNode(const int& item, TreeNode *lptr=NULL,

TreeNode *rptr=NULL);

// функции-элементы доступа к полям указателей

TreeNode* Left() const{return left;}

TreeNode* Right() const{return right;}

private:

// указатели левого и правого дочерних узлов

TreeNode *left;

TreeNode *right;

};

#endif

Файл реализации f_8_1.cpp модуля f_8_1 (без формы)

//---------------------------------------------------------------------------

#pragma hdrstop

#include "f_8_1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

// конструктор инициализирует поля данных и указателей

// значение NULL соответствует пустому поддереву

TreeNode::TreeNode(const int& item, TreeNode *lptr,

TreeNode *rptr):data(item), left(lptr), right(rptr)

{}

Заголовочный файл f_8_2.h модуля f_8_2 (без формы)

//---------------------------------------------------------------------------

#ifndef f_8_2H

#define f_8_2H

#include "f_8_1.h"

//------------------------------------------------------------------------

// класс - бинарное дерево

class BinSTree

{

public:

// конструкторы и деструктор

BinSTree();

BinSTree(const BinSTree& tree);

~BinSTree();

// оператор присваивания

BinSTree& operator=(const BinSTree& rhs);

// функции-элементы обработки данных

int Find(int& item); // есть или нет узла с item

void Insert(const int& item); // вставить узел с item

void Delete(const int& item); // удалить узел с item

void ClearTree(); // уничтожить дерево

TreeNode *CopyTree(TreeNode *t); // копировать дерево

int Depth(TreeNode *t); // получить глубину дерева

// получить количество листьев в дереве

void CountLeaf(TreeNode *t,int& count);

// получить корень дерева

TreeNode *GetRoot() const {return root;}

// получить количество узлов в дереве

int GetSize() const {return size;}

private:

// указатель на корень

TreeNode *root;

// количество узлов в дереве

int size;

// выделить память под узел дерева

TreeNode *GetTreeNode(const int& item,

TreeNode *lptr, TreeNode *rptr);

// удалить все узлы дерева

void DeleteTree(TreeNode* t);

// получить указатели - на узел с item и его родителя

TreeNode *FindNode(const int& item,

TreeNode* &parent)const;

};

#endif

Файл реализации f_8_2.cpp модуля f_8_2 (без формы)

//---------------------------------------------------------------------------

#pragma hdrstop

#include <iostream.h> // для константы NULL

#include "f_8_2.h"

#include "LR_8.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

//---------------------------------------------------------------------------

// конструктор

BinSTree::BinSTree()

{

root=NULL;

size=0;

}

//---------------------------------------------------------------------------

// конструктор копирования

BinSTree::BinSTree(const BinSTree& tree)

{

// скопировать дерево в создаваемое дерево

root=CopyTree(tree.root);

// скопировать размер дерева

size=tree.size;

}

//---------------------------------------------------------------------------

// деструктор

BinSTree::~BinSTree()

{

ClearTree();

size=0;

}

//---------------------------------------------------------------------------

// оператор присваивания

BinSTree& BinSTree::operator = (const BinSTree& rhs)

{

// нельзя копировать дерево в самоё себя

if(this == &rhs)

return *this;

// очистить текущее дерево, скопировать новое дерево в текущий

// объект

ClearTree();

root=CopyTree(rhs.root);

// задать размер дерева

size=rhs.size;

// возвратить ссылку на текущий объект

return *this;

}

//----------------------------------------------------------------------

// искать элемент данных на дереве; если найден, возвратить адрес

// совпавшего узла и указатель на его предка; иначе возвратить NULL

TreeNode *BinSTree::FindNode(const int& item,

TreeNode* &parent) const

{

// пробежать по узлам дерева, начиная с корня

TreeNode *t=root;

// у корня нет родителя

parent=NULL;

// прерваться на пустом поддереве

while (t!=NULL)

{

// остановиться по совпадению

if(item==t->data)

break;

else

{

//обновить родительский указатель и идти налево или направо

parent=t;

if(item<t->data)

t=t->left;

else

t=t->right;

}

}

// возвратить указатель на узел; NULL, если не найден

return t;

}

//----------------------------------------------------------------------

// искать item. если найден, присвоить данные узла параметру item

int BinSTree::Find(int& item)

{

// используем FindNode, который принимает параметр parent

TreeNode *parent, *current;

// искать item, назначить совпавший узел текущим

current = FindNode(item,parent);

// если найден, присвоить данные узла и возвратить true

if(current!=NULL)

{

item=current->data;

return 1;

}

else

// item не найден, возвратить false

return 0;

}

//--------------------------------------------------------------------------

// создать объект TreeNode с указательными полями lptr и rptr.

// по умолчанию указатели содержат NULL.

TreeNode *BinSTree::GetTreeNode(const int& item,

TreeNode *lptr, TreeNode *rptr)

{

TreeNode *p;

// вызвать new для создания нового узла.

// передать туда параметры lptr и rptr.

p=new TreeNode (item, lptr, rptr);

// если памяти недостаточно, завершить программу

// сообщением об ошибке

if(p==NULL)

{

MessageBox(NULL,"Недостаточно памяти!","Ошибка",0);

return NULL;

}

// вернуть указатель на выделенную память

return p;

}

//----------------------------------------------------------------------

// вставить item в дерево

void BinSTree::Insert(const int& item)

{

// t - текущий узел, parent - предыдущий узел

// newNode - новый узел

TreeNode *t=root, *parent=NULL, *newNode;

newNode = GetTreeNode(item, NULL, NULL);

// закончить на пустом поддереве

while (t!=NULL)

{

// если item равно данному в текущем узле, не вставлять

if(item==t->data) return;

// обновить указатель parent и идти налево или направо

parent=t;

if(item<t->data)

t=t->left;

else

t=t->right;

}

// если родителя нет, вставить в качестве корневого узла

if(parent==NULL)

root=newNode;

// если item меньше данного в родительском узле,

// вставить в качестве левого сына

else if(item<parent->data)

parent->left=newNode;

else

// если item больше данному в родительском узле,

// вставить в качестве правого сына

parent->right=newNode;

// увеличить size на единицу

size++;

}

//------------------------------------------------------------------------

// если элемент находится на дереве, удалить его

void BinSTree::Delete(const int& item)

{

// DNodePtr - указатель на удаляемый узел D

// PNodePtr - указатель на родительский узел P узла D

// RNodePtr - указатель на узел R, замещающий узел D

TreeNode *DNodePtr, *PNodePtr, *RNodePtr;

// найти узел, данные в котором совпадают с item.

// получить его адрес и адрес его родителя

if((DNodePtr=FindNode(item,PNodePtr))==NULL)

return;

// если узел D имеет NULL-указатель, то заменяющим

// узлом является тот, что находится на другой ветви

if(DNodePtr->right==NULL)

RNodePtr=DNodePtr->left;

else if(DNodePtr->left==NULL)

RNodePtr=DNodePtr->right;

// узел D имеет двух сыновей

else

{

// найти и отсоединить заменяющий узел R для узла D.

// в левом поддереве узла D найти узел с максимальным данным

// из всех узлов с меньшими данными, чем в узле D.

// отсоединить этот узел от дерева.

// PofRNodePtr - указатель на родителя заменяющего узла

TreeNode *PofRNodePtr=DNodePtr;

// первой возможной заменой является левый сын узла D

RNodePtr=DNodePtr->left;

// спуститься вниз по правому поддереву левого сына узла D,

// сохраняя записи текущего узла и его родителя.

// остановившись, будем иметь заменяющий узел

while (RNodePtr->right!=NULL)

{

PofRNodePtr=RNodePtr;

RNodePtr=RNodePtr->right;

}

if(PofRNodePtr==DNodePtr)

// левый сын удаляемого узла является заменяющим

// присоединить правое поддерево узла D к узлу R

RNodePtr->right=DNodePtr->right;

else

{

// спустились вниз по правой ветви как минимум на один узел.

// удалить заменяющий узел из дерева,

// присоединив его левую ветвь к его родительскому узлу

PofRNodePtr->right=RNodePtr->left;

// присоединить правую и левую ветви удаляемого узла

// к правой и левой ветвям соответственно заменяющего узла

RNodePtr->right=DNodePtr->right;

RNodePtr->left=DNodePtr->left;

}

}

// завершить присоединение заменяющего узла к родительскому узлу.

// удалить корневой узел. назначить новый корень.

if(PNodePtr==NULL)

root=RNodePtr;

// присоединить узел R к узлу P с правильной стороны

else

if(DNodePtr->data<PNodePtr->data)

PNodePtr->left=RNodePtr;

else

PNodePtr->right=RNodePtr;

// удалить узел из памяти и уменьшить размер дерева

delete DNodePtr;

DNodePtr=NULL;

size--;

}

//---------------------------------------------------------------------

// эта функция при обходе дерева подсчитывает его листья.

// функция использует обратный метод обхода дерева.

// во время посещения узла проверяется, является ли он листом.

void BinSTree::CountLeaf(TreeNode *t,int& count)

{

// использовать обратный метод прохождения

if(t!=NULL)

{

CountLeaf(t->left, count); // пройти левое поддерево

CountLeaf(t->right, count); // пройти правое поддерево

// проверить, является ли данный узел листом.

// если да, то произвести приращение переменной count

if( t->left==NULL && t->right==NULL)

count++;

}

}

//----------------------------------------------------------------------

// эта функция использует обратный метод обхода дерева для

// вычисления глубины левого и правого поддеревьев узла и

// возвращает результирующее

// значение глубины, равное 1+max(depthLeft,depthRight).

// глубина пустого дерева равна -1

int BinSTree::Depth(TreeNode *t)

{

int depthLeft, depthRight, depthval;

if(t==NULL)

depthval=-1;

else

{

depthLeft=Depth(t->left);

depthRight=Depth(t->right);

depthval=1+(depthLeft>depthRight?depthLeft:depthRight);

}

return depthval;

}

//-----------------------------------------------------------------------

// создать дубликат нового дерева t и возвратить корень нового дерева

TreeNode *BinSTree::CopyTree(TreeNode *t)

{

// переменная newnode указывает на новый узел, создаваемый

// посредством вызова GetTreeNode и присоединяемый в дальнейшем

// к новому дереву. указатели newlptr и newrptr адресуют сыновей

// нового узла и передаются в качестве параметров в GetTreeNode

TreeNode *newlptr, *newrptr, *newnode;

// остановить рекурсивное прохождение при достижении пустого дерева

if(t==NULL)

return NULL;

// CopyTree строит новое дерево в процессе прохождения узлов дерева t.

// в каждом узле этого дерева функция CopyTree проверяет наличие

// левого сына.

// если он есть, создается его копия. в противном случае возвращается

// NULL.

// CopyTree создает копию узла с помощью GetTreeNode

// и подвешивает к нему копии сыновей

if(t->Left()!=NULL)

newlptr=CopyTree(t->left);

else

newlptr=NULL;

if(t->Right()!=NULL)

newrptr=CopyTree(t->right);

else

newrptr=NULL;

// построить новое дерево снизу вверх, сначала создавая

// двух сыновей, а затем их родителя

newnode=GetTreeNode(t->data, newlptr, newrptr);

// вернуть указатель на вновь созданное дерево

return newnode;

}

//------------------------------------------------------------------------

// использовать обратный алгоритм для прохождения узлов дерева

// и удалить каждый узел при его посещении

void BinSTree::DeleteTree(TreeNode* t)

{

if(t)

{

DeleteTree(t->left);

DeleteTree(t->right);

delete t;

size--;

}

}

//--------------------------------------------------------------------------

// вызвать функцию DeleteTree для удаления узлов дерева.

// затем сбросить указатель на его корень в NULL

void BinSTree::ClearTree()

{

DeleteTree(root);

root=NULL;

// теперь корень пуст, дерево уничтожено

}

//------------------------------------------------------------------------

Достаточно полную информацию для размещения компонентов на форме и задания их свойств можно получить из представленных ниже рис.8.3, рис.8.4 и заголовочного файла модуля LR_8.

Рис.8.3 – форма по окончании проектирования

Рис.8.4 – меню

Заголовочный файл LR_8.h модуля LR_8

//---------------------------------------------------------------------------

#ifndef LR_8H

#define LR_8H

//---------------------------------------------------------------------------

#include <Classes.hpp>

#include <Controls.hpp>

#include <StdCtrls.hpp>

#include <Forms.hpp>

#include "CSPIN.h"

#include <ComCtrls.hpp>

#include <ActnCtrls.hpp>

#include <ActnList.hpp>

#include <ActnMan.hpp>

#include <ActnMenus.hpp>

#include <ImgList.hpp>

#include <ToolWin.hpp>

#include <ExtCtrls.hpp>

#include <Buttons.hpp>

//---------------------------------------------------------------------------

class TForm1 : public TForm

{

__published: // IDE-managed Components

TMemo *Memo1;

TLabel *Label1;

TImageList *ImageList1;

TActionManager *ActionManager1;

TAction *SaveFileAs;

TAction *SaveFile;

TAction *OpenFile;

TAction *OutMemo;

TAction *Depth;

TAction *CountLeaf;

TAction *Find;

TAction *ClearTree;

TAction *Exit;

TGroupBox *GroupBox1;

TRadioButton *RadioButton2;

TRadioButton *RadioButton1;

TCSpinEdit *CSpinEdit1;

TButton *Button1;

TButton *Button2;

TLabeledEdit *LabeledEdit1;

TAction *Insert;

TAction *Delete;

TBitBtn *BitBtn1;

TActionMainMenuBar *ActionMainMenuBar1;

TActionToolBar *ActionToolBar1;

TAction *ClearMemo;

TLabeledEdit *LabeledEdit2;

TLabel *Label2;

void __fastcall RadioButton2Click(TObject *Sender);

void __fastcall RadioButton1Click(TObject *Sender);

void __fastcall ExitExecute(TObject *Sender);

void __fastcall OutMemoExecute(TObject *Sender);

void __fastcall InsertExecute(TObject *Sender);

void __fastcall BitBtn1Click(TObject *Sender);

void __fastcall ClearMemoExecute(TObject *Sender);

void __fastcall ClearTreeExecute(TObject *Sender);

void __fastcall CountLeafExecute(TObject *Sender);

void __fastcall DepthExecute(TObject *Sender);

void __fastcall FindExecute(TObject *Sender);

void __fastcall DeleteExecute(TObject *Sender);

private: // User declarations

public: // User declarations

__fastcall TForm1(TComponent* Owner);

};

//---------------------------------------------------------------------------

extern PACKAGE TForm1 *Form1;

//---------------------------------------------------------------------------

#endif

Перенесем на форму компоненты и зададим их свойствам значения. Со страницы Дополнительно – LabeledEdit1 (EditLabel->Caption – Ключ, Text - 10), диспетчер действий ActionManager1 и полосу главного меню ActionMainMenuBar1. По умолчанию полоса главного меню ActionMainMenuBar1 расположится вверху, на всю ширину формы. Задайте её свойство Align = alNone, чтобы придать ей нужные размеры и расположить в нужном месте.

Затем со страницы Win32 перенесите на форму ImageList1, со страницы Стандарт - Label1 (Caption – ДЕРЕВО), Memo1, GroupBox1 (Caption – Формирование дерева). На панель GroupBox1 перенесите: со страницы Стандарт - две радиокнопки – RadioButton1 (Caption - вручную, Checked – true, Enabled - true) и RadioButton2 (Caption - автоматически, Checked – false, Enabled - true), Label2 (Caption – количество узлов), Button1 (Caption – Добавить узел), Button2 (Caption – Удалить узел ), со страницы Примеры – CSpinEdit1 (MaxValue - 100, MinValue – 1, Value – 10), со страницы Дополнительно – BitBtn1 (Caption – ПУСК), LabeledEdit2 (EditLabel->Caption – целое число, Text - 10).

Загрузите в компонент ImageList1 пиктограммы из файлов fldropen, filesave, floppy, find, insert, clear, delete, arrow2d, erase, dooropen, directry. В компоненте ActionManager1 установим свойство Images равным ImageList1, связав тем самым диспетчер действий со списком изображений.

Добавьте на форму с помощью диспетчера действий ActionManager1 инструментальную панель ActionTollBar1, задайте для нее Align = alNone, Constraints->MaxHeight =230, Constraints->MinHeight =230 и расположите ее на форме согласно рис.8.3.

В диспетчере действий ActionManager1 создайте три категории действий: Файл, Дерево, Выход.

По категориям объектам действий даны следующие надписи (Caption) - имена (Name): Файл: Сохранить как - FileSaveAs, Сохранить - FileSave, Открыть - FileOpen; Дерево: Уничтожить дерево - ClearTree, Поиск узла по ключу - Find, Кол-во листьев - CountLeaf, Глубина дерева - Depth, Вывести дерево в окно - OutMemo, Удалить узел - Delete, Добавить узел - Insert, Очистить окно - ClearMemo. В свойство ImageIndex перечисленных объектов действий занесите соответствующие значения.

В свойство Action кнопок Button1 (Caption – Добавить узел) и Button2 (Caption – Удалить узел ) занесите соответственно значения Insert и Delete.

Действия по активации и инициализации компонентов и обработчики событий приведены в файле реализации LR_8.cpp модуля LR_8.

Файл реализации LR_8.cpp модуля LR_8

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include "LR_8.h"

#include "f_8_2.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma link "CSPIN"

#pragma resource "*.dfm"

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

Memo1->Text="";

RadioButton1->Checked=true;

RadioButton2->Checked=false;

CSpinEdit1->Enabled=false;

Label2->Enabled=false;

BitBtn1->Enabled=false;

Button1->Enabled=true;

Button2->Enabled=true;

LabeledEdit2->Enabled=true;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::RadioButton2Click(TObject *Sender)

{

if(RadioButton2->Checked)

{

Label2->Enabled=true;

CSpinEdit1->Enabled=true;

LabeledEdit2->Enabled=false;

BitBtn1->Enabled=true;

Button1->Enabled=false;

Button2->Enabled=false;

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::RadioButton1Click(TObject *Sender)

{

if(RadioButton1->Checked)

{

Label2->Enabled=false;

CSpinEdit1->Enabled=false;

BitBtn1->Enabled=false;

LabeledEdit2->Enabled=true;

Button1->Enabled=true;

Button2->Enabled=true;

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::ExitExecute(TObject *Sender)

{

Close();

}

//---------------------------------------------------------------------------

// вывод дерева в окно с обходом справа-налево

void PrintTree(TreeNode *t, int level)

{

AnsiString s="";

// обходить дерево справа-налево, пока t!=NULL

if(t!=NULL)

{

// обходить правое поддерево узла t

PrintTree(t->Right(), level+1);

// вывести данное в узле t

for(int i=0; i<level; i++) s += "****";

s += IntToStr(t->data);

Form1->Memo1->Lines->Add(s);

// обходить левое поддерево узла t

PrintTree(t->Left(), level+1);

}

}

//-------------------------------------------------------------------------

// создать объект класса - бинарное дерево

BinSTree AI;

//-------------------------------------------------------------------------

void __fastcall TForm1::OutMemoExecute(TObject *Sender)

{

TreeNode *t= AI.GetRoot();

if(t==NULL)

{

MessageBox(NULL,"Дерево пусто!","",0);

return;

}

Form1->Memo1->Lines->Add("");

PrintTree(t,0);

Form1->Memo1->Lines->Add("Количество узлов - " +

IntToStr(AI.GetSize()));

Form1->Memo1->Lines->Add("");

}

//---------------------------------------------------------------------------

void __fastcall TForm1::InsertExecute(TObject *Sender)

{

AI.Insert(StrToInt(LabeledEdit2->Text));

Form1->Memo1->Lines->Add("Узел "+LabeledEdit2->Text+" добавлен!");

}

//---------------------------------------------------------------------------

void __fastcall TForm1::BitBtn1Click(TObject *Sender)

{

AI.ClearTree();

for(int i=0; i<CSpinEdit1->Value; i++)

AI.Insert(random(101)-random(101));

}

//---------------------------------------------------------------------------

void __fastcall TForm1::ClearMemoExecute(TObject *Sender)

{

Memo1->Clear();

}

//---------------------------------------------------------------------------

void __fastcall TForm1::ClearTreeExecute(TObject *Sender)

{

if(AI.GetRoot()==NULL)

{

MessageBox(NULL,"Дерево пусто!","",0);

return;

}

AI.ClearTree();

if(AI.GetRoot()==NULL)

MessageBox(NULL,"Дерево уничтожено!","",0);

}

//---------------------------------------------------------------------------

void __fastcall TForm1::CountLeafExecute(TObject *Sender)

{

TreeNode* t=AI.GetRoot();

int count=0;

AI.CountLeaf(t, count);

Form1->Memo1->Lines->Add("Количество листьев - "+IntToStr(count));

}

//---------------------------------------------------------------------------

void __fastcall TForm1::DepthExecute(TObject *Sender)

{

TreeNode* t=AI.GetRoot();

int d=AI.Depth(t);

Form1->Memo1->Lines->Add("Глубина дерева - "+IntToStr(d));

}

//---------------------------------------------------------------------------

void __fastcall TForm1::FindExecute(TObject *Sender)

{

int key = StrToInt(LabeledEdit1->Text);

if(AI.Find(key))

Form1->Memo1->Lines->Add("Узел с ключом "+IntToStr(key)+" есть!");

else

Form1->Memo1->Lines->Add("Узла с ключом "+IntToStr(key)+" нет!");

}

//---------------------------------------------------------------------------

void __fastcall TForm1::DeleteExecute(TObject *Sender)

{

int k = StrToInt(LabeledEdit2->Text);

if(AI.Find(k))

{

AI.Delete(k);

Form1->Memo1->Lines->Add("Узел "+IntToStr(k)+" удален!");

}

else

Form1->Memo1->Lines->Add("Узла "+IntToStr(k)+" нет!");

}

//---------------------------------------------------------------------------

Тестирование и использование приложения

1.Запустите приложение на выполнение, нажав быстрые кнопки Сохранить все и Запуск.

2.Выполните тестирование по рис.8.5. Разница между заданным и фактическим количеством узлов в дереве объясняется тем, что узлы для последующих равных чисел не создаются.

3.Выполните тестирование по рис.8.6. Здесь вначале используется автоматический режим формирования дерева, а затем – ручной.

4.Создать дерево, а затем – копию этого дерева. Деревья вывести в окно.

5.Создать два дерева, а затем одно дерево присвоить другому. Правильность действий подтвердить выводом в окно.

6.Реализовать вертикальный вывод дерева в окно.

7.Реализовать сохранение дерева в файле.

8.Написать обработчики соответствующих событий по п.4…п.7 и дополнить интерфейс.

9.Полученные результаты продемонстрировать преподавателю.

Рис.8.5 – формирование дерева в автоматическом режиме

Рис.8.6 - формирование дерева в автоматическом и ручном режимах

Контрольные вопросы

1.Расскажите о назначении и содержании класса TreeNode.

2.Как выделяется и инициализируется память для узла дерева?

3.Укажите в коде использование функций Left() и Right(). Почему они объявлены константными?

4.Как выполняются конструктор и деструктор класса TreeNode?

5.Расскажите о назначении и содержании класса BinSTree.

6.С какой целью класс BinSTree объявлен другом класса TreeNode?

7.Как выполняются конструктор и деструктор класса BinSTree?

8.Как осуществляется поиск узла по ключу?

9.Как выполняется функция Find?

10.Как добавляется узел в дерево?

11.Как создать дерево в автоматическом режиме?

12.Как создать дерево в ручном режиме?

13.Как выводится дерево в окно?

14.Поясните назначение и выполнение функции FindNode.

15.Почему нужен указатель на родителя удаляемого узла?

16.Как находят заменяющий узел, когда удаляемый узел имеет оба поддерева?

17.Как происходит замена удаляемого узла, если заменяющий узел не является его сыном?

18.При выполнении какого условия заменяют корень?

19.Расскажите о назначении и выполнении функций Delete, DeleteTree, ClearTree, CopyTree, Depth, CountLeaf.

20.Как сохранить дерево в файле?

21.Как вывести дерево из файла?

22.Как выполняется перегруженная операция присваивания?

23.Как создать новое дерево – копию другого дерева?

24.Как присвоить одно дерево другому?

25.Как реализовать вертикальный вывод дерева?

Задания

1.Последовательность чисел представить в виде упорядоченного бинарного дерева. Вывести дерево и все его ветви на экран.

2.Массив из целых чисел представить в виде идеально сбалансированного бинарного дерева. Вывести дерево и слой с заданным ключом на экран.

3.Последовательность чисел представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и все ветви слоя с заданным ключом.

4.Массив из чисел представить в виде идеально сбалансированного бинарного дерева. Вывести на экран дерево и ту половину дерева, где находится заданный ключ - с вершины, а другую половину - с корня.

5.Последовательность букв представить в виде идеально сбалансированного бинарного дерева. Вывести на экран дерево и все слои дерева, начиная с вершины, а затем - с корня.

6.Массив из букв представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и номер того слоя, где находится заданная буква.

7.Массив из чисел представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и все его ветви, исходящие из слоя с заданным ключом.

8.Последовательность чисел представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и слой с минимальным ключом.

9.Последовательность чисел представить в виде упорядоченного бинарного дерева. Вывести на экран дерево и ветви, сумма ключей в которых превышает заданное число.

10.Последовательность букв представить в виде идеально сбалансированного дерева. Вывести на экран дерево и ветви с гласными буквами.

11.Массив строк представить в виде упорядоченного бинарного дерева. Вывести дерево и слои со строками одинаковой длины на экран.

12.Массив строк представить в виде идеально сбалансированного дерева. Вывести дерево, слой и ветвь со строкой максимальной длины на экран.

13.Два бинарных дерева зеркально подобны, если либо оба они пусты, либо оба непусты, и при этом левое поддерево одного из них подобно правому поддереву другого и наоборот. Определить, являются ли два дерева зеркально подобными.

14.Два бинарных дерева подобны, если либо оба они пусты, либо оба непусты, и при этом их левые и правые поддеревья подобны. Определить, являются ли два дерева подобными.

15.Составить программу, которая читает произвольный C-файл и печатает в алфавитном порядке каждую группу имен переменных, совпадающих в первых N символах, но различающихся где-либо дальше. При решении задачи использовать дерево с узлами вида: struct NODE{char* word; int k; NODE* left; NODE* right;};. (Слова внутри символьных строк и комментариев не рассматривать.)

16.Формулу вида <формула>::=<цифра>|(<формула><знак><формула>) <знак>::= + | - | * <цифра>::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 можно представить в виде бинарного дерева по следующим правилам: а)формула из одной цифры представляется деревом из одной вершины с этой цифрой; б)формула вида f1# f2 представляется деревом, в котором корень - это знак # соответствующей операции, а левое и правое поддеревья - это представления формул f1,f2 в виде бинарных деревьев. Например, формуле 5*(3+8) соответствует дерево

*

/ \

5 +

/ \

3 8

Требуется: а)построить дерево по формуле указанного выше вида; б)вычислить как целое число значение дерева-формулы; в)по заданному дереву распечатать соответствующую формулу.

17.Составить программу, формирующую “перекрестные списки”, т.е. печатающую список слов, которые встречаются в анализируемом файле, а для каждого слова - список номеров строк, в которых это слово встречается. При решении задачи рекомендуется использовать следующие структуры данных: struct LIST //список номеров строк для данного слова

{ int num; struct LIST* p; }

struct NODE //узел дерева с информацией об очередном слове

{ char* word; struct LIST*lines; struct NODE*left; struct NODE*right;}.

18.Распечатать слова текста, отсортированные в порядке убывания частоты их встречаемости (рядом с каждым словом выводить значение счетчика частоты его вхождений в текст). При решении задачи использовать дерево следующей структуры:

struct NODE

{char* word; int k; struct NODE* left; struct NODE* right;}.

19.В упорядоченном бинарном дереве удалить узел с указанным ключом.

20.В упорядоченном бинарном дереве удалить все листья.

21.Вывести упорядоченное бинарное дерево послойно, начиная с корня, сначала исходное, а затем – после удаления указанного слоя.

22.Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах содержат: номер УДК, фамилию и инициалы автора, название, год издания, количество экземпляров данной книги в библиотеке. Программа должна обеспечивать: а)начальное формирование данных о всех книгах в библиотеке в виде бинарного дерева; б)добавление данных о книгах, вновь поступающих в библиотеку; в)удаление данных о списываемых книгах; г)по запросу выдаются сведения о наличии книг в библиотеке, упорядоченные по годам издания.

23.Составить программу, которая содержит текущую информацию о заявках на авиабилеты. Каждая заявка содержит: пункт назначения, номер рейса, фамилию и инициалы пассажира, желаемую дату вылета. Программа должна обеспечивать: а)хранение всех заявок в виде бинарного дерева; б)добавление и удаление заявок; в) по заданному номеру рейса и дате вылета вывод заявок с их последующим удалением; г)вывод всех заявок.

24.Англо-русский словарь построен как бинарное дерево. Каждая компонента содержит английское слово, соответствующее ему русское слово и счетчик количества обращений к данной компоненте. Первоначально дерево формируется согласно английскому алфавиту. В процессе эксплуатации словаря при каждом обращении к компоненте в счетчик обращений добавляется единица. Составить программу, которая: 1)обеспечивает начальный ввод словаря с конкретными значениями счетчиков обращений; 2)формирует новое представление словаря в виде бинарного дерева по следующему алгоритму: а)в старом словаре находится компонента с наибольшим значением счетчика обращений, б)найденная компонента заносится в новый словарь и удаляется из старого, в)переход к п. ‘а)’ до исчерпания исходного словаря; 3)производит вывод исходного и нового словарей. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

25.На междугородной телефонной станции картотека абонентов, содержащая сведения о телефонах и их владельцах, организована как бинарное дерево. Составить программу, которая: 1)обеспечивает начальное формирование картотеки в виде бинарного дерева; 2)производит вывод всей картотеки; 3)вводит номер телефона и время разговора; 4)выводит извещение на оплату телефонного разговора. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

26.Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования. Для каждого поезда указывается: номер поезда, станция назначения, время отправления. Данные в информационной системе организованы в виде бинарного дерева. Составить программу, которая: 1)обеспечивает первоначальный ввод данных в информационную систему и формирование бинарного дерева; 2)производит вывод всего дерева; 3)вводит номер поезда и выводит все данные об этом поезде; 4)вводит название станции назначения и выводит данные обо всех поездах, следующих до этой станции. Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

27.Бинарное упорядоченное дерево стереть слой за слоем, начиная с максимально дальней вершины.

28.В идеально сбалансированном бинарном дереве удалить узел с заданным ключом.

29.По исходному бинарному дереву построить подобное дерево.

30.По исходному бинарному дереву построить зеркально подобное дерево.

ЛАБОРАТОРНАЯ РАБОТА 9