Реферат: Структуры данных: бинарное упорядоченное несбалансированное дерево

Казанский ГосударственныйТехнический Университет

им. А. Н. Туполева

Курсовая работа

по программированию

на тему

Структуры данных:

бинарное упорядоченное несбалансированное дерево

Выполнил: Зверев И. М.Проверил: Рахматуллин А. И.

Казань

2003

План работы:

1)    Постановказадачи

2)    Описаниепрограммы

3)    Кодпрограммы на языках Pascal иС++

1.         Постановка задачи

Требуется написать программу,реализующую основные операции работы с деревом. Причём, обязательным условиемявляется использование структуры данных класс для описания дерева и методовработы с ним.

2.         Описание программы

Описание ведётся для кода на Pascalе, отличия для С++ будут указаны ниже.

В программе основным элементомявляется класс TTree. Его методы – это основныепроцедуры работы с деревом:

Create – конструкторкласса – процедура, создающая дерево,

Add – метод добавления элемента вдерево,

Del – метод удаления элемента издерева,

View – метод вывода элементовдерева на экран,

Exist – метод проверкисуществования элемента с некоторым ключом, по сути поиск элемента,

Destroy – деструктор класса –процедура, удаляющая дерево.

Рассмотрим алгоритмы работыпроцедур.

Create – создание дерева. Присваивает полю Root (корень) значение nil – указателя, который никуда не указывает.

Add – добавление элемента в дерево. Дляпостроения дерева используем следующий алгоритм. Первый элемент помещаем вкорень (инициализируем дерево). Далее поступаем следующим образом. Если добавляемыйв дерево элемент имеет ключ больший, чем ключ узла, то, если узел не лист,обходим его справа. Если добавляемый элемент имеет ключ не больший чем ключузла, то, если узел не лист, обходим его слева. Если дошли до листа, тодобавляем элемент соответственно справа или слева.

Del – удаление элемента из дерева.

Удаление узладовольно просто если он является листом или имеет одного потомка. Например,если требуется удалить узел с ключом М надо просто заменить правую ссылку узлаК на указатель на L. Трудность заключается в удалении узла с двумя потомками,поскольку мы не можем указать одним указателем на два направления.

/>

/>Например, еслипросто удалить узел с ключом N, то левый указатель узла с ключом Т долженуказывать одновременно на К и R что не возможно. В этом случае удаляемый узелнужно заменить на другой узел из дерева. Возникает вопрос, каким же узлом егозаменить? Этот узел должен обладать двумя свойствами: во-первых, он должениметь не более одного потомка; во-вторых, для сохранения упорядоченностиключей, он должен иметь ключ либо не меньший, чем любой ключ левого поддереваудаляемого узла, либо не больший, чем любой ключ правого поддерева удаляемогоузла. Таким свойствам обладают два узла, самый правый узел левого поддереваудаляемого узла и самый левый узел его правого поддерева. Любым из этих узловим можно заменить удаляемый узел. Например, на рисунке это узлы М и Р.

/>Необходиморазличать три случая:

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

Вспомогательнаярекурсивная процедура del вызывается только в случае, когда удаляемый узелимеет двух потомков. Она “спускается вдоль” самой правой ветви левого поддереваудаляемого узла q^ (при вызове процедуры ей передается в качестве параметрауказатель на левое поддерево) и, затем, заменяет существенную информацию (внашем случае ключ data) в q^ соответствующим значением самого правого узла r^этого левого поддерева, после чего от r^ можно освободиться.

View — печатьдерева, обходя его справа налево. Чем дальше элемент от корня, тем больше емубудет предшествовать пробелов, т. о. путём несложного алгоритма получаетсявполне удобно читаемое дерево.

Exist – проверка существования элемента с заданным ключом.Ищем элемент, двигаясь от корня и переходя на левое или правое поддеревокаждого узла в зависимости от его ключа.

Destroy – удаление дерева. Обходя дерево слева направо,удаляет элементы. Сначала удаляются потомки узла, затем сам узел.

Различия междуописаниями кодов программах на разных языках относятся в основном кконструкторам и деструкторам. В .pas программахони определяются директивами и вызываются явно как методы класса из программы,а в .cpp конструктор вызывается при создании элементакласса и деструктор автоматически при выходе из программы (для чего объекткласса размещается в памяти динамически).

3.         Код программы

program PTree;

{$APPTYPE CONSOLE}

type

  TInfo = Byte;

  PItem = ^Item;

  Item = record

    Key: TInfo;

    Left, Right: PItem;

  end;

  TTree = class

     private

       Root: PItem;

     public

       constructor Create;

       procedure Add(Key: TInfo);

       procedure Del(Key: TInfo);

       procedure View;

       procedure Exist(Key: TInfo);

       destructor Destroy; override;

  end;

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

constructor TTree.Create;

begin

  Root := nil;

end;

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

