Рассмотрим алгоритмы поиска по дереву с включением и исключением на языке программирования С++.
Для простоты будем рассматривать бинарное упорядоченной дерево, в полях элементов которого ключи – вещественные числа, а поля записей отсутствуют. Описание самого элемента, функции создания и обхода подобного дерева подробно описаны в лабораторной работе № 3, поэтому здесь мы на них останавливаться не будем. Функция поиска со вставкой при уже созданном дереве будет иметь следующий вид:
void Vstavka(double key) //функция, вставляющая элемент в дерево
{Q=NULL;
P=tree;
while(P)
{ Q=P;
if(key==P->k)
{cout<<"\n В дереве уже есть такой элемент, он найден, вставлять не надо\n";
return;
/*если такой элемент в дереве уже есть, то функция завершает свою работу*/
}
if(key<P->k) P=P->left;
else P=P->right;
};
V=new element;
V->k=key;
V->left=V->right=NULL;
if(key<Q->k) Q->left=V;
else Q->right=V;
}
Функция поиска с удалением при уже созданном дереве будет иметь следующий вид:
void Poisk_Udalenie (double key) //функция поиска с удалением
{Q=NULL;
P=tree;
{ while(P&&P->k!=key)
{ Q=P;
if(key<P->k) P=P->left;
else P=P->right;
};
if(!P) { cout<<"Ключ не найден!"; return;};
if(P->left==NULL) V=P->right;
else
{if(P->right==NULL) V=P->left;
else
{ T=P;
V=P->right;
S=V->left;
while(S)
{ T=V;
V=S;
S=V->left;
};
if(T!=P) { T->left=V->right;
V->right=P->right;
}
V->left=P->left;
}
}
if(Q==NULL) tree=V;
else
if(P==Q->left) Q->left=V;
else Q->right=V;
delete P;
}
}