Степень дерева равна максимальной степени составляющих его узлов. Дерево, представленное на следующей диаграмме, имеет степень 2
Поддерево (Subtree)
Поддерево — это часть дерева с выбранным узлом в качестве корневого‚ а все его дочерние элементы — это узлы дерева. На диаграмме поддерево от узла E состоит из узла E в качестве корневого и узлов G и H в качестве дочерних
Концевой узел (Leaf node)
Узел в дереве без дочерних элементов называется концевым. Например, на рис. 2.8 D, G, H и F — это четыре концевых узла
Внутренний узел (Internal node)
Любой узел, который не является ни корневым, ни концевым‚ называется внутренним. У внутреннего узла имеются по крайней мере один родительский и один дочерний узлы
Терминология
Рассмотрим некоторые термины, связанные с древовидной структурой данных (табл. 2.7).
Таблица 2.7
Корневой узел (Root node)
Узел без родителя называется корневым узлом. Например, на следующей диаграмме (рис. 2.8) корневым узлом служит A. В алгоритмах корневой узел, как правило, содержит наиболее важное значение во всей древовидной структуре
Уровень узла (Level of a node)
Расстояние от корневого узла называется уровнем узла. На следующей диаграмме уровень узлов D, E и F равен двум
Узлы-братья (Siblings nodes)
Два узла в дереве называются братьями, если они расположены на одном уровне. Например, если мы взглянем на диаграмму‚ то увидим‚ что узлы B и C являются братьями
Дочерний и родительский узлы (Child and parent node)
Узел F является дочерним по отношению к узлу C, если они напрямую связаны и уровень узла C меньше уровня узла F. И наоборот, узел C является родительским для узла F. Узлы C и F на следующей диаграмме демонстрируют отношения родительского и дочернего узлов
Степень узла (Degree of a node)
Степень узла — это количество его дочерних элементов. Например, на рис. 2.8 узел B имеет степень 2
Стек
Стек — это линейная структура данных для хранения одномерного списка. Элементы в стеке могут обрабатываться по принципу LIFO (Last-In, First-Out: «последним пришел — первым ушел») либо по принципу FILO (First-In, Last-Out: «первым пришел — последним ушел». Порядок добавления и удаления элементов определяет характер стека. Новые элементы могут добавляться и удаляться только с одного конца списка.
Ниже приведены операции со стеками:
• isEmpty. Возвращает true, если стек пуст;
• push. Добавляет новый элемент;
• pop. Возвращает элемент, добавленный последним, и удаляет его.
На рис. 2.4 показано, как операции push() и pop() можно использовать для добавления и удаления данных из стека.