В этой статье мы кратко рассмотрим деревья и то, что вам нужно знать о них, прежде чем внедрять и использовать их.

Что такое дерево?

Сначала давайте посмотрим, что такое дерево на самом деле.

(изображение основного дерева)

Деревья представляют собой нелинейную структуру данных, в которой данные хранятся непоследовательно. Это означает, что данные на самом деле не следуют очевидному порядку, например числовому, к которому мы привыкли при использовании массивов, связанных списков и других линейных структур данных.

Из-за этого мы считаем дерево неупорядоченной структурой данных, но это верно только в его основной форме. Только когда мы начинаем думать об обходе, манипулировании и использовании деревьев для решения задачи, мы понимаем, что упорядочение данных в дереве очень важно для большинства реализаций. Мы коснемся этого в следующей статье о других типах деревьев, таких как бинарное дерево.

Из чего состоит дерево?

(Изображение дерева с определенными узлами)

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

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

  • Значение: заданное (необязательное) значение, которое было сохранено в дереве.
  • Указатели. Ссылки, указывающие на несколько узлов.

Теперь, когда мы знаем, что такое узлы, мы можем взглянуть на некоторые жаргонные термины, которые вам понадобятся, когда вы будете говорить о деревьях:

  • Корневой: начальный узел, к которому нет ссылок или ссылок.
  • Link/Edge: ссылка родительского узла, которая связана с дочерним узлом.
  • Дочерний элемент: любой узел, на который указывает родитель.
  • Родительский: любой узел, который ссылается на другой узел как на дочерний.
  • Родственный узел: любая группа узлов, являющихся дочерними элементами одного и того же узла.
  • Внутренний: любой узел, имеющий дочерний узел, любой родительский узел
  • Листок: любой узел, не имеющий дочернего узла.

С помощью этих терминов мы можем определить некоторые другие свойства дерева.

Некоторые свойства дерева

(картинка, объясняющая глубину и высоту)

Когда речь идет о деревьях, часто используются глубина и высота дерева, поэтому давайте определим их.

  • Глубина: количество ссылок для достижения заданного узла от корневого узла.
  • Высота: максимальное количество ссылок на узлы самый дальний лист.

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

Это свойство становится действительно интересным при реализации дерева и, в частности, при обходе деревьев, о чем будет рассказано в следующей статье (возможно).

Примеры

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

Источники