Реализовать программу для работы с типом данных ”Дерево”

25.  if k > key [ t ]

26.    then right [ t ] ← AVL_Delete( right [ t ], k, hh, del )

27.            if hh=TRUE

28.                 then if bal [ t ] = 1

29.                             then bal [ t ] ← 0;

30.                                      h ← TRUE

31.                             else if bal [ t ] = 0

32.                                      then bal [ t ] ← -1

33.                                      else  if bal[left [ t ]] = 0

34.                                                  then t ← R( t )

35.                                                  else h ← TRUE

36                                                          if bal[left [ t ]] = -1

37.                                                            then t ← R( t )

38.                                                            else t ← LR( t )

39.           deleted ← del

40.           return t

41.   найден удаляемый узел t

42.  deleted ← TRUE

43.  if left [ t ] = nil and right [ t ] = nil

44.      then Delete_Node ( t )

45.               h ← TRUE

46.               return nil

47.  if left [ t ]= nil

48.      then x ← right [ t ]

49.              Delete_Node ( t )

50.              h ← TRUE

51.              return x

52.  if right [ t ] = nil

53.      then x ← left [ t ]

54.              Delete_Node ( t )

55.              h ← TRUE

56.              return x

57.  right [ t ] ← Del (right [ t ], t, hh)

58.  if hh = TRUE

59.      then if bal [ t ] = 1

60.                 then bal[t] ← 0

61.                         h ← TRUE

62.                 else if bal [ t ] = 0

63.                           then bal [ t ] ← -1

64.                           else x ← left [ t ]

65.                                   if bal[x] = 0

66.                                       then t ← R(t)

67.                                       else h ← TRUE

68                                               if bal[x] = -1

69.                                                 then t ← R( t )

70.                                                 else t ← LR( t )

71.  return t 

 

 

 

Del( t, t0, h )

1.  h ← FALSE

2.  if left [ t ] ≠ nil

3.      then left [ t ] ← Del (left [ t ], t0,hh)

4.              if hh = TRUE

5.                  then if bal [ t ] = -1

6.                              then bal[t] ← 0

7.                                      h  ← TRUE

8.                              else if bal [ t ] = 0

9.                                         then bal [ t ] ← 1

10.                                       else if bal[right [ t ]] = 0

11.                                                   then  t  ← L( t )

12.                                                   else h  ← TRUE

13.                                                          if bal[right [ t ]] = 1

11.                                                             then t  ← L( t )

12.                                                             else  t ← RL ( t )

13.            return t

14.    else key[ t0 ] ← key [ t ]

15.          data[ t0 ] ← data [ t ]

16.          x ← right [ t ]

17.          Delete_Node ( t )

18.          h  ← TRUE

19.          return x

3. Результаты  тестирования

Рис. 3.1. Создание простого бинарного дерева.

 

Рис. 3.2. Создание АВЛ-дерева.

 

Рис. 3.3. Добавление узла в созданное АВЛ-дерево.

 

Рис. 3.4. Удаление узла из АВЛ-дерева.

 

Рис. 3.5. Поиск элемента в дереве.

 

Рис. 3.6. Поиск упорядоченного поддерева максимальной глубины.

4. Исходный  код

Unit 1

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

 

#include <vcl.h>

#include <math.h>

#pragma hdrstop

 

#include "Unit1.h"

#include "Unit2.cpp"

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

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

 

cTree* curTree;

 

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

__fastcall TForm1::TForm1(TComponent* Owner)

        : TForm(Owner)

{

}

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

 

void __fastcall TForm1::elCountChange(TObject *Sender) //изменение размера массива

{

        int count = 0;

        if (!TryStrToInt(elCount->Text, count)) //проверка правильности ввода

        {

                if (!elCount->Text.IsEmpty())

                        ShowMessage("Ошибка ввода!");

        }

        else

                massGrid->ColCount = count;

}

 

void ClearPaintField() //очистка полотна

{

        Form1->Canvas->Pen->Color = clBlack;

        Form1->Canvas->Brush->Color = clWhite;

        TRect* rect = new TRect(390, 5, 930, 470);

        Form1->Canvas->Rectangle(*rect);

        Form1->Canvas->FillRect(*rect);

}

 

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

void __fastcall TForm1::crtBtnClick(TObject *Sender) //создание массива

