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

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

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

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); //искать в правом поддереве

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;

}