Структуры данных бинарное упорядоченное несбалансированное дерево — страница 3

  • Просмотров 1925
  • Скачиваний 380
  • Размер файла 16
    Кб

R: PItem); //процедура удаляет узел имеющий двух потомков, заменяя его на самый правый //узел левого поддерева begin if R^.Right <> nil then //обойти дерево справа Del(R^.Right) else begin //дошли до самого правого узла //заменить этим узлом удаляемый 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 { //правый узел - лист и надо