14.3 Двоичные деревья

Двоичные деревья являются удобным инструментом организации эффективного поиска. В отличие от двоичного поиска, когда адрес очередного элемента определяется на основе деление отрезка пополам, адрес следующего элемента поиска задан явно. Поиск начинается с корневого элемента, который задан явно. Производится сравнение значений ключей, если совпали, то поиск завершен. Если значение ключа искомого меньше, то происходит переход по левому адресу, в противном случае происходит переход по правому адресу. Процесс поиска продолжается, пока не найден будет искомый элемент или не достигнем листа двоичного дерева.

Двоичное дерево можно представить древовидным списком, однако, зная, что узел двоичного дерева может содержать не более двух сыновей, то лучше узел описать тройкой: <адрес левого сына, адрес правого сына, значение ключа>

Тогда можно записать следующие определения типа:

1. Описание типа на любой объект
   
         typedef void* pObj; //указатель на объект
   
   
2. Описание типа узла двоичного дерева
         typedef struct NodeTag {
               struct NodeTag *left; //адрес левого сына
               struct NodeTag *right; //адрес правого сына
               pObj data; //адрес блока данных, в том числе и ключа
         } Node;
3. Описание типа двоичного дерева
         typedef struct BinaryTreeTag {
               Node *root; //адрес корня дерева
               int size; //количество узлов в дереве
         } BinaryTree;