procedure TTree.Add(Key: TInfo);

  procedure IniTree(var P: PItem; X: TInfo); //создание корня дерева

  begin

    New(P);

    P^.Key :=X;

    P^.Left := nil;

    P^.Right := nil;

  end;

  procedure InLeft (var P: PItem; X: TInfo); //добавление узла слева

  var R: PItem;

  begin

    New(R);

    R^.Key := X;

    R^.Left := nil;

    R^.Right := nil;

    P^.Left := R;

  end;

  procedure InRight (var P: PItem; X: TInfo); //добавить узел справа

  var R: PItem;

  begin

    New(R);

    R^.Key := X;

    R^.Left := nil;

    R^.Right := nil;

    P^.Right := R;

  end;

  procedure Tree_Add (P: PItem; X: TInfo);

  var OK: Boolean;

  begin

    OK := false;

    while not OK do begin

      if X > P^.Key then //посмотреть направо

        if P^.Right <> nil //правый узел не nil

          then P := P^.Right //обход справа

          else begin //правый узел — лист и надо добавить к нему элемент

            InRight (P, X); //и конец

            OK := true;

          end

      else //посмотреть налево

        if P^.Left <> nil //левый узел не nil

          then P := P^.Left //обход слева

          else begin //левый узел -лист и надо добавить к нему элемент

            InLeft(P, X); //и конец

            OK := true

          end;

    end; //цикла while

  end;

begin

  if Root = nil

    then IniTree(Root, Key)

    else Tree_Add(Root, Key);

end;

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

procedure TTree.Del(Key: TInfo);

  procedure Delete (var P: PItem; X: TInfo);

  var Q: PItem;

    procedure Del(var R: PItem);

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

    //узел левого поддерева

    begin

      if R^.Right <> nil then //обойти дерево справа

        Del(R^.Right)

      else begin

        //дошли до самого правого узла

        //заменить этим узлом удаляемый

<p/>

        Q^.Key := R^.Key;

        Q := R;

        R := R^.Left;

      end;

    end; //Del

  begin //Delete

    if P <> nil then //искать удаляемый узел

      if X < P^.Key then

        Delete(P^.Left, X)

      else

        if X > P^.Key then

          Delete(P^.Right, X) //искать в правом поддереве

        else begin

          //узел найден, надо его удалить

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

          Q := P;

          if Q^.Right = nil then

            //справа nil

            //и ссылку на узел надо заменить ссылкой на этого потомка

            P := Q^.Left

          else

            if Q^.Left = nil then

              //слева nil

              //и ссылку на узел надо заменить ссылкой на этого потомка

              P := P^.Right

            else //узел имеет двух потомков

              Del(Q^.Left);

          Dispose(Q);

        end

    else

      WriteLn('Такого элемента в дереве нет');

  end;

begin

  Delete(Root, Key);

end;

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

procedure TTree.View;

  procedure PrintTree(R: PItem; L: Byte);

  var i: Byte;

  begin

    if R <> nil then begin

      PrintTree(R^.Right, L + 3);

      for i := 1 to L do

        Write(' ');

      WriteLn(R^.Key);

      PrintTree(R^.Left, L + 3);

    end;

  end;

begin

  PrintTree (Root, 1);

end;

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

procedure TTree.Exist(Key: TInfo);

  procedure Search(var P: PItem; X: TInfo);

  begin

    if P = nil then begin

      WriteLn('Такого элемента нет');

    end else

      if X > P^. Key then //ищется в правом поддереве

        Search (P^. Right, X)

      else

        if X < P^. Key then

          Search (P^. Left, X)

        else

          WriteLn('Есть такой элемент');

  end;

begin

  Search(Root, Key);

end;

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

destructor TTree.Destroy;

  procedure Node_Dispose(P: PItem);

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

  begin

    if P <> nil then begin

      if P^.Left <> nil then

        Node_Dispose (P^.Left);

      if P^.Right <> nil then

        Node_Dispose (P^.Right);

      Dispose(P);

    end;

  end;

begin

  Node_Dispose(Root);

end;

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

procedure InputKey(S: String; var Key: TInfo);

begin

  WriteLn(S);

  ReadLn(Key);

end;

var

  Tree: TTree;

  N: Byte;

  Key: TInfo;

begin

  Tree := TTree.Create;

  repeat

    WriteLn('1-Добавить элемент в дерево');

    WriteLn('2-Удалить элемент');

    WriteLn('3-Вывести узлы дерева');

    WriteLn('4-Проверить существование узла');

    WriteLn('5-Выход');

    ReadLn(n);

    with Tree do begin

      case N of

        1: begin

             InputKey('Введите значение добавляемого элемента', Key);

             Add(Key);

           end;

        2: begin

             InputKey('Введите значение удаляемого элемента', Key);

             Del(Key);

           end;

        3: View;

        4: begin

             InputKey('Введите элемент, существование которого вы хотите проверить', Key);

             Exist(Key);

           end;

      end;

    end;

  until N=5;

  Tree.Destroy;

end.

#include <iostream.h>

#pragma hdrstop

typedef int TInfo;

typedef struct Item* PItem;

struct Item {

  TInfo Key;

  PItem Left, Right;

};

class TTree {

  private:

     PItem Root;

  public:

     TTree();

     void Add(TInfo Key);

