Обход — это процесс, который посещает все узлы дерева и может также печатать их значения. Поскольку все узлы связаны через ребра (ссылки), мы всегда начинаем с корневого (головного) узла. То есть мы не можем получить произвольный доступ к узлу в дереве. Есть три способа прохождения дерева:
- Порядок обхода
- Предварительный заказ обхода
- Обход после заказа
Порядок обхода
В этом методе обхода сначала посещается левое поддерево, затем корень, а затем правое поддерево. Мы всегда должны помнить, что каждый узел может представлять само поддерево.
В приведенной ниже программе 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))
Когда приведенный выше код выполняется, он дает следующий результат —