Дерево — это наша первая иерархическая структура. Каждое дерево имеет один корневой узел, и разные деревья отличаются от него. Их можно заказать или нет. Узлы называются листьями, и здесь хорошо работает аналогия родитель-потомок или родословная. Листья без потомков называются (). Узлы соединены ребрами.
Двоичные деревья поиска — у каждого узла может быть только два потомка. Они упорядочены, левый узел меньше родительского, правый узел больше родительского. Это имеет отличную временную сложность, поскольку каждый шаг, который вы делаете, удаляет половину возможных оставшихся вариантов.
глубина дерева: отсчет от корневого узла до указателя узла, заканчивающегося нулем.
высота узла: расположение от позиции узла до корня. at root равно -1, а обратный отсчет до родителей будет равен 1.
Отличное видео Сначала в ширину и в глубину.
