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

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

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

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

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

на тему

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

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

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

Казань

2003

<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">

План работы:

1)<span Times New Roman"">     

2)<span Times New Roman"">     

3)<span Times New Roman"">     

Pascalи С++<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">

1.<span Times New Roman"">                 

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

<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">

2.<span Times New Roman"">                 

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

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

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

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

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

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

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

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

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

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

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

<st1:State w:st=«on»><st1:place w:st=«on»>Del</st1:place></st1:State>– удаление элемента из дерева.

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

<img src="/cache/referats/13503/image001.gif" v:shapes="_x0000_i1025">

<img src="/cache/referats/13503/image003.gif" vspace=«5» v:shapes="_x0000_i1026">

<img src="/cache/referats/13503/image003.gif" vspace=«5» v:shapes="_x0000_i1027">

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

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

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

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

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

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

<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">

3.<span Times New Roman"">                 

<span Courier New"; mso-ansi-language:EN-US">program PTree;

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">{$APPTYPE CONSOLE}

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">type

<span Courier New"; mso-ansi-language:EN-US">  TInfo = Byte;

<span Courier New"; mso-ansi-language:EN-US">  PItem = ^Item;

<span Courier New"; mso-ansi-language:EN-US">  Item = record

<span Courier New"; mso-ansi-language:EN-US">    Key: TInfo;

<span Courier New"; mso-ansi-language:EN-US">    Left, Right: PItem;

<span Courier New"; mso-ansi-language:EN-US">  end;

<span Courier New"; mso-ansi-language:EN-US">  TTree = class

<span Courier New"; mso-ansi-language:EN-US">     private

<span Courier New"; mso-ansi-language:EN-US">       Root: PItem;

<span Courier New"; mso-ansi-language:EN-US">     public

<span Courier New"; mso-ansi-language:EN-US">       constructor Create;

<span Courier New"; mso-ansi-language:EN-US">       procedure Add(Key: TInfo);

<span Courier New"; mso-ansi-language:EN-US">       procedure <st1:State w:st=«on»><st1:place w:st=«on»>Del</st1:place></st1:State>(Key: TInfo);

<span Courier New"; mso-ansi-language:EN-US">       procedure View;

<span Courier New"; mso-ansi-language:EN-US">       procedure Exist(Key: TInfo);

<span Courier New"; mso-ansi-language:EN-US">       destructor Destroy; override;

<span Courier New"; mso-ansi-language:EN-US">  end;

<span Courier New"; mso-ansi-language:EN-US">//-------------------------------------------------------------

<span Courier New"; mso-ansi-language:EN-US">constructor TTree.Create;

<span Courier New"; mso-ansi-language:EN-US">begin

<span Courier New"; mso-ansi-language:EN-US">  Root := nil;

<span Courier New"; mso-ansi-language:EN-US">end;

<span Courier New"; mso-ansi-language:EN-US">//-------------------------------------------------------------

<span Courier New"; mso-ansi-language:EN-US">procedure TTree.Add(Key: TInfo);

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">  procedure IniTree(var P: PItem; X: TInfo); //

<span Courier New"">создание<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">корня<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">дерева<span Courier New";mso-ansi-language: EN-US">

<span Courier New"; mso-ansi-language:EN-US">  begin

<span Courier New"; mso-ansi-language:EN-US">    New(P);

<span Courier New"; mso-ansi-language:EN-US">    P^.Key :=X;

<span Courier New"; mso-ansi-language:EN-US">    P^.Left := nil;

<span Courier New"; mso-ansi-language:EN-US">    P^.Right := nil;

<span Courier New"; mso-ansi-language:EN-US">  end;

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">  procedure InLeft (var P: PItem; X: TInfo); //

<span Courier New"">добавление<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">узла<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">слева<span Courier New";mso-ansi-language: EN-US">

<span Courier New"; mso-ansi-language:EN-US">  var R: PItem;

<span Courier New"; mso-ansi-language:EN-US">  begin

<span Courier New"; mso-ansi-language:EN-US">    New(R);

<span Courier New"; mso-ansi-language:EN-US">    R^.Key := X;

<span Courier New"; mso-ansi-language:EN-US">    R^.Left := nil;

