Int CmpKeys; // результат сравнения ключей

x=new NODE;

x->Record=NewRecord;

Cur=Root;

// поиск места вставки

for(;;){

CmpKeys=Cmp(NewRecord,Cur->Record);

switch(CmpKeys){

case –1:

WhatSon=LEFT;

Next=Cur->Left;

break;

case 0:

case 1:

WhatSon=RIGHT;

Next=Cur->Right;

break;

}

if(Next==NULL){

break;

}

Cur=Next;

}

if(WhatSon==LEFT){

Cur->Left=x;

} else {

Cur->Right=x;

}

return x;

Рис 41. Результат вставки ключей в бинарное дерево

На рис. 41 изображен результат работы алгоритма.

Операция удаления узла.Сначала заметим, что обход бинарного дерева в обратном порядке даёт сортированную последо­ва­тель­ность. Все замечательные свойства древовидной таблицы связаны с этим обстоятельством. При удалении узла необходимо сохранить порядок следования узлов в обратном порядке. Легко удалить лист или узел, у которого пуста правая или левая связь. В общем случае одно из возможных решений таково: удалить следующий в обратном порядке узел, левая связь которого пуста, а затем вернуть его на место узла, который действительно требуется удалить. Ниже приведен текст функции, удаляющей узел, содержащий запись с целым ключом Key. Здесь предполагается, что дерево имеет голову, и, что само дерево является левым поддеревом головы. Голова содержит максимально возможное значение ключа. В случае успеха функция возвращает true.

struct NODE {

int Info;

NODE *Left;

NODE *Right;