     void Del(TInfo Key);

     void View();

     void Exist(TInfo Key);

     ~TTree();

};

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

TTree::TTree()

{

  Root = NULL;

}

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

static void IniTree(PItem& P, TInfo X) //создание корня дерева

{

  P = new Item;

  P->Key =X;

  P->Left = NULL;

  P->Right = NULL;

}

static void Iendleft (PItem& P, TInfo X) //добавление узла слева

{

    PItem R;

  R = new Item;

  R->Key = X;

  R->Left = NULL;

  R->Right = NULL;

  P->Left = R;

}

static void InRight (PItem& P, TInfo X) //добавить узел справа

{

    PItem R;

  R = new Item;

  R->Key = X;

  R->Left = NULL;

  R->Right = NULL;

  P->Right = R;

}

static void Tree_Add (PItem P, TInfo X)

{

  int OK;

  OK = false;

  while (! OK)  {

    if (X > P->Key)  //посмотреть направо

      if (P->Right != NULL) //правый узел не NULL

             P = P->Right; //обход справа

        else { //правый узел — лист и надо добавить к нему элемент

          InRight (P, X); //и конец

          OK = true;

        }

    else //посмотреть налево

      if (P->Left != NULL) //левый узел не NULL

             P = P->Left; //обход слева

        else { //левый узел -лист и надо добавить к нему элемент

          Iendleft(P, X); //и конец

          OK = true;

        }

  } //цикла while

}

void TTree::Add(TInfo Key)

{

  if (Root == NULL)

         IniTree(Root, Key);

    else Tree_Add(Root, Key);

}

//-------------------------------------------------------------static void delete_ (PItem& P, TInfo X);

static void Del(PItem& R, PItem& Q)

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

//узел левого поддерева

{

  if (R->Right != NULL)  //обойти дерево справа

    Del(R->Right, Q);

  else {

//дошли до самого правого узла

//заменить этим узлом удаляемый

    Q->Key = R->Key;

    Q = R;

    R = R->Left;

  }

} //Del

static void delete_ (PItem& P, TInfo X)

{

    PItem Q;

//Delete

  if (P != NULL)  //искать удаляемый узел

    if (X < P->Key)

      delete_(P->Left, X);

    else

      if (X > P->Key)

        delete_(P->Right, X); //искать в правом поддереве

<p/>

      else {

//узел найден, надо его удалить

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

        Q = P;

        if (Q->Right == NULL)

//справа NULL

//и ссылку на узел надо заменить ссылкой на этого потомка

          P = Q->Left;

        else

          if (Q->Left == NULL)

//слева NULL

//и ссылку на узел надо заменить ссылкой на этого потомка

            P = P->Right;

          else //узел имеет двух потомков

            Del(Q->Left, Q);

        delete Q;

      }

  else

    cout << «Такого элемента в дереве нет» << endl;

}

void TTree::Del(TInfo Key)

{

  delete_(Root, Key);

}

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

static void PrintTree(PItem R, TInfo L)

{

    int i;

  if (R != NULL)  {

    PrintTree(R->Right, L + 3);

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

      cout << ' ';

    cout << R->Key << endl;

    PrintTree(R->Left, L + 3);

  }

}

void TTree::View()

{

  PrintTree (Root, 1);

}

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

static void Search(PItem& P, TInfo X)

{

  if (P == NULL)  {

    cout << «Такого элемента нет» << endl;

  } else

    if (X > P-> Key)  //ищется в правом поддереве

      Search (P-> Right, X);

    else

      if (X < P-> Key)

        Search (P-> Left, X);

      else

        cout << «Есть такой элемент» << endl;

}

void TTree::Exist(TInfo Key)

{

  Search(Root, Key);

}

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

static void Node_Dispose(PItem P)

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

{

  if (P != NULL)  {

    if (P->Left != NULL)

      Node_Dispose (P->Left);

    if (P->Right != NULL)

      Node_Dispose (P->Right);

    delete P;

  }

}

TTree::~TTree()

{

  Node_Dispose(Root);

}

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

void inputKey(string S, TInfo& Key)

{

  cout << S << endl;

  cin >> Key;

}

TTree *Tree = new TTree;

int N;

TInfo Key;

int main(int argc, const char* argv[])

{

  do {

    cout << «1-Добавить элемент в дерево» << endl;

    cout << «2-Удалить элемент» << endl;

    cout << «3-Вывести узлы дерева» << endl;

    cout << «4-Проверить существование узла» << endl;

    cout << «5-Выход» << endl;

    cin >> N;

                 {

      switch (N) {

        case 1: {

             inputKey(«Введите значение добавляемого элемента», Key);

             Tree->Add(Key);

           }

           break;

        case 2: {

             inputKey(«Введите значение удаляемого элемента», Key);

             Tree->Del(Key);

           }

           break;

        case 3: Tree->View(); break;

        case 4: {

             inputKey(«Введите элемент, существование которого вы хотите проверить», Key);

             Tree->Exist(Key);

           }

           break;

      }

    }

  } while (!(N==5));

  return EXIT_SUCCESS;

}