Python - двоичное дерево

Дерево представляет собой узлы, соединенные ребрами. Это нелинейная структура данных. Он обладает следующими свойствами.

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

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

Создать рут

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

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data


    def PrintTree(self):
        print(self.data)

root = Node(10)

root.PrintTree()

Когда приведенный выше код выполняется, он дает следующий результат:

Вставка в дерево

Для вставки в дерево мы используем тот же класс узла, созданный выше, и добавляем к нему метод вставки. Метод вставки сравнивает значение узла с родительским узлом и решает добавить его как левый узел или как правый узел. Наконец, для печати дерева используется метод PrintTree.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
# Compare the new value with the parent node
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)

root.PrintTree()

Когда приведенный выше код выполняется, он дает следующий результат:

3 6 12 14

Путешествие по дереву

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