Рассмотрим алгоритм организации поиска по некоторому бинарному дереву со вставкой новых записей в такое дерево, если поиск неудачен.
{часть программы}
class item
{
public:
char name;
int k;
item * left; // указатели
item *right;
item(char, item *, item *, int ); // конструктор
~item(); // деструктор
};
class tree
{
public:
tree * g; // указатель на начало прохода дерева
};
…
void main()
{
tree *p= new tree;; // создается объект - дерево
int search=0; // 1 — признак нахождения ключа
item *l,r; // указатели левого и правого полей
item *q,p;
…
q= NULL; // q — указатель на отца, если он существует
p=g; // g — указатель на начало прохождения дерева
while( p!=NULL)
{
if (key==p->k) search=1;
else
{
q:=p;
if( key<p->k ) p=p->left;
else p=p->right;
}
}
if (search==1)
{
cout<<”ключ найден\n”;
return;
}
else
{
сout<<”ключ не найден\n”;
// вставка информации с ключом
item *v=new item(rec,l,r,key);
v->name=rec; // rec - запись
v->k=key;
if (q==nil) // дерево было пусто изначально
*tree==v;
else // дерево не было пусто
{
if( key<q->k)
{
v->left=q->left;
q->left=v;
}
else
{
v->right=q->right;
q->right=v;
}
}
}
…
Отметим, что после того, как будет вставлена некоторая новая запись, данное дерево сохранит то свойство, что при прохождении его в симметричном порядке получится отсортированный массив.
