Ключевые термины
Бинарное (двоичное) дерево – это дерево, в котором каждая вершина имеет не более двух потомков. Вершина (узел) дерева – это каждый элемент дерева. Ветви дерева – это направленные дуги, которыми соединены вершины дерева. Высота (глубина) дерева – это количество уровней, на которых располагаются его вершины. Дерево – это структура данных, представляющая собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов. Корень дерева – это начальный узел дерева, ему соответствует нулевой уровень. Листья дерева – это вершины, в которые входит одна ветвь и не выходит ни одной ветви. Неполное бинарное дерево – это дерево, уровни которого заполнены не полностью. Нестрогое бинарное дерево – это дерево, у которого вершины имеют степень ноль (у листьев), один или два (у узлов). Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается только один раз. Поддерево – это часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева. Полное бинарное дерево – это дерево, которое содержит только полностью заполненные уровни. Потомки – это все вершины, в которые входят ветви, исходящие из одной общей вершины. Почти сбалансированное дерево – это дерево, у которого длины всевозможных путей от корня к внешним вершинам отличаются не более, чем на единицу. Предок – это вершина, из которой исходят ветви к вершинам следующего уровня. Сбалансированное дерево – это дерево, у которого длины всех путей от корня к внешним вершинам равны между собой. Степень вершины – это количество дуг, которое выходит из этой вершины. Степень дерева – это максимальная степень вершин, входящих в дерево. Строгое бинарное дерево – это дерево, у которого вершины имеют степень ноль (у листьев) или два (у узлов). Упорядоченное дерево – это дерево, у которого ветви, исходящие из каждой вершины, упорядочены по определенному критерию. Уровень вершины – это количество дуг от корня дерева до вершины.
|