Алгоритм обхода дерева 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++, обратитесь к этому руководству.

   Источник

   Обход дерева в несколько потоков

   Всем привет, хочу поделиться с общественностью некоторым объемом информации, который как мне показалось трудно найти в интернете.

   

   Рис.1 Пример дерева.

   Итак, зачем вообще может понадобится обходить дерево в несколько потоков? В моем случае, это была необходимость поиска файлов на диске. Понятно, что физически диск работает в один поток, но тем не менее, многопоточный поиск файлов может дать ускорение, в случае, когда один-единственный поток ищет файл в многоуровневой иерархии, а искомый файл лежит в соседней папке с одним уровнем. Также доказательством актуальности применения многопоточного поиска служит его реализации во многих успешных коммерческих продуктах. Не исключаю, что возможны и другие варианты применения алгоритма, пишите в комментариях.

   Для начала предлагаю рассмотреть анимацию:

   Что здесь происходит? Вся суть алгоритма сводится к тому, что:

   1. Первый поток обходит дерево начиная с корня на всю глубину по «крайне левому» пути, т.е. всегда при перемещении вглубь поворачивает налево или другими словами всегда выбирает последний дочерний узел.
   2. Параллельно первый поток собирает все пропущенные дочерние узлы и отправляет их в очередь (либо в стек) где их забирает другой поток, очередь или стек должны реализовывать многопоточный подход, и алгоритм повторяется, подставляя на место корня только-что взятый узел.

   Программная реализация на Java

   Привожу пример кода, который может кому-то пригодится, я его долго искал, но так и не нашел:

   import java.io.File; import java.util.concurrent.BlockingQueue; import java.util.concurrent.Executor; import java.util.concurrent.Executors; import java.util.concurrent.LinkedBlockingDeque; public class MultiThreadTreeWalker extends Thread < private static BlockingQueuenodesToReview = new LinkedBlockingDeque<>(); private File f; public MultiThreadTreeWalker(File f) < this.f = f; >public MultiThreadTreeWalker() < >public static void main(String[] args) < Executor ex = Executors.newFixedThreadPool(2); MultiThreadTreeWalker mw = new MultiThreadTreeWalker(new File("C:\\")); mw.run(); for (int i = 0;i<2;i++) < ex.execute(new MultiThreadTreeWalker()); >> @Override public void run() < if (f != null) < //только для первого потока reviewFileSystem(f); >else < try < while (true) < f = nodesToReview.take(); reviewFileSystem(f); >> catch (InterruptedException e) < e.printStackTrace(); >> > void reviewFileSystem(File f) < if (f == null) < return; >if (f.isFile()) < //завершение обхода (+дополнительная логика) System.out.println("Файл " + f.getName() + " найден потоком " + Thread.currentThread()); return; >File[] files = f.listFiles(); if (files.length != 0) < for (int i = 0; i < files.length - 1; i++) < nodesToReview.add(files[i]); //добавление файлов всех кроме последнего >//последний дочерний узел используется для перехода дальше File last = files[files.length - 1]; reviewFileSystem(last); > > > 

   Заключение

   Как видно многопоточность в Java можно реализовать достаточно просто посредством BlockingQueue, структуры данных реализующей доступ нескольких потоков к хранимым данных.

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

   P.S. также советую всем прочитать комментарии (там много интересного)

   Ссылка на GitHub. Там же рядом лежит поисковик на JavaFX, если кто-то захочет потестить, то я только буду рад.

   Источник

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

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

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

   Источник

   Читайте также:  Там где пилят деревья