Java обход дерева без рекурсии

Поиск в глубину в Java

В этом руководстве мы рассмотрим поиск в глубину в Java.

Поиск в глубину (DFS) — это алгоритм обхода, используемый как для структур данных Tree, так и для Graph . Поиск в глубину углубляется в каждую ветвь, прежде чем переходить к изучению другой ветви .

В следующих разделах мы сначала рассмотрим реализацию дерева, а затем графа.

Чтобы узнать, как реализовать эти структуры в Java, ознакомьтесь с нашими предыдущими руководствами по двоичному дереву и графику .

2. Поиск в глубину дерева​

Существует три разных порядка обхода дерева с помощью DFS:

2.1. Обход предзаказа​

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

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

 public void traversePreOrder(Node node)    if (node != null)    visit(node.value);   traversePreOrder(node.left);   traversePreOrder(node.right);   >   > 

Мы также можем реализовать предварительный обход без рекурсии.

Чтобы реализовать итеративный обход предварительного заказа, нам понадобится Stack , и мы выполним следующие шаги:

• Вставьте root в наш стек
• Пока стек не пуст
• Вытолкнуть текущий узел
• Посетить текущий узел
• Нажмите правый дочерний элемент, затем левый дочерний элемент, чтобы сложить

 public void traversePreOrderWithoutRecursion()    StackNode> stack = new StackNode>();   Node current = root;   stack.push(root);   while(!stack.isEmpty())    current = stack.pop();   visit(current.value);    if(current.right != null)    stack.push(current.right);   >   if(current.left != null)    stack.push(current.left);   >   >   > 

2.2. Неупорядоченный обход​

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

Неупорядоченный обход для бинарного дерева поиска означает обход узлов в порядке возрастания их значений.

Мы можем просто реализовать неупорядоченный обход с помощью рекурсии:

 public void traverseInOrder(Node node)    if (node != null)    traverseInOrder(node.left);   visit(node.value);   traverseInOrder(node.right);   >   > 

Мы также можем реализовать неупорядоченный обход без рекурсии :

• Инициализировать текущий узел с помощью root
• Пока текущий не равен нулю или стек не пуст
• Продолжайте помещать левый дочерний элемент в стек, пока мы не достигнем самого левого дочернего элемента текущего узла.
• Поп и посетите самый левый узел из стека
• Установите текущий правый дочерний элемент выдвинутого узла

 public void traverseInOrderWithoutRecursion()    Stack stack = new Stack>();   Node current = root;    while (current != null || !stack.isEmpty())    while (current != null)    stack.push(current);   current = current.left;   >    Node top = stack.pop();   visit(top.value);   current = top.right;   >   > 

2.3. Почтовый обход​

Наконец, при обходе в обратном порядке мы проходим левое и правое поддерево до того, как проходим корень .

Мы можем следовать нашему предыдущему рекурсивному решению :

 public void traversePostOrder(Node node)    if (node != null)    traversePostOrder(node.left);   traversePostOrder(node.right);   visit(node.value);   >   > 

Или мы также можем реализовать обратный обход без рекурсии :

• Поместить корневой узел в стек «
• Пока стек не пуст
• Проверяем, прошли ли мы уже левое и правое поддерево
• Если нет, то поместите правый дочерний элемент и левый дочерний элемент в стек

 public void traversePostOrderWithoutRecursion()    StackNode> stack = new StackNode>();   Node prev = root;   Node current = root;   stack.push(root);    while (!stack.isEmpty())    current = stack.peek();   boolean hasChild = (current.left != null || current.right != null);   boolean isPrevLastChild = (prev == current.right ||   (prev == current.left && current.right == null));    if (!hasChild || isPrevLastChild)    current = stack.pop();   visit(current.value);   prev = current;   > else    if (current.right != null)    stack.push(current.right);   >   if (current.left != null)    stack.push(current.left);   >   >   >   > 

3. Графический поиск в глубину​

Основное различие между графами и деревьями состоит в том, что графы могут содержать циклы .

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

Мы увидим две реализации DFS графа, с рекурсией и без рекурсии.

3.1. График DFS с рекурсией​

Во-первых, давайте начнем с рекурсии:

• Мы начнем с заданного узла
• Отметить текущий узел как посещенный
• Посетить текущий узел
• Обход непосещенных смежных вершин

 public void dfs(int start)    boolean[] isVisited = new boolean[adjVertices.size()];   dfsRecursive(start, isVisited);   >    private void dfsRecursive(int current, boolean[] isVisited)    isVisited[current] = true;   visit(current);   for (int dest : adjVertices.get(current))    if (!isVisited[dest])   dfsRecursive(dest, isVisited);   >   > 

3.2. График DFS без рекурсии​

Мы также можем реализовать граф DFS без рекурсии. Мы просто будем использовать стек :

