Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 4.10. Поиск по дереву с включением 
public void Insert(ref Node t, int data,
int x, int y)
// 
вставка 
{ 
if (t == null) 
t = new Node(null, null, data, x, y); 
else 
if (data < Convert.ToInt32(t.data)) 
Insert(ref t.left, data, t.x-step,
t.y+ dh * step); 
else 
if (data > Convert.ToInt32(t.data)) 
Insert(ref t.right, data, t.x + step,
t.y + dh * step); 
else 
t.count++; 
} 
Как следует из листинга 4.10, поиск осуществляется перемещением по 
узлам дерева с выбором на каждом этапе дальнейшего направления движения 
в зависимости от соотношения между искомым и хранящимся в текущем уз-
ле значением. После завершения процесса построения дерева можно выпол-
нить его обход по способу «сверху-вниз» с формированием упорядоченной 
последовательности значений.
В листинге 4.11 представлен алгоритм обхода упорядоченного дерева с 
формированием последовательности значений, упорядоченной по убыванию. 
Листинг 4.11. Формирование отсортированной последовательности 
public string SetStrSort(Node p) 
{ 
string s=""; 
18 / 23

---

88 
if (p == null) 
return s; 
if (p.right != null) 
s += SetStrSort(p.right); 
s += Convert.ToString(p.data) + "\r\n"; 
if (p.left != null) 
s += SetStrSort(p.left); 
return s; 
} 
Результат выполнения этого алгоритма представлен на рисунке 4.3. 
Рис. 4.3. Вывод отсортированной последовательности 
4.2.3. У
ДАЛЕНИЕ ИЗ УПОРЯДОЧЕННОГО ДЕРЕВА
 
Задача удаления узла из упорядоченного дерева является обратной за-
даче добавления узла. После операции удаления дерево должно остаться упо-
рядоченным. Операция удаления узла из упорядоченного дерева в общем 
случае является более сложной, чем добавление узла. Различные ситуации, 
возникающие при удалении узла, иллюстрируются рисунком 4.4.
Удаление узла легко выполняется, если этот узел является листом де-
рева (узел 13 на рис. 4.4). Лист дерева удаляется без перестройки дерева. Ес-
ли удаляемый узел имеет только одного сына, то удаляемый узел заменяется 
узлом-сыном (узел 15 на рис. 4.4). Трудность заключается в удалении узла с 
19 / 23

---

89 
двумя сыновьями, поскольку невозможно указать одной ссылкой два направ-
ления (узел 5 на рис. 4.4). В этом случае удаляемый узел нужно заменить ли-
бо на самый правый элемент его левого поддерева, либо на самый левый эле-
мент его правого поддерева. Причина такого выбора заключается в том, что 
указанные узлы не могут иметь более одного потомка, что позволяет «при-
крепить» к ним «осиротевшее» поддерево.
Так, при замене удаляемого узла на самый правый элемент левого под-
дерева (узел 10 на рис. 4.4) мы сможем «прикрепить» к нему правое поддере-
во удаленного узла, а его собственное левое поддерево передать в качестве 
правого поддерева его узлу-родителю. При альтернативном выборе ситуация 
будет симметричной. 
Рис. 4.4. Удаление из упорядоченного дерева 
Алгоритм удаления узла с ключом x из упорядоченного дерева реали-
зован процедурой Delete(), приведенной в листинге 4.12.
Функция различает три случая: 
− в дереве нет узла с ключом x; 
− узел с ключом x имеет не более одного сына; 
− узел с ключом x имеет двух сыновей.