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

Листинг 4.3. Процедуры обхода дерева 
void PreOrder(TNode Tree) // 
Сверху-вниз 
{ 
if (Tree != null) 
{ 
Proc(Tree); // 
обработка узла 
PreOrder(Tree.left); 
PreOrder(Tree.right); 
} 
} 
void InOrder(TNode Tree); //
Слева-направо 
{ 
if (Tree != null) 
{ 
InOrder(Tree.left); 
Proc(Tree); // 
обработка узла 
InOrder(Tree.right); 
} 
} 
10 / 23

---

80 
void PostOrder(TNode Tree); // 
Снизу-вверх 
{ 
if (Tree != null) 
{ 
PostOrder(Tree^.left); 
PostOrder(Tree^.right); 
Proc(Tree^); // 
обработка узла 
} 
} 
Примечание 
Следует обратить внимание, что ссылка Tree передается как параметр-значение. Это 
отражает тот факт, что здесь существенна сама ссылка (указатель) на рассматриваемое 
поддерево, а не переменная, значение которой есть эта ссылка и которая могла бы из-
менить значение, если бы Tree передавалась как параметр-переменная. 
Пример процедуры, осуществляющий обход дерева, приведен ниже, в 
листинге 4.4. Обход дерева осуществляется с целью найти ближайший к ука-
зателю мышки узел нарисованного на канве дерева. 
4.2.1. У
ПОРЯДОЧЕННЫЕ ДЕРЕВЬЯ
 
Упорядоченным называется дерево, у которого для каждого узла Node 
значение левого дочернего узла меньше, чем значение в Node, а значение 
правого дочернего узла больше значения в Node. Если в дереве могут содер-
жаться одинаковые значения, то программист сам должен определить, влево 
или вправо помещать значение, равное значению в родительском узле, то 
есть соответствующее строгое неравенство заменить на нестрогое. 
Построение упорядоченного дерева начинается с корня. Первое из вхо-
дящих значений и будет значением корня. Для каждого следующего значения 
производится, начиная с корня, сравнение со значением в очередном узле. 
Если это значение не превосходит значения в узле, то переходим в левое 
поддерево, иначе переходим в правое. Эти переходы и сравнения продолжа-
ются до тех пор, пока не придем к ссылке, которая равна null. Тогда созда-
ется новый узел. Этот алгоритм, реализованный в виде рекурсивной проце-
дуры, приведен в листинге 4.4.