Как построить бинарное дерево Python: шаг за шагом руководство 🌳

Для построения бинарного дерева в Python нужно создать класс для узла дерева и класс для самого дерева.

Вот пример кода:

    
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        
class BinaryTree:
    def __init__(self):
        self.root = None
  
    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            self._insert_recursive(key, self.root)
            
    def _insert_recursive(self, key, current_node):
        if key < current_node.key:
            if current_node.left is None:
                current_node.left = Node(key)
            else:
                self._insert_recursive(key, current_node.left)
        else:
            if current_node.right is None:
                current_node.right = Node(key)
            else:
                self._insert_recursive(key, current_node.right)
    
    

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

Как построить бинарное дерево в Python

Добро пожаловать в эту подробную статью о том, как построить бинарное дерево в Python! Мы будем рассматривать концепции, код и примеры, чтобы вам было легче понять эту важную структуру данных.

Что такое бинарное дерево?

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

Как построить бинарное дерево?

Для начала давайте создадим класс Node(узел), который будет представлять узел в бинарном дереве.

    class Node:
        def __init__(self, value):
            self.value = value
            self.left = None
            self.right = None
    

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

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

Вот как мы можем использовать эту функцию:

    root = None
    root = insert(root, 10)
    root = insert(root, 5)
    root = insert(root, 15)
    root = insert(root, 3)
    root = insert(root, 7)
    root = insert(root, 12)
    root = insert(root, 17)
    

Как обойти бинарное дерево?

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

• Префиксный обход (Preorder traversal): Сначала посещаем текущий узел, затем его левого потомка и, наконец, правого потомка.
• Инфиксный обход (Inorder traversal): Сначала посещаем левого потомка текущего узла, затем сам текущий узел и, наконец, правого потомка.
• Постфиксный обход (Postorder traversal): Сначала посещаем левого потомка текущего узла, затем правого потомка и, наконец, сам текущий узел.

Давайте реализуем эти обходы с помощью рекурсии:

    def preorder(node):
        if node is not None:
            print(node.value)
            preorder(node.left)
            preorder(node.right)
            
    def inorder(node):
        if node is not None:
            inorder(node.left)
            print(node.value)
            inorder(node.right)
            
    def postorder(node):
        if node is not None:
            postorder(node.left)
            postorder(node.right)
            print(node.value)
    

Вы можете использовать следующий код для вызова этих функций:

    print("Префиксный обход:")
    preorder(root)
    
    print("Инфиксный обход:")
    inorder(root)
    
    print("Постфиксный обход:")
    postorder(root)
    

Заключение

Теперь у вас есть подробное понимание того, как построить и обойти бинарное дерево в Python! Мы рассмотрели основные концепции, представили код и привели примеры использования. Успехов в изучении этой важной структуры данных!