Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > Примеры двух алгоритмов на java

Автор: Atum 6.11.2012, 23:48

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

есть интерфейс interface Node{

List<Node> getChildren();
}

interface Tree {

List<Node> getAllleafs(final Node rootNode);
}

Нужно получить все листья дерева (лист это нода у которой нет больше листьев)

что то сложно с логикой в 1 час ночи.

помогите составить два примера алгоритмов.

Автор: Mirkes 7.11.2012, 06:31

С рекурсией алгоритм совершенно простой.
поскольку не понял, что значит получить, решил складывать в коллекцию.
ghtlgjkfuf.
Одна рекурсивная процедура findLeaves, точнее метод класса Node

Код


  public ArrayList<Node> findLeaves(){
      ArrayList<Node> result = new ArrayList<Node>();
      List<Node> child = getChildren();
      if (child.size()==0){
         //root is leaf
         result.add(this);
      }else{
        // Add child's lists
        for (Node node : child)
          result.addAll(node.findLeaves());
      }
      return result;
  }

Код писал прямо здесь. Так что не проверял.
А вот с нерекурсивным поиском по дереву сложнее. А зачем это надо? Для зачета? В принципе это можно сделать с помощью стека, куда складывать еще не проверенных детишек.
Писать не буду, а идея такова.
Создаем массив стека (Например ArrayList, Vector и т.д.)
Кладем туда корневой узел.
Запускаем цикл пока ...
Понял, что проще написать в коде

Код


public ArrayList<Node> getAllleafs(final Node rootNode){
   ArrayList<Node> stack = new ArrayList<Node>(); // стек тпа FIFO первым пришел, первым ушел
   ArrayList<Node> result = new ArrayList<Node>();
   stack.add(rootNode); // Кладем корневой элемент
   while (stack.size()>0){
      Node node = stack.get(0); // Этот узел будем обрабатывать
      stack.remove(0); // удаляем его из стека
      List<Node> child = node.getChildren(); // Получаем детей нашего клиента
      if (child.size()==0){
         //node is leaf
         result.add(node);
      }else{
        // Put child's to stack
        stack.addAll(child);
      }
   }
   return result;
}