Обход двоичного дерева на 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)
Вот и все, мы рассмотрели три простейших способа совершить обход двоичного дерева.
Источник
Обход бинарных деревьев: рекурсия, итерации и указатель на родителя
Основы о бинарных деревьях представлены, в том числе, здесь . Добавлю свои «5 копеек» и данным постом систематизирую материалы, связанные с обходом бинарных деревьев, а именно сравнений возможностей рекурсии и итераций, а также обсуждение возможностей использования указателя на родительский узел.
Итак… язык Java, класс узла имеет следующий вид:
Примечание: Указатель на родителя parent – как правило не имеет большого смысла, однако, как следует из заголовка и будет показано, может быть полезен в ряде случаев.
Обход деревьев – последовательная обработка (просмотр, изменение и т.п.) всех узлов дерева, при котором каждый узел обрабатывается строго один раз. При этом получается линейная расстановка узлов дерева.
В зависимости от траекторий выделяют два типа обхода:
— горизонтальный (в ширину); и
— вертикальный (в глубину).
Горизонтальный обход подразумевает обход дерева по уровням (level-ordered) – вначале обрабатываются все узлы текущего уровня, после чего осуществляется переход на нижний уровень.
При вертикальном обходе порядок обработки текущего узла и узлов его правого и левого поддеревьев варьирует и по этому признаку выделяют три варианта вертикального обхода:
— прямой (префиксный, pre-ordered): вершина – левое поддерево – правое поддерево;
— обратный (инфиксный, in-ordered): левое поддерево – вершина – правое поддерево; и
— концевой (постфиксный, post-ordered): левое поддерево – правое поддерево – вершина.
Сам обход во всех случаях в принципе один и тот же, различается порядок обработки. Для представления в каком порядке будет проходить обработка узлов дерева удобно следовать по «контуру обхода». При прямом обходе узел будет обработан в точке слева от узла, при обратном снизу от узла и при концевом, соответственно, справа от узла.
Другими словами «находясь» в некотором узле, нам нужно знать, нужно ли его обрабатывать и куда двигаться дальше.
Рекурсия
Все три варианта вертикального обхода элементарно реализуются рекурсивными функциями.
void recPreOrder() < treatment(); if (left!=null) left.recPreOrder(); if (right!=null) right.recPreOrder(); >void recInOrder() < if (left!=null) left.recInOrder(); treatment(); if (right!=null) right.recInOrder(); >void recPostOrder()
Рекурсия крайне удобна не только при обходе, но также при построении дерева, поиска в дереве, а также балансировки. Однако рекурсией нельзя осуществить горизонтальный обход дерева. В этом случае, а так же при обеспокоенности перегрузкой программного стека, следует применять итерационный подход.
Контейнеры
В случае использования итераций необходимо хранить сведенья о посещенных, но не обработанных узлах. Используются контейнеры типа стек (для вертикального обхода) и очередь (для горизонтального обхода).
Горизонтальный обход:
обрабатываем первый в очереди узел, при наличии дочерних узлов заносим их в конец очереди. Переходим к следующей итерации.
static void contLevelOrder(Node top) < Queuequeue=new LinkedList<> (); do< top.treatment(); if (top.left!=null) queue.add(top.left); if (top.right!=null) queue.add(top.right); if (!queue.isEmpty()) top=queue.poll(); >while (!queue.isEmpty()); > Вертикальный прямой обход:
обрабатываем текущий узел, при наличии правого поддерева добавляем его в стек для последующей обработки. Переходим к узлу левого поддерева. Если левого узла нет, переходим к верхнему узлу из стека.
static void contPreOrder(Node top) < Stackstack = new Stack<> (); while (top!=null || !stack.empty()) < if (!stack.empty())< top=stack.pop(); >while (top!=null) < top.treatment(); if (top.right!=null) stack.push(top.right); top=top.left; >> > Вертикальный обратный обход:
из текущего узла «спускаемся» до самого нижнего левого узла, добавляя в стек все посещенные узлы. Обрабатываем верхний узел из стека. Если в текущем узле имеется правое поддерево, начинаем следующую итерацию с правого узла. Если правого узла нет, пропускаем шаг со спуском и переходим к обработке следующего узла из стека.
static void contInOrder(Node top) < Stackstack = new Stack<> (); while (top!=null || !stack.empty()) < if (!stack.empty())< top=stack.pop(); top.treatment(); if (top.right!=null) top=top.right; else top=null; >while (top!=null) < stack.push(top); top=top.left; >> > Вертикальный концевой обход:
Здесь ситуация усложняется – в отличие от обратного обхода, помимо порядка спуска нужно знать обработано ли уже правое поддерево. Одним из вариантов решения является внесение в каждый экземпляр узла флага, который бы хранил соответствующую информацию (не рассматривается). Другим подходом является «кодирование» непосредственно в очередности стека — при спуске, если у очередного узла позже нужно будет обработать еще правое поддерево, в стек вносится последовательность «родитель, правый узел, родитель». Таким образом, при обработке узлов из стека мы сможем определить, нужно ли нам обрабатывать правое поддерево.
static void contPostOrder(Node top) < Stackstack = new Stack<> (); while (top!=null || !stack.empty())< if (!stack.empty())< top=stack.pop(); if (!stack.empty() && top.right==stack.lastElement())< top=stack.pop(); >else < top.treatment(); top=null; >> while (top!=null) < stack.push(top); if (top.right!=null)< stack.push(top.right); stack.push(top); >top=top.left; > > > Об указателе на родителя
Наличие в экземпляре класса указателя на родителя приносит определенные хлопоты при построении и балансировки деревьев. Однако, возможность из произвольного узла дерева «дойти» до любого из его узлов может придтись весьма кстати. Все, за чем нужно следить при «подъеме» на верхний уровень – пришли ли от правого потомка или от левого.
Так, с использованием родительских указателей будет выглядеть код вертикального концевого обхода.
static void parentPostOrder(Node top) < boolean fromright=false; Node shuttle=top, holder; while(true)< while (fromright)< shuttle.treatment(); if (shuttle==top) return; holder=shuttle; shuttle=shuttle.parent; fromright=shuttle.right==holder; if (!fromright && shuttle.right!=null) shuttle=shuttle.right; else fromright=true; >while (shuttle.left!=null) shuttle=shuttle.left; if (shuttle.right!=null) shuttle=shuttle.right; else fromright=true; > > Другой класс задач, которые позволяет решить родительский указатель, как уже было упомянуто — перемещение внутри дерева.
Так, что бы перейти на n-ый по счету узел от текущего узла, без «ориентации в дереве» пришлось бы обходить дерево с самого начала, до известного узла, а потом еще n-узлов. С использованием же родительского указателя при обратном обходе дерева перемещение на steps узлов от текущего узла (start) будет иметь следующий вид.
public static Node walkTheTree(Node start, int steps) < boolean fromright=true; Node shuttle=start, holder; if (shuttle.right!=null)< shuttle=shuttle.right; while (shuttle.left!=null) shuttle=shuttle.left; fromright=false; >int counter=0; do < while (true)< if (!fromright && ++counter==steps) return shuttle; if (!fromright && shuttle.right!=null)< shuttle=shuttle.right; break; >holder=shuttle; shuttle=shuttle.parent; fromright=(holder==shuttle.right); > while (shuttle.left!=null) shuttle=shuttle.left; >while (true); > Примечание: В общем случае также требуется предотвратить возможность попытки выхода за пределы дерева (подняться выше корневого узла).
Источник
Обход бинарного дерева в обратном порядке
Для заданного бинарного дерева выведите его узлы уровень за уровнем в обратном порядке, т. е. сначала выведите все узлы, присутствующие на последнем уровне, затем узлы предпоследнего уровня и т. д. Выведите узлы любого уровня слева направо.
Например, обратная обход порядка уровней для следующего дерева 4, 5, 6, 7, 2, 3, 1 :
Простым решением было бы напечатать все узлы уровня h сначала, потом уровень h-1 , до уровня 1, где h это высота дерева. Мы можем вывести все узлы, присутствующие на уровне, изменив обход предварительного заказа на дереве. Временная сложность этого решения O(n 2 ) , куда n это общее количество узлов в бинарном дереве.
Мы можем уменьшить временную сложность до O(n) с использованием дополнительного пространства. Ниже приведен псевдокод для простого queueобход в обратном порядке, требующий пространства, пропорционального максимальному количеству узлов на заданной глубине. Она может составлять до половины от общего количества узлов.
levelorder(root)
q —> empty queue
s —> empty stack
q.enqueue(root)
while (not q.isEmpty())
node —> q.dequeue()
s.push(node)
if (node.right <> null)
q.enqueue(node.right)
if (node.left <> null)
q.enqueue(node.left)
while (not s.isEmpty())
node —> s.pop()
print(node)
Алгоритм может быть реализован следующим образом на C++, Java и Python:
Источник