Глубина бинарного дерева python

Максимальная глубина бинарного дерева в питоне

Я создал кортеж из двоичного дерева, и это выглядит так:

Древовидная структура становится более ясной, применяя отступы:

(1, (2, (4, 5, 6), (7, Никто, 8)), (3, 9, (10, 11, 12)))

Я знаю, как найти максимальную глубину двоичного дерева, используя рекурсивный метод, но я пытаюсь найти максимальную глубину, используя созданный мной кортеж. Может кто-нибудь помочь мне с тем, как это сделать?

4 ответа

a = (1,(2,(4,5,6),(7,None,8)),(3,9,(10,11,12))); def depth(x): if(isinstance(x, int) or x == None): return 1; else: dL = depth(x[1]); dR = depth(x[2]); return max(dL, dR) + 1; print(depth(a)); 

Идея состоит в том, чтобы определить глубину дерева, посмотрев на его левое и правое поддерево. Если у узла нет поддеревьев, возвращается глубина 1. В противном случае возвращает max(глубина справа, глубина слева) + 1

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

string = str(myTuple) currentDepth = 0 maxDepth = 0 for c in string: if c == '(': currentDepth += 1 elif c == ')': currentDepth -= 1 maxDepth = max(maxDepth, currentDepth) 

Это дает глубину в линейном времени относительно количества символов в строке, в которую был преобразован кортеж. Это число должно быть более или менее пропорционально количеству элементов плюс глубина, поэтому сложность будет примерно равна O(n + d) ,

Я решаю это с обходом порядка уровней. Если вы знаете обход порядка уровней, этот вопрос и вопрос https://leetcode.com/problems/binary-tree-right-side-view/ можно решить с помощью одной и той же техники:

from collections import deque class Solution: def max_depth(self,root): if not root: return 0 level=0 q=deque([root]) while q: # once we exhaust the for loop, that means we traverse all the nodes in the same level # so after for loop increase level+=1 for i in range(len(q)): node=q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) level+=1 return level 

Источник

Русские Блоги

Описание Python процесса двоичного дерева в глубину и в ширину

Двоичное дерево в первую очередь в глубину (DFS) и сначала в ширину (BFS)

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

• Обход первого порядка (корня): для любого поддерева сначала посетите корень, затем обойдите его левое поддерево и, наконец, обойдите его правое поддерево.
• Обход среднего (корневого) порядка: для любого поддерева сначала обойдите его левое поддерево, затем посетите корень и, наконец, обойдите его правое поддерево.
• Пост-порядковый (корневой) обход: для любого поддерева сначала обойдите его левое поддерево, затем его правое поддерево и, наконец, посетите корень.

Описание алгоритма Python DFS:

def depth_tree(tree_node): """ # Процесс сначала в глубину :param tree_node: :return: """ if tree_node is not None: print(tree_node._data) if tree_node._left is not None: return depth_tree(tree_node._left) if tree_node._right is not None: return depth_tree(tree_node._right) 

Примечание: scrapy По умолчанию сначала применяется глубина.

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

def level_queue(root): """ # В первую очередь процесс :param root: :return: """ if root is None: return my_queue = [] node = root my_queue.append(node) while my_queue: node = my_queue.pop(0) print(node.elem) if node.lchild is not None: my_queue.append(node.lchild) if node.rchild is not None: my_queue.append(node.rchild) 

различия:

Как правило, метод поиска в глубину не сохраняет все узлы во время обхода. После обхода узлы выталкиваются и удаляются из стека. Таким образом, количество узлов, хранящихся в стеке, обычно является значением глубины двоичного дерева, поэтому оно занимает меньше места. Следовательно, когда в дереве поиска много узлов и другие методы подвержены переполнению памяти, поиск в глубину может быть эффективным методом решения. Однако алгоритм поиска в глубину имеет операции отслеживания с возвратом (то есть операции наложения и выталкивания), а скорость выполнения низкая.

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

Источник

Алгоритмы обхода дерева в Python, которые должен знать каждый разработчик

Программирование и разработка

Алгоритмы являются важной частью карьеры разработчика программного обеспечения, как на собеседованиях, так и на работе. Многие стартапы и компании FAANG, такие как Facebook и Google, в основном сосредотачиваются на алгоритмах и структурах данных во время собеседований, поэтому понимание этих концепций может иметь важное значение для продвижения по карьерной лестнице.

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

