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

Поиск в ширину (BFS) и поиск в глубину (DFS) для двоичных деревьев в Java

Поиск в ширину и поиск в глубину — это два метода обхода графов и деревьев. В этом руководстве мы сосредоточимся в основном на обходах BFS и DFS в деревьях.

Что такое поиск в глубину (DFS)?

Алгоритм начинается с корневого узла, а затем исследует каждую ветвь перед возвратом. Он реализован с помощью стеков. Часто при написании кода мы используем стеки рекурсии для возврата. Используя рекурсию, мы можем воспользоваться тем фактом, что левое и правое поддеревья также являются деревьями и имеют одни и те же свойства.

Для двоичных деревьев существует три типа обхода DFS.

Что такое поиск в ширину (BFS)?

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

Для бинарных деревьев у нас есть обход порядка уровней, который следует за BFS.

Реализация BFS и DFS на Java

Пусть рассматриваемое дерево:

Структура класса TreeNode выглядит следующим образом:

1. Обход предварительного заказа

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

Алгоритм обхода предварительного заказа следующий:

1. Обход корня.
2. Вызов preorder() для левого поддерева.
3. Вызов preorder() для правого поддерева.

Обход предварительного заказа дерева выше:

Java-код выглядит следующим образом:

 static void preorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse root System.out.print(TreeNode.item + "->"); // Traverse left preorder(TreeNode.left); // Traverse right preorder(TreeNode.right); > 

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

Обход двоичного дерева по порядку сначала проходит через левое поддерево, затем корень и, наконец, правое поддерево.

Алгоритм обхода по порядку следующий:

1. Вызов inorder() для левого поддерева.
2. Обход корня.
3. Вызовите inorder() для правого поддерева.

Порядок обхода дерева выше:

Java-код выглядит следующим образом:

 static void inorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left inorder(TreeNode.left); // Traverse root System.out.print(TreeNode.item + "->"); // Traverse right inorder(TreeNode.right); > 

3. Обход после заказа

Обход двоичного дерева в обратном порядке сначала проходит по левому поддереву, затем по правому поддереву и, наконец, по корню.

Алгоритм обхода после заказа следующий:

1. Вызов postorder() для левого поддерева.
2. Вызов postorder() для правого поддерева.
3. Обход корня.

Пост-порядковый обход дерева выше:

Java-код выглядит следующим образом:

 static void postorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left postorder(TreeNode.left); // Traverse right postorder(TreeNode.right); // Traverse root System.out.print(TreeNode.item + "->"); > 

4. Обход по уровням

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

1. Инициализировать пустую очередь
2. Начните с установки temp от имени пользователя root
3. Запускать цикл до тех пор, пока очередь не станет пустой
   1. Печатать данные из временного файла.
   2. Поставить дочерние элементы temp в порядке слева и справа.
   3. Удалить узел из очереди и присвоить его значение переменной temp.

   Обход по порядку уровней дерева выше:

   Java-код выглядит следующим образом:

    static void printLevelOrder(TreeNode root) < Queuequeue = new LinkedList(); queue.add(root); while (!queue.isEmpty()) < TreeNode temp = queue.poll(); System.out.print(temp.data + " "); /*add left child to the queue */ if (temp.left != null) < queue.add(temp.left); >/*add right right child to the queue */ if (temp.right != null) < queue.add(temp.right); >> > 

   Полная реализация кода BFS и DFS на Java

   Полный код Java приведен ниже:

   package com.JournalDev; import java.util.LinkedList; import java.util.Queue; public class Main < static class TreeNode < int data; TreeNode left, right; public TreeNode(int key) < data = key; left = right = null; >> static void preorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse root System.out.print(TreeNode.data + " "); // Traverse left preorder(TreeNode.left); // Traverse right preorder(TreeNode.right); >static void inorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left inorder(TreeNode.left); // Traverse root System.out.print(TreeNode.data + " "); // Traverse right inorder(TreeNode.right); >static void postorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left postorder(TreeNode.left); // Traverse right postorder(TreeNode.right); // Traverse root System.out.print(TreeNode.data + " "); >static void printLevelOrder(TreeNode root) < Queuequeue = new LinkedList(); queue.add(root); while (!queue.isEmpty()) < TreeNode tempNode = queue.poll(); System.out.print(tempNode.data + " "); /*add left child to the queue */ if (tempNode.left != null) < queue.add(tempNode.left); >/*add right right child to the queue */ if (tempNode.right != null) < queue.add(tempNode.right); >> > public static void main(String args[]) < TreeNode root = new TreeNode(0); root.left = new TreeNode(1); root.right = new TreeNode(2); root.left.left = new TreeNode(3); root.left.right = new TreeNode(4); System.out.println("Inorder traversal"); inorder(root); System.out.println("\nPreorder traversal "); preorder(root); System.out.println("\nPostorder traversal"); postorder(root); System.out.println("\nLevelorder traversal"); printLevelOrder(root); >> 

   Output : Inorder traversal 3 1 4 0 2 Preorder traversal 0 1 3 4 2 Postorder traversal 3 4 1 2 0 Levelorder traversal 0 1 2 3 4 

   

   Заключение

   Это руководство было посвящено обходам BFS и DFS в двоичных деревьях. Чтобы получить реализацию DFS на C++, обратитесь к этому руководству.

   Источник

   Обход бинарных деревьев: рекурсия, итерации и указатель на родителя

   Основы о бинарных деревьях представлены, в том числе, здесь . Добавлю свои «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); >

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

   Источник