|
program
PTree;
{$APPTYPE
CONSOLE}
type
TInfo = Byte;
PItem = ^Item;
Item = record
Key: TInfo;
Left, Right: PItem;
end;
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);
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 //ищется в правом поддереве
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;
};
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 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;
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;
}
|