<span Courier New"; mso-ansi-language:EN-US">    R^.Right := nil;

<span Courier New"; mso-ansi-language:EN-US">    P^.Left := R;

<span Courier New"; mso-ansi-language:EN-US">  end;

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">  procedure InRight (var P: PItem; X: TInfo); //

<span Courier New"">добавить<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">узел<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">справа<span Courier New";mso-ansi-language: EN-US">

<span Courier New"; mso-ansi-language:EN-US">  var R: PItem;

<span Courier New"; mso-ansi-language:EN-US">  begin

<span Courier New"; mso-ansi-language:EN-US">    New(R);

<span Courier New"; mso-ansi-language:EN-US">    R^.Key := X;

<span Courier New"; mso-ansi-language:EN-US">    R^.Left := nil;

<span Courier New"; mso-ansi-language:EN-US">    R^.Right := nil;

<span Courier New"; mso-ansi-language:EN-US">    P^.Right := R;

<span Courier New"; mso-ansi-language:EN-US">  end;

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">  procedure Tree_Add (P: PItem; X: TInfo);

<span Courier New"; mso-ansi-language:EN-US">  var OK: Boolean;

<span Courier New"; mso-ansi-language:EN-US">  begin

<span Courier New"; mso-ansi-language:EN-US">    OK := false;

<span Courier New"; mso-ansi-language:EN-US">    while not OK do begin

<span Courier New"; mso-ansi-language:EN-US">     

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

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

<span Courier New"">          then P := P^.Right //обход справа

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

<span Courier New"">            InRight (P, X); //и конец

<span Courier New"">            OK := true;

<span Courier New"">          end

<span Courier New"">      else //посмотреть налево

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

<span Courier New"">          then P := P^.Left //обход слева

<span Courier New"">          else begin //левый узел -лист и надо добавить к нему элемент

<span Courier New"">            InLeft(P, X); //и конец

<span Courier New"">           

<span Courier New";mso-ansi-language:EN-US">OK := true

<span Courier New"; mso-ansi-language:EN-US">          end;

<span Courier New"; mso-ansi-language:EN-US">    end; //

<span Courier New"">цикла<span Courier New";mso-ansi-language: EN-US"> while

<span Courier New"; mso-ansi-language:EN-US">  end;

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">begin

<span Courier New"; mso-ansi-language:EN-US">  if Root = nil

<span Courier New"; mso-ansi-language:EN-US">    then IniTree(Root, Key)

<span Courier New"; mso-ansi-language:EN-US">    else Tree_Add(Root, Key);

<span Courier New"; mso-ansi-language:EN-US">end;

<span Courier New"; mso-ansi-language:EN-US">//-------------------------------------------------------------

<span Courier New"; mso-ansi-language:EN-US">procedure TTree.Del(Key: TInfo);

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">  procedure Delete (var P: PItem; X: TInfo);

<span Courier New"; mso-ansi-language:EN-US">  var Q: PItem;

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">    procedure <st1:State w:st=«on»><st1:place w:st=«on»>Del</st1:place></st1:State>(var R: PItem);

<span Courier New"; mso-ansi-language:EN-US">   

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

<span Courier New"">    //узел левого поддерева

<span Courier New"">    begin

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

<span Courier New"">       

<st1:State w:st=«on»><st1:place w:st=«on»><span Courier New"; mso-ansi-language:EN-US">Del</st1:place></st1:State><span Courier New";mso-ansi-language: EN-US">(R^.Right)

<span Courier New"; mso-ansi-language:EN-US">      else begin

<span Courier New"; mso-ansi-language:EN-US">       

<span Courier New"">//дошли до самого правого узла

<span Courier New"">        //заменить этим узлом удаляемый

<span Courier New"">

<span Courier New"">        Q^.Key := R^.Key;

<span Courier New"">       

<span Courier New";mso-ansi-language:EN-US">Q := R;

<span Courier New"; mso-ansi-language:EN-US">        R := R^.Left;

<span Courier New"; mso-ansi-language:EN-US">      end;

<span Courier New"; mso-ansi-language:EN-US">    end; //Del

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">  begin //Delete

<span Courier New"; mso-ansi-language:EN-US">    if P <> nil then //

