Программирование на языке высокого уровня. Марапулец Ю.В. - 72 стр.

      X *end = first;
      for (int i = 1; i<8; i++)
               In(&end, i);
      while (first)
               printf("%d ",Out(&first));
      return 0;
}

     2.9.5. Бинарные деревья

     Бинарное дерево - это иерархическая динамическая структура данных, состоящая
из узлов (вершин), каждый из которых содержит, кроме данных, не более двух ссылок
на другие бинарные деревья. На каждый узел имеется только одна ссылка. Начальный
узел называется корнем дерева. Узел, не имеющий поддеревьев, называется листом.
Исходящие узлы называются предками, восходящие - потомками. Высота дерева оп-
ределяется количеством уровней, на которых располагаются его узлы.
     Есть много типов деревьев, которые отражают различные сложные структуры, на-
пример деревья синтаксического разбора (parse trees), хранящие синтаксис предложе-
ния или программы; либо генеалогические деревья, описывающие родственные связи.
Если дерево организовано таким образом, что для каждого узла все ключи его левого
поддерева меньше ключа этого узла, а все ключи его правого поддерева - больше, оно
называется деревом поиска. Одинаковые ключи не допускаются. В дереве поиска можно
найти элемент по ключу, двигаясь от корня и переходя на левое или правое поддерево в
зависимости от значения ключа в каждом узле. Такой поиск гораздо эффективнее поиска
по списку, поскольку время поиска определяется высотой дерева, а она пропорциональ-
на двоичному логарифму количества узлов. На рис.2.6 [8] приведен пример бинарного
дерева поиска.




                                    Рис.2.6. Бинарное дерево



                                              72