VPF::Примеры двух алгоритмов на java - Форум программистов

Atum

Дата 6.11.2012, 23:48 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 265
Регистрация: 3.10.2008

Репутация: нет
Всего: нет

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

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

List<Node> getChildren();
}

interface Tree {

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

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

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

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

Mirkes

Дата 7.11.2012, 06:31 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 586
Регистрация: 18.8.2011
Где: Красноярск

Репутация: 7
Всего: 17

С рекурсией алгоритм совершенно простой.
поскольку не понял, что значит получить, решил складывать в коллекцию.
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;
}

--------------------

Mirkes

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »