Python обход дерева in order to

Да, двоичные деревья — не самая любимая тема программистов. Это одна из тех старых концепций, о целесообразности изучения которых постоянно ведутся споры. В работе вам довольно редко придется реализовывать двоичные деревья и обходить их, так зачем же уделять им так много внимания на технических собеседованиях?

Сегодня мы не будем переворачивать двоичное дерево (ффухх!), но рассмотрим пару методов его обхода. К концу статьи вы поймете, что двоичные деревья не так страшны, как кажется.

Что такое двоичное дерево?

Недавно мы разбирали реализацию связных списков на Python. Каждый такой список состоит из некоторого количества узлов, указывающих на другие узлы. А если бы узел мог указывать не на один другой узел, а на большее их число? Вот это и есть деревья. В них каждый родительский узел может иметь несколько узлов-потомков. Если у каждого узла максимум два узла-потомка (левый и правый), такое дерево называется двоичным (бинарным).

В приведенном выше примере «корень» дерева, т. е. самый верхний узел, имеет значение 1. Его потомки — 2 и 3. Узлы 3, 4 и 5 называют «листьями»: у них нет узлов-потомков.

Строим двоичное дерево на Python

Как построить дерево на Python? Реализация будет похожей на наш класс Node в реализации связного списка. В этом случае мы назовем класс TreeNode.

Определим метод __init__(). Как всегда, он принимает self. Также мы передаем в него значение, которое будет храниться в узле.

class TreeNode: def __init__(self, value):

Установим значение узла, а затем определим левый и правый указатель (для начала поставим им значение None).

class TreeNode: def __init__(self, value): self.value = value self.left = None self.right = None

И… все! Что, думали, что деревья куда сложнее? Если речь идет о двоичном дереве, единственное, что его отличает от связного списка, это то, что вместо next у нас тут есть left и right.

Давайте построим дерево, которое изображено на схеме в начале статьи. Верхний узел имеет значение 1. Далее мы устанавливаем левые и правые узлы, пока не получим желаемое дерево.

tree = TreeNode(1) tree.left = TreeNode(2) tree.right = TreeNode(3) tree.left.left = TreeNode(4) tree.left.right = TreeNode(5)

Обход двоичного дерева

Итак, вы построили дерево и теперь вам, вероятно, любопытно, как же его увидеть. Нет никакой команды, которая позволила бы вывести на экран дерево целиком, тем не менее мы можем обойти его, посетив каждый узел. Но в каком порядке выводить узлы?

Самые простые в реализации обходы дерева — прямой (Pre-Order), обратный (Post-Order) и центрированный (In-Order). Вы также можете услышать такие термины, как поиск в ширину и поиск в глубину, но их реализация сложнее, ее мы рассмотрим как-нибудь потом.

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

При прямом обходе мы посещаем родительские узлы до посещения узлов-потомков. В случае с нашим деревом мы будем обходить узлы в таком порядке: 1, 2, 4, 5, 3.

Обратный обход двоичного дерева — это когда вы сначала посещаете узлы-потомки, а затем — их родительские узлы. В нашем случае порядок посещения узлов при обратном обходе будет таким: 4, 5, 2, 3, 1.

При центрированном обходе мы посещаем все узлы слева направо. Центрированный обход нашего дерева — это посещение узлов 4, 2, 5, 1, 3.

Давайте напишем методы обхода для нашего двоичного дерева.

Pre-Order

Начнем с определения метода pre_order(). Наш метод принимает один аргумент — корневой узел (расположенный выше всех).

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

def pre_order(node): if node: pass

Написать обход просто. Прямой обход — это посещение родительского узла, а затем каждого из его потомков. Мы «посетим» родительский узел, выведя его на экран, а затем «обойдем» детей, вызывая этот метод рекурсивно для каждого узла-потомка.

# Выводит родителя до всех его потомков def pre_order(node): if node: print(node.value) pre_order(node.left) pre_order(node.right)

Просто, правда? Можем протестировать этот код, совершив обход построенного ранее дерева.

Post-Order

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

Вместо «посещения» родительского узла и последующего «обхода» детей, мы сначала «обойдем» детей, а затем «посетим» родительский узел. То есть, мы просто передвинем print на последнюю строку! Не забудьте поменять имя метода на post_order() во всех вызовах.

