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

Бинарное (двоичное) дерево - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значения данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значения данного узла.

Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом, и, следовательно, каждый его узел в свою очередь является корнем дерева. Узел дерева, не имеющий потомков, называется листом.

Схематичное изображение бинарного дерева представлено на рисунке 1:

Рисунок 1 - Схематичное изображение бинарного дерева

Бинарное дерево может выродиться в список, представленный на рисунке 2:

Рисунок 2 - Схематичное изображение списка

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

Строго двоичным деревом называется дерево, у которого каждая внутренняя вершина имеет непустые левое и правое поддеревья. Это означает, что в строго двоичном дереве нет вершин, у которых есть только одно поддерево.

Полным двоичным деревом называется дерево, у которого все листья находятся на одном уровне и каждая внутренняя вершина имеет непустые левое и правое поддеревья, [1].