<span Courier New"">искать<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">удаляемый<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">узел<span Courier New";mso-ansi-language: EN-US">

<span Courier New"; mso-ansi-language:EN-US">      if X < P^.Key then

<span Courier New"; mso-ansi-language:EN-US">        Delete(P^.Left, X)

<span Courier New"; mso-ansi-language:EN-US">      else

<span Courier New"; mso-ansi-language:EN-US">        if X > P^.Key then

<span Courier New"; mso-ansi-language:EN-US">         

<span Courier New"">Delete<span Courier New"">(P^.Right, X) //искать в правом поддереве

<span Courier New"">        else begin

<span Courier New"">          //узел найден, надо его удалить

<span Courier New"">          //сохранить ссылку на удаленный узел

<span Courier New"">          

<span Courier New";mso-ansi-language:EN-US">Q := P;

<span Courier New"; mso-ansi-language:EN-US">          if Q^.Right = nil then

<span Courier New"; mso-ansi-language:EN-US">           

<span Courier New"">//справа nil

<span Courier New"">            //и ссылку на узел надо заменить ссылкой на этого потомка

<span Courier New"">           

<span Courier New";mso-ansi-language:EN-US">P := Q^.Left

<span Courier New"; mso-ansi-language:EN-US">          else

<span Courier New"; mso-ansi-language:EN-US">            if Q^.Left = nil then

<span Courier New"; mso-ansi-language:EN-US">             

<span Courier New"">//слева nil

<span Courier New"">              //и ссылку на узел надо заменить ссылкой на этого потомка

<span Courier New"">              P := P^.Right

<span Courier New"">            else //узел имеет двух потомков

<span Courier New"">             

<st1:State w:st=«on»><st1:place w:st=«on»><span Courier New"; mso-ansi-language:EN-US">Del</st1:place></st1:State><span Courier New";mso-ansi-language: EN-US">(Q^.Left);

<span Courier New"; mso-ansi-language:EN-US">          Dispose(Q);

<span Courier New"; mso-ansi-language:EN-US">       

<span Courier New"">end<span Courier New"">

<span Courier New"">    else

<span Courier New"">      WriteLn('Такого элемента в дереве нет');

<span Courier New""> 

<span Courier New";mso-ansi-language:EN-US">end;

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">begin

<span Courier New"; mso-ansi-language:EN-US">  Delete(Root, Key);

<span Courier New"; mso-ansi-language:EN-US">end;

<span Courier New"; mso-ansi-language:EN-US">//-------------------------------------------------------------

<span Courier New"; mso-ansi-language:EN-US">procedure TTree.View;

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">  procedure PrintTree(R: PItem; L: Byte);

<span Courier New"; mso-ansi-language:EN-US">  var i: Byte;

<span Courier New"; mso-ansi-language:EN-US">  begin

<span Courier New"; mso-ansi-language:EN-US">    if R <> nil then begin

<span Courier New"; mso-ansi-language:EN-US">      PrintTree(R^.Right, L + 3);

<span Courier New"; mso-ansi-language:EN-US">      for i := 1 to L do

<span Courier New"; mso-ansi-language:EN-US">        Write(' ');

<span Courier New"; mso-ansi-language:EN-US">      WriteLn(R^.Key);

<span Courier New"; mso-ansi-language:EN-US">      PrintTree(R^.Left, L + 3);

<span Courier New"; mso-ansi-language:EN-US">    end;

<span Courier New"; mso-ansi-language:EN-US">  end;

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">begin

<span Courier New"; mso-ansi-language:EN-US">  PrintTree (Root, 1);

<span Courier New"; mso-ansi-language:EN-US">end;

<span Courier New"; mso-ansi-language:EN-US">//-------------------------------------------------------------

<span Courier New"; mso-ansi-language:EN-US">procedure TTree.Exist(Key: TInfo);

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">  procedure Search(var P: PItem; X: TInfo);

<span Courier New"; mso-ansi-language:EN-US">  begin

<span Courier New"; mso-ansi-language:EN-US">    if P = nil then begin

<span Courier New"; mso-ansi-language:EN-US">     

<span Courier New"">WriteLn<span Courier New"">('Такого элемента нет');

<span Courier New"">    end else

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

<span Courier New"">       

