На этом шаге мы рассмотрим алгоритм добавления вершины в дерево.
Перед добавлением вершины в дерево обращаемся к функции Poisk (k,Tree,&r);. Если значение глобальной переменной B, которое вернула функция Poisk, равен FALSE (в дереве нет ключа, равного вновь поступающему), то вершина, после которой будет осуществляться добавление, является листом. Указатель на этот лист хранится в переменной r.
В heap-области резервируем место для динамического объекта:
s = new(node); (*s).Key = Элем; (*s).Count = 1;
(*s).Left = (*s).Right = NULL;
и "подвешиваем" вершину:
*Tree = s;.
Иначе, если вершина, после которой будем прикреплять новую, не является листом дерева, то перед "подвешиванием" определяем, в какое поддерево относительно этой вершины будет включена новая:
if (k<(*r).Key) (*r).Left = s;
else (*r).Right = s;
Приведем текст функции добавления:
void Addition (node **Tree, int k) // Добавление вершины k в бинарное дерево. // *Tree - указатель на вершину дерева. // B - глобальная булевская переменная: // TRUE, если вершина с ключом k в дереве найдена, // FALSE, в противном случае. { node *r, *s; Poisk (k,Tree,&r); if (!B) { s = new(node); (*s).Key = k; (*s).Count = 1; (*s).Left = (*s).Right = NULL; if (*Tree==NULL) *Tree = s; else if (k<(*r).Key) (*r).Left = s; else (*r).Right = s; } else (*r).Count += 1; }
На следующем шаге мы рассмотрим удаление вершины из дерева.
