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

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова .
При вставке узла со значением 10, аналогично переходим по узлам «17»,
«6», «9», «12», и поскольку 10 меньше 12, то связываем узел «10» с узлом
«12» слева.
Рис. 6.5. Вставка значения 10.
Для решения задачи рассмотрим два варианта функции – рекурсивный и
нерекурсивный. Разберем сначала рекурсивный вариант. Поскольку каждое
поддерево по определению также является деревом, то каждый узел дерева
можно обрабатывать как корень.
Параметрами функции будут – адрес корня поддерева (переменная root)
и добавляемое значение (key).
Если дерево пусто, формируем корень дерева. Для этого адрес вновь со-
зданного элемента сохраняется в переменной root, заполняется информаци-
онное поле, и ссылки на левое и правое поддеревья обнуляются. На этом
функция завершает свою работу.
Если дерево непусто, вызываем эту же функцию для левого (со значения-
ми аргументов root->left и key) или для правого поддеревьев (root-
>right и key), в зависимости от добавляемого значения.
// определение рекурсивной функции
// добавления в дерево нового элемента
void AddTree(Tree*& root, int key)
{
// если дерево пусто, формируем корень дерева
if(root==NULL)
{
Tree* help=new Tree;
92
А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                   .
    При вставке узла со значением 10, аналогично переходим по узлам «17»,
«6», «9», «12», и поскольку 10 меньше 12, то связываем узел «10» с узлом
«12» слева.




                               Рис. 6.5. Вставка значения 10.


    Для решения задачи рассмотрим два варианта функции – рекурсивный и
нерекурсивный. Разберем сначала рекурсивный вариант. Поскольку каждое
поддерево по определению также является деревом, то каждый узел дерева
можно обрабатывать как корень.
    Параметрами функции будут – адрес корня поддерева (переменная root)
и добавляемое значение (key).
    Если дерево пусто, формируем корень дерева. Для этого адрес вновь со-
зданного элемента сохраняется в переменной root, заполняется информаци-
онное поле, и ссылки на левое и правое поддеревья обнуляются. На этом
функция завершает свою работу.
    Если дерево непусто, вызываем эту же функцию для левого (со значения-
ми аргументов root->left и key) или для правого поддеревьев (root-
>right и key), в зависимости от добавляемого значения.

    // определение рекурсивной функции
    // добавления в дерево нового элемента
    void AddTree(Tree*& root, int key)
    {
          // если дерево пусто, формируем корень дерева
          if(root==NULL)
          {
               Tree* help=new Tree;

                                            92

Страницы