<span Courier New";mso-ansi-language:EN-US">Search (P^. Right, X)

<span Courier New"; mso-ansi-language:EN-US">      else

<span Courier New"; mso-ansi-language:EN-US">        if X < P^. Key then

<span Courier New"; mso-ansi-language:EN-US">          Search (P^. Left, X)

<span Courier New"; mso-ansi-language:EN-US">        else

<span Courier New"; mso-ansi-language:EN-US">         

<span Courier New"">WriteLn<span Courier New"">('Есть такой элемент');

<span Courier New"">  end;

<span Courier New"">

<span Courier New"; mso-ansi-language:EN-US">begin

<span Courier New"; mso-ansi-language:EN-US">  Search(Root, Key);

<span Courier New"; mso-ansi-language:EN-US">end;

<span Courier New"; mso-ansi-language:EN-US">//-------------------------------------------------------------

<span Courier New"; mso-ansi-language:EN-US">destructor TTree.Destroy;

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">  procedure Node_Dispose(P: PItem);

<span Courier New"; mso-ansi-language:EN-US"> 

<span Courier New"">//Удаление узла и всех его потомков в дереве

<span Courier New""> 

<span Courier New";mso-ansi-language:EN-US">begin

<span Courier New"; mso-ansi-language:EN-US">    if P <> nil then begin

<span Courier New"; mso-ansi-language:EN-US">      if P^.Left <> nil then

<span Courier New"; mso-ansi-language:EN-US">        Node_Dispose (P^.Left);

<span Courier New"; mso-ansi-language:EN-US">      if P^.Right <> nil then

<span Courier New"; mso-ansi-language:EN-US">        Node_Dispose (P^.Right);

<span Courier New"; mso-ansi-language:EN-US">      Dispose(P);

<span Courier New"; mso-ansi-language:EN-US">    end;

<span Courier New"; mso-ansi-language:EN-US">  end;

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">begin

<span Courier New"; mso-ansi-language:EN-US">  Node_Dispose(Root);

<span Courier New"; mso-ansi-language:EN-US">end;

<span Courier New"; mso-ansi-language:EN-US">//-------------------------------------------------------------

<span Courier New"; mso-ansi-language:EN-US">procedure InputKey(S: String; var Key: TInfo);

<span Courier New"; mso-ansi-language:EN-US">begin

<span Courier New"; mso-ansi-language:EN-US">  WriteLn(S);

<span Courier New"; mso-ansi-language:EN-US">  ReadLn(Key);

<span Courier New"; mso-ansi-language:EN-US">end;

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New";mso-ansi-language:EN-US">var

<span Courier New";mso-ansi-language: EN-US">

<span Courier New"; mso-ansi-language:EN-US">  Tree: TTree;

<span Courier New"; mso-ansi-language:EN-US">  N: Byte;

<span Courier New"; mso-ansi-language:EN-US">  Key: TInfo;

<span Courier New"; mso-ansi-language:EN-US">begin

<span Courier New"; mso-ansi-language:EN-US">  Tree := TTree.Create;

<span Courier New"; mso-ansi-language:EN-US"> 

<span Courier New"">repeat<span Courier New"">

<span Courier New"">    WriteLn('1-Добавить элемент в дерево');

<span Courier New"">    WriteLn('2-Удалить элемент');

<span Courier New"">    WriteLn('3-Вывести узлы дерева');

<span Courier New"">    WriteLn('4-Проверить существование узла');

<span Courier New"">   

<span Courier New";mso-ansi-language: EN-US">WriteLn<span Courier New";mso-ansi-language:EN-US">('5-<span Courier New"">Выход<span Courier New";mso-ansi-language: EN-US">');

<span Courier New"; mso-ansi-language:EN-US">    ReadLn(n);

<span Courier New"; mso-ansi-language:EN-US">    with Tree do begin

<span Courier New"; mso-ansi-language:EN-US">      case N of

<span Courier New"; mso-ansi-language:EN-US">       

<span Courier New"">1: begin

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

<span Courier New"">             Add(Key);

<span Courier New"">           end;

<span Courier New"">        2: begin

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

<span Courier New"">            

