Двоичное дерево - это тип структуры данных, в которой каждый узел имеет не более двух дочерних элементов (левый дочерний элемент и правый дочерний элемент). Двоичные деревья используются для реализации двоичных деревьев поиска и двоичных куч, а также для эффективного поиска и сортировки. Бинарное дерево - это частный случай K-арного дерева, где k равно 2. Общие операции для бинарных деревьев включают вставку, удаление и обход. Сложность выполнения этих операций зависит от того, сбалансировано ли дерево, а также от того, являются ли узлы листовыми узлами или узлами ветвления. Для сбалансированных деревьев глубина левого и правого поддеревьев каждого узла отличается на 1 или меньше. Это позволяет получить предсказуемую глубину, также известную как высота.. Это мера узла от корня до листа, где корень равен 0, а следующие узлы - (1,2..n). Это может быть выражено целой частью log 2 (n), где n - количество узлов в дереве.
g s 9
/ \ / \ / \
b m f u 5 13
/ \ / \ / \
c d t y 11 15
Операции, выполняемые с деревьями, требуют поиска одним из двух основных способов: поиск в глубину и поиск в ширину. Поиск в глубину (DFS) - это алгоритм обхода или поиска структур данных в виде дерева или графа. Каждый начинает с корня и исследует, насколько это возможно, каждую ветвь, прежде чем вернуться. Существует три типа обхода поиска в глубину: посещение по предварительному заказу , влево, вправо, влево по порядку , посещение, вправо, влево по порядку , вправо, посещение. Поиск в ширину (BFS) - это алгоритм обхода или поиска структур дерева или графа. В порядке уровней, когда мы посещаем каждый узел на уровне, прежде чем перейти на более низкий уровень.
Ниже представлена реализация двоичного дерева с возможностью вставки и печати. Это дерево упорядочено, но не сбалансировано. Этот пример сохраняет порядок во время вставки.
Измените процедуру печати на предварительный заказ поиска в глубину .