{

        int i;    //индекс

        int count = massGrid->ColCount; //количество элементов в массиве

        float* mass = new float[count]; //указатель на массив

        bool isReady = true;

        for (i = 0; i < count ; i++)

        {

                float tmp = 0;

                if (!TryStrToFloat(massGrid->Cells[i][0], tmp)) //проверка правильности ввода

                {

                        if (massGrid->Cells[i][0] != "")

                        {

                                ShowMessage("Неправильный формат числа.");

                                free(mass);

                                isReady = false;

                                break;

                        }

                        else

                        {

                                massGrid->Cells[i][0] = 0;

                                tmp = 0;

                        }

                }

                mass[i] = tmp;

        }

        if (isReady) //если все данные введены правильно

        {

                if (curTree != NULL) //проверка на наличие старого дерева

                {

                        curTree->Destroy();

                        free(curTree);

                }

                curTree = new cTree(mass[0]); //сосздаем новое дерево

                for (i = 1; i < count; i++)

                        curTree->AddNode(mass[i], modeChkBox->Checked);

                ClearPaintField(); //очищаем полотно

                curTree->DrawTree(Form1); //рисуем дерево

        }

}

 

bool GetParams(float &key) //получение параметров поиска

{

        if (!TryStrToFloat(Form1->keyEdit->Text, key)) //проверка правильности ввода

        {

                ShowMessage("Неправильно задан искомый элемент.");

                return false;

        }

        if (curTree == NULL) //проверка на наличие дерева

        {

                ShowMessage("Дерево не задано.");

                return false;

        }

        return true;

}

 

void __fastcall TForm1::clrBtnClick(TObject *Sender) //очистка полей ввода массива

{

        for (int i = 0; i < massGrid->ColCount; i++)

                massGrid->Cells[i][0] = "";

}

 

 

 

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

 

void __fastcall TForm1::SvTFlBtnClick(TObject *Sender) //открытие диалога сохранения файла

{

        SaveDialog1->Execute();

}

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

 

void __fastcall TForm1::SaveDialog1CanClose(TObject *Sender,

      bool &CanClose) //сохранение файла

{

        outputMemo->Lines->SaveToFile(SaveDialog1->FileName);

}

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

 

 

 

 

void __fastcall TForm1::SrchBtnClick(TObject *Sender) //поиск узла по заданому ключу

{

        float key;

        if (GetParams(key)) //получение параметров

        {

                cNode* node = curTree->Find(key); //поиск

                if (node != NULL) //проверка на результат

                        outputMemo->Lines->Add(node->ToString());

                else

                        outputMemo->Lines->Add("Элемент не найден.");

        }

}

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

 

void __fastcall TForm1::minSrchBtnClick(TObject *Sender) //поиск минимального узла

{

        if (curTree == NULL) //проверка на наличие дерева

                ShowMessage("Дерево не задано.");

        else

                outputMemo->Lines->Add(curTree->FindMin()->ToString());

}

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

 

void __fastcall TForm1::maxSrchBtnClick(TObject *Sender) //поиск максимального узла

{

        if (curTree == NULL) //проверка на наличие дерева

                ShowMessage("Дерево не задано.");

        else

                outputMemo->Lines->Add(curTree->FindMax()->ToString());

}

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

 

void __fastcall TForm1::addBtnClick(TObject *Sender) //добавление узла

{

        if (curTree == NULL) //проверка на наличие дерева

        {

                ShowMessage("Дерево не задано.");

                return;

        }

        float key;

        if (!TryStrToFloat(Form1->addKeyEdit->Text, key)) //проверка правильности ввода

        {

                ShowMessage("Неправильно задан добавляемый элемент.");

                return;

        }

        curTree->AddNode(key, modeChkBox->Checked); //добавляем узел

        ClearPaintField(); //очищаем полотно

        curTree->DrawTree(Form1); //рисуем дерево

}

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

 

void __fastcall TForm1::delBtnClick(TObject *Sender) //удаление узла

{

        if (curTree == NULL) //проверка на наличие дерева

        {

                ShowMessage("Дерево не задано.");

                return;

        }

        float key;

        if (!TryStrToFloat(Form1->addKeyEdit->Text, key)) //проверка правильности ввода

        {

                ShowMessage("Неправильно задан добавляемый элемент.");

                return;

        }

        if (curTree->DeleteNode(key, modeChkBox->Checked)) //удаляем узел