<st1:State w:st=«on»><st1:place w:st=«on»><span Courier New"; mso-ansi-language:EN-US">Del</st1:place></st1:State><span Courier New";mso-ansi-language: EN-US">(Key);

<span Courier New"; mso-ansi-language:EN-US">           end;

<span Courier New"; mso-ansi-language:EN-US">        3: View;

<span Courier New"; mso-ansi-language:EN-US">        4: begin

<span Courier New"; mso-ansi-language:EN-US">             

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

<span Courier New"">            

<span Courier New";mso-ansi-language:EN-US">Exist(Key);

<span Courier New"; mso-ansi-language:EN-US">           end;

<span Courier New"; mso-ansi-language:EN-US">      end;

<span Courier New"; mso-ansi-language:EN-US">    end;

<span Courier New"; mso-ansi-language:EN-US">  until N=5;

<span Courier New"; mso-ansi-language:EN-US">  Tree.Destroy;

<span Courier New"; mso-ansi-language:EN-US">end.

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">#include <iostream.h>

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">#pragma hdrstop

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New";mso-ansi-language:EN-US">typedef

<span Courier New";mso-ansi-language: EN-US"> int TInfo;

<span Courier New";mso-ansi-language:EN-US">typedef

<span Courier New";mso-ansi-language: EN-US"> struct Item* PItem;

<span Courier New";mso-ansi-language:EN-US">struct

<span Courier New";mso-ansi-language: EN-US"> Item {

<span Courier New"; mso-ansi-language:EN-US">  TInfo Key;

<span Courier New"; mso-ansi-language:EN-US">  PItem Left, Right;

<span Courier New"; mso-ansi-language:EN-US">};

<span Courier New"; mso-ansi-language:EN-US">class TTree {

<span Courier New"; mso-ansi-language:EN-US">  private:

<span Courier New"; mso-ansi-language:EN-US">     PItem Root;

<span Courier New"; mso-ansi-language:EN-US">  public:

<span Courier New"; mso-ansi-language:EN-US">     TTree();

<span Courier New"; mso-ansi-language:EN-US">     void Add(TInfo Key);

<span Courier New"; mso-ansi-language:EN-US">     void <st1:State w:st=«on»><st1:place w:st=«on»>Del</st1:place></st1:State>(TInfo Key);

<span Courier New"; mso-ansi-language:EN-US">     void View();

<span Courier New"; mso-ansi-language:EN-US">     void Exist(TInfo Key);

<span Courier New"; mso-ansi-language:EN-US">     ~TTree();

<span Courier New"; mso-ansi-language:EN-US">};

<span Courier New"">

<span Courier New"; mso-ansi-language:EN-US">//-------------------------------------------------------------

<span Courier New";mso-ansi-language:EN-US">TTree::TTree

<span Courier New";mso-ansi-language: EN-US">()

<span Courier New"; mso-ansi-language:EN-US">{

<span Courier New"; mso-ansi-language:EN-US">  Root = NULL;

<span Courier New"; mso-ansi-language:EN-US">}

<span Courier New"; mso-ansi-language:EN-US">//-------------------------------------------------------------

<span Courier New"; mso-ansi-language:EN-US">static void IniTree(PItem& P, TInfo X) //

<span Courier New"">создание<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">корня<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">дерева<span Courier New";mso-ansi-language: EN-US">

<span Courier New"; mso-ansi-language:EN-US">{

<span Courier New"; mso-ansi-language:EN-US">  P = new Item;

<span Courier New"; mso-ansi-language:EN-US">  P->Key =X;

<span Courier New"; mso-ansi-language:EN-US">  P->Left = NULL;

<span Courier New"; mso-ansi-language:EN-US">  P->Right = NULL;

<span Courier New"; mso-ansi-language:EN-US">}

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">static void Iendleft (PItem& P, TInfo X) //

<span Courier New"">добавление<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">узла<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">слева<span Courier New";mso-ansi-language: EN-US">

<span Courier New"; mso-ansi-language:EN-US">{

<span Courier New"; mso-ansi-language:EN-US">    PItem R;

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">  R = new Item;

<span Courier New"; mso-ansi-language:EN-US">  R->Key = X;

<span Courier New"; mso-ansi-language:EN-US">  R->Left = NULL;

<span Courier New"; mso-ansi-language:EN-US">  R->Right = NULL;

<span Courier New"; mso-ansi-language:EN-US">  P->Left = R;

<span Courier New"; mso-ansi-language:EN-US">}

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">static void InRight (PItem& P, TInfo X) //

