Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 91 стр.

            .       Практикум по курсу «Алгоритмизация и программирование». Часть 2
    Подвидом бинарных деревьев является дерево сортировки. Это такое де-
рево, в котором слева от любой вершины находятся вершины с элементами,
меньшими, чем в данной вершине, а справа – с большими или равными эле-
ментами. Пример дерева сортировки представлен на рис. 6.1.

    Далее приводится описание процесса решения некоторых задач с при-
менением пользовательских функций.
    Задача 1. Дано дерево сортировки. Написать функцию добавления в де-
рево нового элемента.
    При добавлении нового узла в дерево используются следующие правила:
     1) если дерево было пустым, то значение помещается в корень дерева;
     2) в противном случае просматриваются узлы дерева, начиная с корня, и
осуществляется переход к левому поддереву, если новый элемент имеет мень-
шее значение, чем значение в текущей вершине. В противном случае – пере-
ход к правому поддереву.
    Как только достигается вершина, от которой нет возможности передви-
гаться в нужном направлении, т.е. указатель на соответствующее поддерево
равен NULL, создаем новый узел и присоединяем его к этой вершине в соот-
ветствии с определением дерева сортировки.
    Рассмотрим вставку новых элементов в дерево сортировки, представлен-
ного на рис. 6.1. Например, сначала добавим элемент «12», затем «10».
    Просматриваем узлы дерева, начиная с корня. Поскольку 17 больше 12,
то переходим к левому потомку – узлу «6». 6 меньше 12, следовательно, пере-
ходим на правый потомок узла «6» – узел «9». 9 меньше 12, поэтому следует
перейти к правому потомку, которого не существует. Таким образом, опреде-
лилось место вставки нового элемента – справа от узла «9».




                          Рис. 6.4. Вставка значения 12.


                                      91