Узлы, графы и деревья

В этой главе мы будем изучать деревья и графы, которые, вероятно, являются самым распространенным типом вопросов на собеседованиях (хеш-карты не являются "типом" вопросов, а "массив" или "строка" слишком широки).
Деревья и графы — это абстрактные структуры данных, которые встречаются повсюду как в физическом мире, так и в мире программного обеспечения.
Большое количество задач на собеседованиях включает деревья или графы в качестве ввода, и вся задача сосредоточена на них. Поэтому крайне важно, чтобы любой, кто идет на собеседование по программированию, хорошо разбирался в них.

Что такое узел?

Начнем с того, что повторим, что такое узел. Мы уже рассматривали узлы в главе о связанных списках - помните, что узел является абстрактным типом данных, содержащим две вещи.
Во-первых, узел хранит данные. Эти данные могут быть любыми - целое число, логическое значение, хеш-карта, ваши собственные объекты или все вышеперечисленное.
Во-вторых, узел хранит указатели на другие узлы.

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

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

Узлы графа также называются вершинами, а указатели, которые их соединяют, называются ребрами. В графических представлениях узлы/вершины обычно изображаются кругами, а ребра - линиями/стрелками, соединяющими круги (мы видели это в главе о связанных списках).

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

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

Помните, что начало связанного списка называлось головой. Начало бинарного дерева называется корнем.

В связанном списке указатель узла указывал на следующий узел. В дереве узел имеет указатели на своих детей. Если узел A указывает на узел B, то B является ребенком A, а A является родителем B. Корень - это единственный узел, у которого нет родителя. Обратите внимание, что в дереве узел не может иметь более одного родителя.

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

В итоге, бинарное дерево - это собрание узлов. Каждый узел имеет от 0 до 2 детей, и каждый узел, кроме корня, имеет ровно одного родителя.

Примеры использования деревьев в реальной жизни

Деревья (не только бинарные деревья) реализованы вокруг нас в повседневной жизни. Некоторые примеры:

• Файловые системы
• Поток комментариев в приложении, таком как Reddit или Twitter
• Организационная структура компании

В каждом из этих примеров соответствующие корневые узлы и их потомки будут следующими:

• Корневой каталог и подкаталоги/файлы
• Оригинальный пост/твит и комментарии и ответы
• Генеральный директор и прямые подчиненные

Терминология деревьев

Существует некоторая специфическая для деревьев терминология, которую необходимо изучить.

• Корневой узел - это узел, находящийся "наверху" дерева. Каждый узел в дереве доступен, начиная с корневого узла. В большинстве задач на деревья корень дерева будет дан в качестве входных данных, так же как в связанных списках голова списка давалась в качестве входных данных.

• Если у вас есть узел A с ребром к узлу B, то есть A -> B, мы называем A родителем узла B, а узел B - ребенком узла A.

• Если у узла нет детей, он называется листовым узлом. Листовые узлы являются листьями дерева.

  

• Глубина узла - это расстояние от корневого узла. Корень имеет глубину 0. Каждый ребенок имеет глубину, равную глубине родителя + 1, так что дети корня имеют глубину 1, их дети имеют глубину 2 и так далее.

• Наконец, возможно, самое важное для понимания: поддерево дерева - это узел и все его потомки. Деревья являются рекурсивными структурами - вы можете рассматривать поддерево как самостоятельное дерево с выбранным узлом в качестве корня.

Реализация бинарных деревьев

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

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

В задачах на бинарные деревья вам будет предоставлена ссылка на корень бинарного дерева в качестве входных данных. Вы можете получить доступ к левому поддереву корня с помощью root.left и к правому поддереву корня с помощью root.right. Как и в связанных списках, каждый узел также будет содержать значение val в качестве данных. В связанном списке хвост (последний узел) имеет указатель next, равный null. В бинарном дереве, если у узла нет левого ребенка, то node.left будет null, и аналогично с правым ребенком. Помните, что если оба ребенка равны null, то узел является листом.