Python глубина бинарного дерева

Русские Блоги

Описание Python процесса двоичного дерева в глубину и в ширину

Двоичное дерево в первую очередь в глубину (DFS) и сначала в ширину (BFS)

Обход в глубину: Углубить каждый возможный путь ветвления до точки, где он не может идти дальше, и к каждому узлу можно получить доступ только один раз. Общий нерекурсивный подход обхода двоичного дерева в глубину заключается в использовании стеков. Следует отметить, что обход двоичных деревьев в глубину является особенным и может быть разделен на обход первого порядка, обход среднего порядка и обход после порядка. Конкретные инструкции следующие:

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

Описание алгоритма Python DFS:

def depth_tree(tree_node): """ # Процесс сначала в глубину :param tree_node: :return: """ if tree_node is not None: print(tree_node._data) if tree_node._left is not None: return depth_tree(tree_node._left) if tree_node._right is not None: return depth_tree(tree_node._right) 

Примечание: scrapy По умолчанию сначала применяется глубина.

Первый обход в ширину: Это также называется обходом уровней. Каждый слой посещается последовательно сверху вниз. В каждом слое узлы посещаются слева направо (или справа налево). После посещения одного слоя переходите на следующий уровень, пока Пока нельзя будет посетить ни один узел. Общий нерекурсивный подход для обхода в ширину заключается в использовании очередей.

def level_queue(root): """ # В первую очередь процесс :param root: :return: """ if root is None: return my_queue = [] node = root my_queue.append(node) while my_queue: node = my_queue.pop(0) print(node.elem) if node.lchild is not None: my_queue.append(node.lchild) if node.rchild is not None: my_queue.append(node.rchild) 

различия:

Как правило, метод поиска в глубину не сохраняет все узлы во время обхода. После обхода узлы выталкиваются и удаляются из стека. Таким образом, количество узлов, хранящихся в стеке, обычно является значением глубины двоичного дерева, поэтому оно занимает меньше места. Следовательно, когда в дереве поиска много узлов и другие методы подвержены переполнению памяти, поиск в глубину может быть эффективным методом решения. Однако алгоритм поиска в глубину имеет операции отслеживания с возвратом (то есть операции наложения и выталкивания), а скорость выполнения низкая.

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

Источник

how to find the height of a node in binary tree recursively

this is my sample code for find the Height, is defined as the length of the longest path by number of nodes from self to a leaf. The height of a leaf node is 1. it doesn’t work.

Actually, I just need an algorithm. Because, my code doesn’t work. And if you know the solution, maybe pseudo code 😛

@thg435 My guess is: «why doesn’t it work?» The poster seems to be struggling with English, so I would give him a break here. That being said, I wouldn’t give the code (since it looks like a homework to me), but explain some of the more blatant mistakes that he made.

@TGulmammadov: two options. Option 1: draw a tree on a piece of paper and try to find the height for any given node manually. Note your steps. Try to describe what you’re doing first in pseudocode and then in python. Option 2: sit back and wait for some nice guy to post the codez for you.

Do you have an example where it fails? How does it fail? Let me guess: it always counts the depth of the leftmost path, not of arbitrary paths?

6 Answers 6

What you’re doing isn’t recursive, it’s iterative. Recursive would be something like:

def height(node): if node is None: return 0 else: return max(height(node.left), height(node.right)) + 1 

return max(height(node.left), height(node.right)) + 1 returns a value >= 1 however leaf nodes have height zero. @mata Could you please clarify. Thanks.

@harishvc — Looking at the edit history, I had return -1 , which means a leaf would have a height of 0 (which is usually how the hight of a tree is defined), but the OP specified «The height of a leaf node is 1», so that’s probably why I changed it.

A leaf node will have None for node.left and node.right , therefore ending the recursion there, there’s no need to treat leaf or inner or root nodes differently.

@Illusionist — for any node the height ist the height of it’s largest child tree (that’s what the max function does) + 1. For a leaf node where both node.left and node.right are None heigh will return 0 for both and the recursion ends there.

You were given the solution by mata, but I suggest you also look at your code and understand what it is doing:

 while self.right != None: self = self.right path = path +1 

What will this do? it will find the right child, then its right child, and so on. So this checks only one path of the «rightmost» leaf.

This does the same for the left:

 while self.left != None: self = self.left path = path +1 

The idea in recursion is that for each subproblem, you solve it using the exact same recipe for all other subproblems. So if you would apply your algorithm only to a subtree or a leaf, it would still work.

Also, a recursive definition calls itself (although you can implement this with a loop, but that is beyond the scope here).

Recursion: see definition of Recursion.

Источник

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

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

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

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

Недавно мы разбирали реализацию связных списков на 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)

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

Источник