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