<span Courier New"">добавить<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">узел<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">справа<span Courier New";mso-ansi-language: EN-US">

<span Courier New"; mso-ansi-language:EN-US">{

<span Courier New"; mso-ansi-language:EN-US">    PItem R;

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">  R = new Item;

<span Courier New"; mso-ansi-language:EN-US">  R->Key = X;

<span Courier New"; mso-ansi-language:EN-US">  R->Left = NULL;

<span Courier New"; mso-ansi-language:EN-US">  R->Right = NULL;

<span Courier New"; mso-ansi-language:EN-US">  P->Right = R;

<span Courier New"; mso-ansi-language:EN-US">}

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">static void Tree_Add (PItem P, TInfo X)

<span Courier New"; mso-ansi-language:EN-US">{

<span Courier New"; mso-ansi-language:EN-US">  int OK;

<span Courier New"; mso-ansi-language:EN-US">  OK = false;

<span Courier New"; mso-ansi-language:EN-US">  while (!

<span Courier New"">OK)  {

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

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

<span Courier New"">             P = P->Right; //обход справа

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

<span Courier New"">          InRight (P, X); //и конец

<span Courier New"">          OK = true;

<span Courier New"">        }

<span Courier New"">    else //посмотреть налево

<span Courier New"">      if (P->Left != NULL) //левый узел не NULL

<span Courier New"">             P = P->Left; //обход слева

<span Courier New"">        else { //левый узел -лист и надо добавить к нему элемент

<span Courier New"">          Iendleft(P, X); //и конец

<span Courier New"">         

<span Courier New";mso-ansi-language:EN-US">OK = true;

<span Courier New"; mso-ansi-language:EN-US">        }

<span Courier New"; mso-ansi-language:EN-US">  } //

<span Courier New"">цикла<span Courier New";mso-ansi-language: EN-US"> while

<span Courier New"; mso-ansi-language:EN-US">}

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">void TTree::Add(TInfo Key)

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">{

<span Courier New"; mso-ansi-language:EN-US">  if (Root == NULL)

<span Courier New"; mso-ansi-language:EN-US">         IniTree(Root, Key);

<span Courier New"; mso-ansi-language:EN-US">    else Tree_Add(Root, Key);

<span Courier New"; mso-ansi-language:EN-US">}

<span Courier New"; mso-ansi-language:EN-US">//-------------------------------------------------------------static void delete_ (PItem& P, TInfo X);

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">static void <st1:State w:st=«on»><st1:place w:st=«on»>Del</st1:place></st1:State>(PItem& R, PItem& Q)

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

<span Courier New"">//узел левого поддерева

<span Courier New"">{

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

<span Courier New"">    Del(R->Right, Q);

<span Courier New"">  else {

<span Courier New"">//дошли до самого правого узла

<span Courier New"">//заменить этим узлом удаляемый

<span Courier New"">    Q->Key = R->Key;

<span Courier New"">   

<span Courier New";mso-ansi-language:EN-US">Q = R;

<span Courier New"; mso-ansi-language:EN-US">    R = R->Left;

<span Courier New"; mso-ansi-language:EN-US">  }

<span Courier New"; mso-ansi-language:EN-US">} //Del

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">static void delete_ (PItem& P, TInfo X)

