Алгоритм добавления нового элемента в достаточно прост.
Начните с корневого узла. По очереди сравните значения всех узлов со значением
нового элемента. Если новое значение меньше или равно значению в рассматри-
ваемом узле, продолжайте движение вниз по левой ветви. Если новое значение
больше значения узла, переходите вниз по правой ветви. Когда вы достигнете кон-
ца дерева, вставьте элемент в эту позицию.
Чтобы включить значение 8 в дерево, изображенное на рис. 6.15, начните с кор-
ня, который имеет значение 4. Поскольку 8 больше 4, переходите по правой ветви
к следующему узлу - 9. Поскольку 8 меньше 9, продолжайте двигаться налево -
к узду 7. Поскольку 8 больше 7, программа пытается идти направо, но этот узел не
имеет правого дочернего. Поэтому новый элемент вставляется именно в этой точ-
ке, и образуется дерево, изображенное на рис. 6.16.
Рис. 6.15. Упорядоченный список: 1, 2, 4, 6,7,9
Рис. 6.16. Упорядоченный список: 1, 2, 4, 6, 7,8,9
Следующий код добавляет новое значение под узлом в упорядоченном дере-
ве. Программа начинает вставлять элемент с корневого узла, используя функцию
Insertltem(Root,new_value).
procedure Insertltem(var node : PSortNode; new_value : Integer);
begin
if (node=nil) then
begin
// Достигли листа.
// Вставка элемента в этом месте.
GetMem(node,SizeOf(TSortNode));
node^.Value := new_value;
end else if (new_value<=nodeл.Value) then
begin
// Левая ветвь.
InsertItem(node^.LeftChild,new_value);
end else begin
// Правая ветвь.
InsertItem(node^.RightChild,new_value);
end;
end;
Когда процедура достигает конца дерева, происходит нечто довольно неожи-
данное. Параметр node этой процедуры объявлен с ключевым словом var. Это
означает, что процедура работает с той же копией переменной node, которую ис-
пользует вызывающая процедура. Если процедура изменяет значение параметра
node, то значение изменяется и для вызывающей процедуры.
Когда процедура Insertltem рекурсивно вызывает саму себя, она передает
указатель на дочерний узел. Например, в следующих операторах процедура пере-
дает указатель на правый дочерний узел в качестве параметра. Если вызванная
процедура изменяет значение параметра node, в вызывающей процедуре указа-
тель на потомка также автоматически обновляется, что добавляет созданный но-
вый узел к дереву.
InsertItem(node^.RightChild,new_value);
|
Главная
Каталог файлов