• Мы начнем с заданного узла
• Поместить начальный узел в стек
• Пока стек не пуст
• Отметить текущий узел как посещенный
• Посетить текущий узел
• Втолкнуть непосещенные соседние вершины

 public void dfsWithoutRecursion(int start)    StackInteger> stack = new StackInteger>();   boolean[] isVisited = new boolean[adjVertices.size()];   stack.push(start);   while (!stack.isEmpty())    int current = stack.pop();   if(!isVisited[current])   isVisited[current] = true;   visit(current);   for (int dest : adjVertices.get(current))    if (!isVisited[dest])   stack.push(dest);   >   >   > 

3.4. Топологическая сортировка​

Существует множество приложений для поиска по графу в глубину. Одним из известных приложений для DFS является топологическая сортировка.

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

Чтобы получить топологическую сортировку, нам понадобится простое дополнение к DFS, которую мы только что реализовали:

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

 public ListInteger> topologicalSort(int start)    LinkedListInteger> result = new LinkedListInteger>();   boolean[] isVisited = new boolean[adjVertices.size()];   topologicalSortRecursive(start, isVisited, result);   return result;   >    private void topologicalSortRecursive(int current, boolean[] isVisited, LinkedListInteger> result)    isVisited[current] = true;   for (int dest : adjVertices.get(current))    if (!isVisited[dest])   topologicalSortRecursive(dest, isVisited, result);   >   result.addFirst(current);   > 

4. Вывод​

В этой статье мы обсудили поиск в глубину как для структур данных Tree, так и для Graph.

Полный исходный код доступен на GitHub .

Источник

Как обойти дерево файловой системы БЕЗ рекурсии

Подскажите как обойти дерево файловой системы на заданную глубину БЕЗ рекурсии, и найти элементы которые в своем имени содержат определенную маску.
Предложили вариант брать два списка — текущего и следующего уровня. Идти по текущему уровню и все дочерние класть в следующий. После того как прошли — следующий уровень делается текущим. И так до достижения нужной глубины.
По сути у меня сейчас в list список текущего, в folderlist список следующего уровня, но как обойти все дерево на глубину, допустим 2, все равно сообразить не могу

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

import java.io.*; public class TestPE { // фильтр static class MyFilter implements FilenameFilter { private String mask; public MyFilter(String mask) { this.mask = mask; } public boolean accept(File dir, String name) { File f = new File (name); if (f.getName().contains(mask)){ return true; } else {return false;} } } public static void main (String args []){ String Path = args[0]; //Integer depth_temp =Integer.valueOf(args[1]); //int depth = depth_temp.intValue(); String mask = args[1]; File rootPath = new File (Path); //Ecли rootPath директория, то получаем список ее файлов. if (rootPath.isDirectory()){ File [] list = rootPath.listFiles(new MyFilter(mask)); /*Для каждого файла папки rootPath, проверяем не является ли она папкой, *если является получаем список файлов в folderlist, и выводим его */ for (int i=0; ilist.length; i++){ if (list[i].isDirectory()){ File [] folderlist = list[i].listFiles(new MyFilter(mask)); for (int j=0; jfolderlist.length; j++){ System.out.println(folderlist[j]); } } System.out.println(list[i]); } } } }

Источник

Как обойти дерево файловой системы БЕЗ рекурсии

Подскажите как обойти дерево файловой системы на заданную глубину БЕЗ рекурсии, и найти элементы которые в своем имени содержат определенную маску.
Предложили вариант брать два списка — текущего и следующего уровня. Идти по текущему уровню и все дочерние класть в следующий. После того как прошли — следующий уровень делается текущим. И так до достижения нужной глубины.
По сути у меня сейчас в list список текущего, в folderlist список следующего уровня, но как обойти все дерево на глубину, допустим 2, все равно сообразить не могу

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

import java.io.*; public class TestPE { // фильтр static class MyFilter implements FilenameFilter { private String mask; public MyFilter(String mask) { this.mask = mask; } public boolean accept(File dir, String name) { File f = new File (name); if (f.getName().contains(mask)){ return true; } else {return false;} } } public static void main (String args []){ String Path = args[0]; //Integer depth_temp =Integer.valueOf(args[1]); //int depth = depth_temp.intValue(); String mask = args[1]; File rootPath = new File (Path); //Ecли rootPath директория, то получаем список ее файлов. if (rootPath.isDirectory()){ File [] list = rootPath.listFiles(new MyFilter(mask)); /*Для каждого файла папки rootPath, проверяем не является ли она папкой, *если является получаем список файлов в folderlist, и выводим его */ for (int i=0; ilist.length; i++){ if (list[i].isDirectory()){ File [] folderlist = list[i].listFiles(new MyFilter(mask)); for (int j=0; jfolderlist.length; j++){ System.out.println(folderlist[j]); } } System.out.println(list[i]); } } } }

Источник