<span Courier New"; mso-ansi-language:EN-US">{

<span Courier New"; mso-ansi-language:EN-US">    PItem Q;

<span Courier New"; mso-ansi-language:EN-US">//Delete

<span Courier New"; mso-ansi-language:EN-US">  if (P !=

<span Courier New"">NULL)  //искать удаляемый узел

<span Courier New"">    if (X < P->Key)

<span Courier New"">     

<span Courier New";mso-ansi-language:EN-US">delete_(P->Left, X);

<span Courier New"; mso-ansi-language:EN-US">    else

<span Courier New"; mso-ansi-language:EN-US">     

<span Courier New"">if<span Courier New""> (X > P->Key)

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

<span Courier New"">

<span Courier New"">      else {

<span Courier New"">//узел найден, надо его удалить

<span Courier New"">//сохранить ссылку на удаленный узел

<span Courier New"">       

<span Courier New";mso-ansi-language:EN-US">Q = P;

<span Courier New"; mso-ansi-language:EN-US">        if (Q->Right == NULL)

<span Courier New"">//справа NULL

<span Courier New"">//и ссылку на узел надо заменить ссылкой на этого потомка

<span Courier New"">         

<span Courier New";mso-ansi-language:EN-US">P = Q->Left;

<span Courier New"; mso-ansi-language:EN-US">        else

<span Courier New"; mso-ansi-language:EN-US">          if (Q->Left == NULL)

<span Courier New"">//слева NULL

<span Courier New"">//и ссылку на узел надо заменить ссылкой на этого потомка

<span Courier New"">            P = P->Right;

<span Courier New"">          else //узел имеет двух потомков

<span Courier New"">           

<st1:State w:st=«on»><st1:place w:st=«on»><span Courier New"; mso-ansi-language:EN-US">Del</st1:place></st1:State><span Courier New";mso-ansi-language: EN-US">(Q->Left, Q);

<span Courier New"; mso-ansi-language:EN-US">        delete Q;

<span Courier New"; mso-ansi-language:EN-US">     

<span Courier New"">}

<span Courier New"">  else

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

<span Courier New"; mso-ansi-language:EN-US">}

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">void TTree::Del(TInfo Key)

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">{

<span Courier New"; mso-ansi-language:EN-US">  delete_(Root, Key);

<span Courier New"; mso-ansi-language:EN-US">}

<span Courier New"; mso-ansi-language:EN-US">//-------------------------------------------------------------

<span Courier New"; mso-ansi-language:EN-US">static void PrintTree(PItem R, TInfo L)

<span Courier New"; mso-ansi-language:EN-US">{

<span Courier New"; mso-ansi-language:EN-US">    int i;

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">  if (R != NULL)  {

<span Courier New"; mso-ansi-language:EN-US">    PrintTree(R->Right, L + 3);

<span Courier New"; mso-ansi-language:EN-US">    for( i = 1; i <= L; i ++)

<span Courier New"; mso-ansi-language:EN-US">      cout << ' ';

<span Courier New"; mso-ansi-language:EN-US">    cout << R->Key << endl;

<span Courier New"; mso-ansi-language:EN-US">    PrintTree(R->Left, L + 3);

<span Courier New"; mso-ansi-language:EN-US">  }

<span Courier New"; mso-ansi-language:EN-US">}

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">void TTree::View()

<span Courier New"; mso-ansi-language:EN-US">{

<span Courier New"; mso-ansi-language:EN-US">  PrintTree (Root, 1);

<span Courier New"; mso-ansi-language:EN-US">}

<span Courier New"; mso-ansi-language:EN-US">//-------------------------------------------------------------

<span Courier New"; mso-ansi-language:EN-US">static void Search(PItem& P, TInfo X)

<span Courier New"">{

<span Courier New"">  if (P == NULL)  {

<span Courier New"">    cout << «Такого элемента нет» << endl;

<span Courier New"">  } else

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

<span Courier New"">     

<span Courier New";mso-ansi-language:EN-US">Search (P-> Right, X);

<span Courier New"; mso-ansi-language:EN-US">    else

<span Courier New"; mso-ansi-language:EN-US">      if (X < P-> Key)

<span Courier New"; mso-ansi-language:EN-US">        Search (P-> Left, X);

<span Courier New"; mso-ansi-language:EN-US">     

<span Courier New"">else<span Courier New"">

<span Courier New"">        cout << «Есть такой элемент» << endl;

<span Courier New"; mso-ansi-language:EN-US">}

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">void TTree::Exist(TInfo Key)

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">{

<span Courier New"; mso-ansi-language:EN-US">  Search(Root, Key);

<span Courier New"; mso-ansi-language:EN-US">}

<span Courier New"; mso-ansi-language:EN-US">//-------------------------------------------------------------

<span Courier New"; mso-ansi-language:EN-US">static void Node_Dispose(PItem P)

<span Courier New"">//Удаление узла и всех его потомков в дереве