# Выводит потомков, а затем родителя def post_order(node): if node: post_order(node.left) post_order(node.right) print(node.value)

Каждый узел-потомок посещен до посещения его родителя.

In-Order

Наконец, напишем метод центрированного обхода. Как нам обойти левый узел, затем родительский, а затем правый? Опять же, нужно переместить предложение print!

# выводит левого потомка, затем родителя, затем правого потомка def in_order(node): if node: in_order(node.left) print(node.value) in_order(node.right)

Вот и все, мы рассмотрели три простейших способа совершить обход двоичного дерева.

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

Источник

In-order Tree Traversal in Python

You might have studied algorithms to traverse a python dictionary, a list, or a tuple. In this article, we will study the in-order traversal algorithm to traverse a binary tree. We will also discuss the implementation of the algorithm.

What is an In-order tree traversal algorithm?

In-order tree traversal algorithm is a depth first traversal algorithm. It means that we traverse the children of a node before traversing its siblings. In this way, we traverse to the maximum depth, print the elements till the last node and then come back to the top to print other elements.

The algorithm is termed as in-order traversal algorithm because, when we traverse a binary search tree using this algorithm, The elements of the tree are printed in increasing order of their value.

Algorithm for In-order Traversal

We know that, In a binary search tree, The left child of any node contains an element less than the current node and the right child of a node contains an element greater than the current node. So, to print the elements in order, we will have to print the left child first, then the current node and the right child at last. This same rule will be used to print each node of the tree.

We will start from the root node, will traverse the left child or left sub-tree of the current node and then we will traverse the current node. At last we will traverse the right child or right sub-tree of the current node. We will perform this operation recursively till all the nodes are traversed.

To understand the concept better, let us use an example binary search tree and traverse it using the In-order binary tree traversal algorithm.

Here, we will start from root node 50. Before printing 50, we have to traverse the left subtree of 50. So, we will go to 20. Before printing 20, we have to traverse the left subtree of 20. So, we will go to 11. As 11 has no children, we will print 11 and move upwards to 20. After printing 20, we will traverse right subtree of 20. As 22 has no children, we will print 22 and move upwards to 50. At 50, its left subtree has been traversed, so we will print 50. After that we will traverse the right subtree of 50 using the same process. The in-order traversal of whole tree is : 11, 20, 22, 50, 52, 53, 78.

Implementation of In-order tree traversal in Python

The algorithm for in-order tree traversal can be formulated as follows.

Recursively Traverse the left sub-tree.
Print the root node.
Recursively Traverse the right sub-tree.

Here, we print the element in the node only if it is a leaf node or all the elements in its left subtree have already been printed.

We will now implement the above algorithm in python and will execute it for the binary search tree given in the above example.

class BinaryTreeNode: def __init__(self, data): self.data = data self.leftChild = None self.rightChild = None def inorder(root): # if root is None,return if root == None: return # traverse left subtree inorder(root.leftChild) # print the current node print(root.data, end=" ,") # traverse right subtree inorder(root.rightChild) def insert(root, newValue): # if binary search tree is empty, create a new node and declare it as root if root is None: root = BinaryTreeNode(newValue) return root # if newValue is less than value of data in root, add it to left subtree and proceed recursively if newValue < root.data: root.leftChild = insert(root.leftChild, newValue) else: # if newValue is greater than value of data in root, add it to right subtree and proceed recursively root.rightChild = insert(root.rightChild, newValue) return root root = insert(None, 50) insert(root, 20) insert(root, 53) insert(root, 11) insert(root, 22) insert(root, 52) insert(root, 78) print("Inorder traversal of the binary tree is:") inorder(root)

Inorder traversal of the binary tree is: 11 ,20 ,22 ,50 ,52 ,53 ,78 ,

Conclusion

In this article, we have discussed the In-order tree traversal algorithm in Python. In next articles, we will implement other tree traversal algorithms such as preorder tree traversal, and postorder tree traversal algorithm. To learn more about other data structures, you can read this article on Linked List in Python.

Источник

Python обход дерева in order to