Терминология

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

Узел. В древовидных структурах данных узел является контейнером для наших значений.

Edge- Ребра - это линии, которые соединяют узлы и образуют деревья.

Предок — это другое название родительского узла, узла, который «рождает другой узел».

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

Родительский узел. Как объяснялось выше, родительский узел порождает дочерние узлы.

Дочерний узел — узел, рожденный от родительского узла.

Листовой узел — узел, у которого нет дочерних узлов.

Корневой узел — это основной узел, с которого начинается дерево.

Введение

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

Следующее математическое выражение может быть представлено в виде древовидной структуры данных; 8*а+б.

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

Мы превратили «линейное выражение» в древовидную структуру данных, теперь давайте посмотрим, как мы можем записать это выражение в Python.

Мы можем использовать объектно-ориентированное программирование, чтобы представить наше дерево в Python, поэтому изначально у нас есть класс Expression, и мы пока его пропустим.

Затем нам нужно определить подклассы, которые будут умножением, плюсом, переменной и нашей константой.

Теперь давайте добавим методы в наши классы, мы хотим инициализировать класс Expression.

Наш основной класс будет иметь левый и правый дочерние узлы.

Давайте также инициализируем наши подклассы;

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

Двоичное дерево поиска

Двоичное дерево поиска — это структура данных, позволяющая перемещаться по данным, разделяя их пополам.

Следующие свойства определяют бинарное дерево поиска:

У каждого родительского узла не более двух дочерних узлов, то есть родительский узел может иметь 2, 1 или не иметь дочерних узлов, но не более двух дочерних узлов.

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

Давайте проиллюстрируем это, используя следующие цифры; 40,19,50,23,35,41,55

Изначально дерево пусто, мы вставляем наше первое значение, равное 40, оно становится корневым узлом. Переходя к следующему числу, 19, мы хотим добавить 19 к нашему дереву, мы сначала проверяем, больше ли 19, чем текущее значение, равное 40.

Если оно меньше 40, мы вставляем его слева, если больше 40, мы вставляем его справа, 19 меньше 40, поэтому мы вставляем его в левую часть дерева. Мы переходим к следующему значению, равному 50, проверяем, больше оно или меньше 40, замечаем, что оно больше, и вставляем его справа.

Теперь и левый, и правый дочерние узлы заняты, нам еще нужно добавить 23,35,41,55 к нашему бинарному дереву.

Берем 23, сравниваем с 40 что больше его, значит вставляем в левую часть нашего дерева, но слева у нас уже 19, так что 23 тоже сравниваем с 19, так как 23 больше чем 19, мы добавляем его справа от 19, тем самым формируя дочерний узел 19. То же самое относится к остальным нашим цифрам, и конечным результатом является наше дерево.

Теперь, как нам перевести это в код Python?

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

Выше мы только что определили наш класс узла, нам все еще нужно определить наш класс дерева и, в частности, наш класс бинарного дерева поиска.

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

давайте разберем приведенный выше код:

Во-первых, мы определяем наш метод добавления и передаем self, value и current. Значение — это любое значение, которое мы хотим добавить в двоичное дерево поиска, а текущий — это текущий узел, который мы будем сравнивать со значением.

Наш оператор if говорит Python проверить, пуст ли корневой узел «self.root == None», и если это так, создает новый узел со значением.

С приведенным выше кодом мы возвращаемся к предыдущему коду, наш оператор else означает, что корневой узел занят, поэтому мы инструктируем Python проверить, меньше ли значение, которое мы хотим вставить, чем значение корневого узла. Если это так, то мы инструктируем его проверить, является ли этот левый узел пустым «current.left == None», и если он пуст, создайте узел с левой стороны.

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

Мы не можем указать Python проверять каждый узел и создавать пустые узлы с бесконечными операторами if и else, используя рекурсивный оператор «self.add» и передавать current.left и value в качестве наших аргументов.

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

Обход двоичного дерева поиска

Есть несколько операций, которые мы можем выполнять с бинарным деревом поиска. Сначала я хотел бы рассказать об обходе с помощью методов Pre-Order, In-Order и Post-Order.

Предварительный заказ

При обходе предварительного заказа мы делаем три простых шага: посещаем, идем налево, а затем идем направо. Давайте снова представим наш BST.

Поэтому, когда мы посещаем узел, мы распечатываем его, и, таким образом, наш порядок обхода предварительного порядка будет таким: 40,19,23,35,50,41,55

Мы всегда начинаем с нашего корневого узла, который равен 40, затем мы идем налево, где мы встретимся с 19, который мы посещаем и распечатываем, затем идем направо, где мы встретимся с 23, посещаем и распечатываем, переходим к 35, который мы посетим а затем распечатать.

Мы зашли так далеко влево и вправо в левой части нашего поддерева, поэтому мы возвращаемся назад, и теперь мы движемся вправо к 50, который мы посетим и распечатаем, затем идем налево, где мы найдем 41, который мы посетим и распечатать. Мы двигались максимально влево и вправо, 41 — дочерний узел, поэтому мы возвращаемся к 50 и идем влево, где находим 55, который мы посетим и распечатаем.

Теперь давайте скажем Python выполнить предварительный обход.

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

У нас есть наша функция предварительного заказа, которая является рекурсивной функцией, которая будет посещать, идти влево, затем вправо и повторять это до тех пор, пока не будут выполнены условия.

Обход по порядку

Мы следуем методам «слева», «посетить», «справа» и снова добавим наше дерево для иллюстрации.

Наш порядок для заказа будет; 19,23,35,40,41,50,55

При обходе по порядку мы исчерпываем все наши варианты налево, затем только мы посещаем узел, затем идем направо и посещаем.

Мы начинаем с нашего корневого узла, который равен 40, но мы не посещаем его, мы идем влево, где находим 19, мы прошли, насколько это возможно, с 19, что означает, что мы посещаем 19 и распечатываем его.

Теперь мы идем прямо к 23, который мы посещаем и распечатываем, а затем переходим к 35 и распечатываем его. Мы зашли так далеко влево и вправо, насколько это возможно, поэтому мы возвращаемся к 40 и посещаем его, затем пришло время двигаться вправо, где мы находим 50, которые мы еще не посещали, поскольку нам нужно исчерпать все наши варианты слева.

Итак, мы движемся влево и встречаем 41 и посещаем его, поскольку мы исчерпали все наши варианты движения влево, мы возвращаемся к 50 и посещаем узел, затем идем направо и посещаем наш последний узел.

Выпишем обход по порядку;

Обход после заказа

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

35,23,19,41,55,50,40

А вот код на Python, как и все остальные, мы просто немного рефакторим код.

Присоединяйтесь к FAUN: Сайт💻|Подкаст🎙️|Twitter🐦|Facebook👥 |Instagram📷|Группа Facebook🗣️|Группа Linkedin💬| Slack 📱|Cloud Native Новости📰|Дополнительно.

Если этот пост был полезен, пожалуйста, несколько раз нажмите кнопку аплодисментов 👏 ниже, чтобы выразить свою поддержку автору 👇