Сегодня мы обсудим алгоритмы обхода дерева в Python, о которых часто спрашивают на собеседованиях по разработке программного обеспечения.

Мы уделим особое внимание Python по сравнению с другими языками программирования из-за его растущей популярности среди компаний и простого в использовании синтаксиса.

Что такое деревья (trees)?

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

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

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

Изображение древовидной структуры данных

Номенклатура деревьев

• Узел: Узел или вершина — это структура, которая может содержать данные и соединения с другими узлами (известными как ее дочерние узлы). Связь между двумя узлами называется ребром. Ребро может быть исходящим или входящим к узлу. Например, на рисунке выше узел-2 имеет входящее ребро от узла-1 и два исходящих края к узлу-4 и узлу-5.
• Листовой узел: узел без исходящих ребер называется листовым узлом. В приведенном выше примере Node-4, Node-8, Node-10 и Node-7 являются конечными узлами.
• Корневой узел: Корневой узел не имеет входящих к нему ребер. Обычно он считается самым верхним узлом дерева. В нашем примере Node-1 является корневым узлом. Как правило, дерево должно иметь ровно один корневой узел.
• Высота узла: максимальное количество ребер от узла до конечного узла. В приведенном выше примере высоты узлов Node-3 и Node-4 равны 3 и 0 соответственно.
• Глубина узла: количество ребер от корня до узлов в дереве. В приведенном выше примере глубина узлов Node-3 и Node-10 равна 1 и 4 соответственно.
• Высота дерева: высота корневого узла или глубина самого глубокого узла.
• Степень выхода и степень входа узла: степень входа узла относится к количеству входящих ребер, тогда как исходящая степень относится к количеству исходящих ребер. В приведенном выше примере узел-3 имеет входную степень 1, а исходящую степень 2.
• Префикс: здесь мы получаем доступ к дереву, начиная с корневого узла, за которым следует левый дочерний элемент, а затем, наконец, правый дочерний узел.
• Постфикс: здесь мы получаем доступ к дереву, начиная сначала с левого дочернего элемента, затем правого дочернего элемента и, наконец, корневого узла.
• In-fix: здесь мы получаем доступ к дереву, начиная с левого дочернего элемента, корневого узла и, наконец, правого дочернего элемента.

Как обойти деревья

Обход дерева — это процесс, в котором мы посещаем каждый узел дерева, при необходимости распечатывая данные из этих узлов. Мы всегда начинаем поиск с корневого узла, потому что оттуда доступны все узлы.

Есть два способа обойти дерево. Один использует подход в глубину, а второй использует метод в ширину.

Поиск в глубину

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

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

Рисунок, изображающий обход дерева

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

В этом методе обхода дерева мы сначала посещаем левое поддерево, затем корень и, наконец, правое поддерево.

Давайте посмотрим на обход по порядку в действии. В приведенном ниже примере Python мы делаем следующее:

• Строка 5-9: Создайте класс Node. В классе три участника
  • Левый дочерний элемент: содержит левого дочернего элемента узла.
  • Правый дочерний элемент: содержит правый дочерний элемент узла.
  • Данные: значение узла

  Обход предварительного заказа

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

  В нашем примере ниже мы предпримем следующие шаги:

  • Строка 4-9: Создайте класс Node. В классе три участника
    • Левый дочерний элемент: содержит левого дочернего элемента узла.
    • Правый дочерний элемент: содержит правый дочерний элемент узла.
    • Данные: значение узла

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

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

    Давайте учиться на примере. В приведенной ниже программе Python мы делаем следующее:

    • Строка 4-9: Создайте класс Node. В классе три участника
      • Левый дочерний элемент: содержит левого дочернего элемента узла.
      • Правый дочерний элемент: содержит правый дочерний элемент узла.
      • Данные: значение узла

      Применение алгоритмов обхода дерева в глубину

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

      Алгоритмы поиска в ширину

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

      Алгоритмы поиска в ширину (BFS) следующие:

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

      В нашем интерактивном редакторе кода выше в кодах обхода в глубину наша функция printTreeпечатает treeс использованием BFS. Мы призываем вас внимательно наблюдать за нашей реализацией printTreeи экспериментировать с ней.

      Заключение

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

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

      • Дано бинарное дерево,
      • Найти его высоту
      • Обход двоичного дерева по порядку
      • Максимальная глубина бинарного дерева
      • Суммировать корень в листовые числа

      Источник