Python - алгоритмы обхода дерева

Обход - это процесс посещения всех узлов дерева и также может распечатать их значения. Поскольку все узлы соединены ребрами (связями), мы всегда начинаем с корневого (головного) узла. То есть мы не можем получить произвольный доступ к узлу в дереве. Есть три способа, которые мы используем, чтобы пройти по дереву:

  • Обход по порядку
  • Предварительный заказ обхода
  • Пост-заказ обход

Обход по порядку

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

В приведенной ниже программе на Python мы используем класс Node для создания заполнителей для корневого узла, а также для левого и правого узлов. Затем мы создаем функцию вставки для добавления данных в дерево. Наконец, реализуется логика обхода Inorder путем создания пустого списка и добавления сначала левого узла, а затем корневого или родительского узла. Наконец, добавлен левый узел, чтобы завершить обход Inorder. Обратите внимание, что этот процесс повторяется для каждого поддерева, пока не будут пройдены все узлы.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data
# Insert Node
    def insert(self, data):

        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()

# Inorder traversal
# Left -> Root -> Right
    def inorderTraversal(self, root):
        res = []
        if root:
            res = self.inorderTraversal(root.left)
            res.append(root.data)
            res = res + self.inorderTraversal(root.right)
        return res

root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))

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

[10, 14, 19, 27, 31, 35, 42]

Предварительный заказ обхода

В этом методе обхода сначала посещается корневой узел, затем левое поддерево и, наконец, правое поддерево.

В приведенной ниже программе на Python мы используем класс Node для создания заполнителей для корневого узла, а также для левого и правого узлов. Затем мы создаем функцию вставки для добавления данных в дерево. Наконец, реализуется логика обхода предварительного заказа путем создания пустого списка и добавления сначала корневого узла, а затем левого узла. Наконец, правый узел добавлен для завершения обхода предварительного заказа. Обратите внимание, что этот процесс повторяется для каждого поддерева, пока не будут пройдены все узлы.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data
# Insert Node
    def insert(self, data):

        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()

# Preorder traversal
# Root -> Left ->Right
    def PreorderTraversal(self, root):
        res = []
        if root:
            res.append(root.data)
            res = res + self.PreorderTraversal(root.left)
            res = res + self.PreorderTraversal(root.right)
        return res

root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))

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

[27, 14, 10, 19, 35, 31, 42]

Пост-заказ обход

В этом методе обхода корневой узел посещается последним, отсюда и название. Сначала мы обходим левое поддерево, затем правое поддерево и, наконец, корневой узел.

В приведенной ниже программе на Python мы используем класс Node для создания заполнителей для корневого узла, а также для левого и правого узлов. Затем мы создаем функцию вставки для добавления данных в дерево. Наконец, реализуется логика обхода пост-заказа путем создания пустого списка и добавления сначала левого узла, а затем правого узла. Наконец, добавляется корневой или родительский узел для завершения обхода пост-заказа. Обратите внимание, что этот процесс повторяется для каждого поддерева, пока не будут пройдены все узлы.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data
# Insert Node
    def insert(self, data):

        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()

# Postorder traversal
# Left ->Right -> Root
    def PostorderTraversal(self, root):
        res = []
        if root:
            res = self.PostorderTraversal(root.left)
            res = res + self.PostorderTraversal(root.right)
            res.append(root.data)
        return res

root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))

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

[10, 19, 14, 31, 42, 35, 27]