Итак, что же такое бинарное дерево? Что ж, представьте себе древовидную структуру, в которой каждый узел может иметь не более двух дочерних элементов. Это двоичное дерево! Думайте об этом как о генеалогическом древе, где у каждого человека может быть не более двух детей (братьев и сестер).

Давайте начнем с создания простого двоичного дерева в коде. Вот фрагмент на Python:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
# Creating a binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)

В этом примере мы определили класс Node, который представляет каждый узел двоичного дерева. Каждый узел имеет значение и два дочерних узла: leftи right. Затем мы создаем двоичное дерево, связывая узлы вместе.

Теперь давайте рассмотрим некоторые распространенные методы и операции, которые мы можем выполнять с двоичными деревьями:

1. Обход. Обход двоичного дерева означает посещение каждого узла в определенном порядке. Существует два популярных способа обхода двоичного дерева: поиск в глубину (DFS) и поиск в ширину (BFS).

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

     def pre_order_traversal(node):
      if node:
          print(node.value)
          pre_order_traversal(node.left)
          pre_order_traversal(node.right)
     
     def in_order_traversal(node):
      if node:
          in_order_traversal(node.left)
          print(node.value)
          in_order_traversal(node.right)
     
     def post_order_traversal(node):
      if node:
          post_order_traversal(node.left)
          post_order_traversal(node.right)
          print(node.value)

   • В BFS мы посещаем узлы уровень за уровнем, начиная с корня. Мы исследуем все узлы на текущем уровне, прежде чем перейти к следующему уровню.

     def breadth_first_search(root):
      queue = [root]
      while queue:
          node = queue.pop(0)
          print(node.value)
          if node.left:
              queue.append(node.left)
          if node.right:
              queue.append(node.right)

2. Вставка. Добавление нового узла в двоичное дерево предполагает поиск подходящей позиции для нового узла на основе его значения. Если значение меньше текущего узла, мы идем влево; в противном случае мы идем направо.

   def insert_node(root, value):
      if root is None:
          return Node(value)
      if value < root.value:
          root.left = insert_node(root.left, value)
      else:
          root.right = insert_node(root.right, value)
      return root

3. Поиск. Поиск определенного значения в двоичном дереве аналогичен вставке. Мы сравниваем целевое значение со значением текущего узла и перемещаемся влево или вправо соответственно, пока не найдем совпадение или не достигнем конечного узла.

   def search_node(root, value):
      if root is None or root.value == value:
          return root
      if value < root.value:
          return search_node(root.left, value)
      else:
          return search_node(root.right, value)

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

   (Пример кода для удаления немного длинный, поэтому для краткости я его пропущу.)

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

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