Код для печати двоичного дерева в Python

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

В этом уроке мы создадим бинарное дерево на языке Python и напишем код для его вывода.

Содержание

Шаг 1. Определите двоичное дерево

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

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

Этот класс представляет узел бинарного дерева. Каждый узел содержит некоторые данные и ссылки на своих левого и правого потомков.

Шаг 2. Вставьте данные в двоичное дерево

Чтобы вставить данные в дерево, мы определим функцию вставки:

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

Если дерево пустое (корень равен None), мы создаём новый узел с заданными данными и возвращаем его. В случае, когда дерево не пустое, мы рекурсивно вставляем данные либо в левое, либо в правое поддерево, в зависимости от значения данных.

Шаг 3. Распечатайте двоичное дерево

Есть несколько способов «распечатать» двоичное дерево. Здесь мы реализуем методы обхода по порядку, по предзаказу и после заказа:

  • Обход по порядку: в этом методе обхода сначала посещается левое поддерево, затем корень, а затем правое поддерево.
def print_inorder(root):
    if root:
        print_inorder(root.left)
        print(root.data, end=" ")
        print_inorder(root.right)
  • Обход по предварительному заказу: в этом методе обхода сначала посещается корневой узел, затем левое поддерево и, наконец, правое поддерево.
def print_preorder(root):
    if root:
        print(root.data, end=" ")
        print_preorder(root.left)
        print_preorder(root.right)
  • Обход после заказа: в этом методе обхода корневой узел посещается последним. Сначала мы проходим левое поддерево, затем правое поддерево и, наконец, корневой узел.

Шаг 4. Код для печати двоичного дерева

Вот полный код:

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

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

def print_inorder(root):
    if root:
        print_inorder(root.left)
        print(root.data, end=" ")
        print_inorder(root.right)

def print_preorder(root):
    if root:
        print(root.data, end=" ")
        print_preorder(root.left)
        print_preorder(root.right)

def print_postorder(root):
    if root:
        print_postorder(root.left)
        print_postorder(root.right)
        print(root.data, end=" ")

root = Node(50)

root = insert(root, 30)
root = insert(root, 20)
root = insert(root, 40)
root = insert(root, 70)
root = insert(root, 60)
root = insert(root, 80)

print("In-order traversal:")
print_inorder(root)

print("\nPre-order traversal:")
print_preorder(root)

print("\nPost-order traversal:")
print_postorder(root)

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

Код для печати двоичного дерева

Добавить комментарий