<span Courier New"; mso-ansi-language:EN-US">{

<span Courier New"; mso-ansi-language:EN-US">  if (P != NULL)  {

<span Courier New"; mso-ansi-language:EN-US">    if (P->Left != NULL)

<span Courier New"; mso-ansi-language:EN-US">      Node_Dispose (P->Left);

<span Courier New"; mso-ansi-language:EN-US">    if (P->Right != NULL)

<span Courier New"; mso-ansi-language:EN-US">      Node_Dispose (P->Right);

<span Courier New"; mso-ansi-language:EN-US">    delete P;

<span Courier New"; mso-ansi-language:EN-US">  }

<span Courier New"; mso-ansi-language:EN-US">}

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New";mso-ansi-language:EN-US">TTree::~TTree

<span Courier New";mso-ansi-language: EN-US">()

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New"; mso-ansi-language:EN-US">{

<span Courier New"; mso-ansi-language:EN-US">  Node_Dispose(Root);

<span Courier New"; mso-ansi-language:EN-US">}

<span Courier New"; mso-ansi-language:EN-US">//-------------------------------------------------------------

<span Courier New"; mso-ansi-language:EN-US">void inputKey(string S, TInfo& Key)

<span Courier New"; mso-ansi-language:EN-US">{

<span Courier New"; mso-ansi-language:EN-US">  cout << S << endl;

<span Courier New"; mso-ansi-language:EN-US">  cin >> Key;

<span Courier New"; mso-ansi-language:EN-US">}

<span Courier New"; mso-ansi-language:EN-US">

<span Courier New";mso-ansi-language:EN-US">TTree

<span Courier New";mso-ansi-language: EN-US"> *Tree = new TTree;

<span Courier New";mso-ansi-language:EN-US">int

<span Courier New";mso-ansi-language: EN-US"> N;

<span Courier New";mso-ansi-language:EN-US">TInfo

<span Courier New";mso-ansi-language: EN-US"> Key;

<span Courier New";mso-ansi-language:EN-US">int

<span Courier New";mso-ansi-language: EN-US"> main(int argc, const char* argv[])

<span Courier New"">{

<span Courier New"">  do {

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

<span Courier New"">    cout << «2-Удалить элемент» << endl;

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

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

<span Courier New"">   

<span Courier New";mso-ansi-language: EN-US">cout<span Courier New";mso-ansi-language:EN-US"> << «5-<span Courier New»">Выход<span Courier New";mso-ansi-language: EN-US">" << endl;

<span Courier New"; mso-ansi-language:EN-US">    cin >> N;

<span Courier New"; mso-ansi-language:EN-US">                 {

<span Courier New"; mso-ansi-language:EN-US">      switch (N) {

<span Courier New"; mso-ansi-language:EN-US">        case 1: {

<span Courier New"; mso-ansi-language:EN-US">             inputKey("

<span Courier New"">Введите<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">значение<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">добавляемого<span Courier New";mso-ansi-language:EN-US"> <span Courier New"">элемента<span Courier New";mso-ansi-language: EN-US">", Key);

<span Courier New"; mso-ansi-language:EN-US">             Tree->Add(Key);

<span Courier New"; mso-ansi-language:EN-US">           }

<span Courier New"; mso-ansi-language:EN-US">           break;

<span Courier New"; mso-ansi-language:EN-US">        case 2: {

<span Courier New"; mso-ansi-language:EN-US">            

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

<span Courier New"">            

<span Courier New";mso-ansi-language:EN-US">Tree-><st1:State w:st=«on»><st1:place w:st=«on»>Del</st1:place></st1:State>(Key);

<span Courier New"; mso-ansi-language:EN-US">           }

<span Courier New"; mso-ansi-language:EN-US">           break;

<span Courier New"; mso-ansi-language:EN-US">        case 3: Tree->View(); break;

<span Courier New"; mso-ansi-language:EN-US">       

<span Courier New"">case<span Courier New""> 4: {

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

<span Courier New"">            

<span Courier New";mso-ansi-language:EN-US">Tree->Exist(Key);

<span Courier New"; mso-ansi-language:EN-US">           }

<
еще рефераты
Еще работы по программированию, базе данных