Учебники

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

Декабрь 19, 2018

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

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

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

Создать Root

Мы просто создаем класс 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()

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

10

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

Для вставки в дерево мы используем тот же класс узлов, созданный выше, и добавляем в него класс вставки. Класс вставки сравнивает значение узла с родительским узлом и решает добавить его в качестве левого узла или правого узла. Наконец, класс 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

Обход дерева

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

84
Share: