VPF::Вывод деревьев - Форум программистов

admin82

Дата 3.9.2007, 23:07 (ссылка)

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

Загрузка ...

Шустрый

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

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

Всем добрый денек (вечер). Такая вот задачка. Есть куча равноправных объектов. Пусть это люди. Каждый человек может быть в подчинении у другого, и может сам иметь подчиненных. Т.е. у человека есть поле "boss". Это поле может быть пусто, либо там может быть имя другого человека, и тогда этот другой человек -- его хозяин. Если человек не имеет босса, но является боссом у кого-то другого, то он, соответственно, будет корнем дерева. Если человек не имеет босса и не для кого не является боссом, то он не учитывается, т.е. ни в какое дерево не попадает.
Надо вывести все деревья по порядку (это будет jsp, но не важно). Проблема в том, что глубина

чел(root)->чел->чел->чел->чел->...чел->чел (без подчиненных) не ограничена. Естественно, на каждом этапе у человека может быть несколько подчиненных, это просто схема такая корявая. Ваши мнения, господа?

niasilil

Дата 4.9.2007, 01:25 (ссылка)

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

Загрузка ...

Опытный

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

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

Рекурсивный обход дерева прямо по учебнику. Высота дерева не имеет значения, потому что проблемы с памятью начнутся значительно раньше проблем со стеком. Стек в java большой, 5 тысяч элементов, уж не знаю меняется ли этот параметр значительно от машины к машине, но дерево подчиненных такого размера представить не могу.
В некоторых случаях особенно больших деревьев можно нерекурсно обходить, но здесь это неважно. Если рекурсия будет медленно работать, то будешь думать о нерекурсивных обходах, но пока рано.
Примеры обхода дерева, например, находятся в Sedgewick - Algorithms In Java, 3Rd Edition.

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

SCJP 5.0, SCJD

nornad

Дата 4.9.2007, 02:02 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1079
Регистрация: 16.2.2007
Где: в Караганде

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

admin82, как я понял, у тебя нет построенного дерева, а есть массив объектов, которые являются узлами непостроенного дерева.
В этом случае два варианта:
а) построение дерева и обход его (требует дополнительную память хотя бы на минимальные болванки со ссылками на объекты)
б) сортировка массива по хитрому алгоритму, который будет учитывать структуру
Во втором случае алгоритм примерно следующий. Берём элемент и смотрим на его босса. Если босса не было - добавляем. Если этот босс уже есть в результате, то узнаём его индекс (это можно сделать за счёт хранения индексов в мапе по боссам и хранения массива боссов по индексам; добавляем новый элемент в массив - перебираем мапу и корректируем индексы после него). Зная индекс, мы пихаем элемент сразу после его босса.

Алгоритм, естественно, не очень умный и оптимальный, но хоть что-то для начала.

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

Три достоинства программиста: Леность, Нетерпение и Гордость
Ларри Уолл

niasilil

Дата 4.9.2007, 03:44 (ссылка)

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

Загрузка ...

Опытный

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

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

А, точно, в поле объекта нет ссылки на работников.
1) Сделать ArrayList новых объекты со ссылками на самого работнка, их босса и лист всех его подчиненных. Простым перебором, взять человека, добавить его в список своего босса. и т.д. время O(N). Дополнительно здесь создать boolean [] isPrinted использовать как флаг, где индекс этого массива будет соответствовать индексу
Дальше
2) Берем любой объект,
3) находим его главного босса (это корень дерева). время - высота дерева, мелочь, в худшем маловероятном случае O(N).
4) рекурсивно обходим это дерево, используя созданные в первом этапе объекты со ссылками на ветви. Распечатываем если объектов больше чем один. время O(N)
5) Берем любой другой объект из оставшихся (первый false в массиве isPrinted), делаем пункт 2. время O(N)*k где k-количество деревьев (это опять же худшем маловероятном случае, в реальности будет немного.).
повторяем до тех пор пока не кончатся объекты.

Сортировать не надо.

Это сообщение отредактировал(а) niasilil - 4.9.2007, 04:05

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

SCJP 5.0, SCJD

admin82

Дата 4.9.2007, 10:07 (ссылка)

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

Загрузка ...

Шустрый

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

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

Ну это же надо так запутанно написать. Поясни, пожалуйста

Добавлено через 4 минуты и 31 секунду
Как мне построить дерево, имея массив описанных объектов (ArrayList)

niasilil

Дата 5.9.2007, 00:33 (ссылка)

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

Загрузка ...

Опытный

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

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

Что то типа этого. Вроде работает. Только осталось добавить флаги на проверку и применить процедуру к первому же необработанному элементу.

Код

import java.awt.BorderLayout;
import java.awt.Container;
import java.util.Hashtable;
import java.util.Iterator;

import javax.swing.JFrame;
import javax.swing.JScrollPane;
import javax.swing.JTree;
import javax.swing.tree.DefaultMutableTreeNode;

public class All extends JFrame {
    /**
     *
     */
    private static final long serialVersionUID = 6124092094567417340L;

    // vse kogo imeem
    Hashtable<String, Employer> employer = new Hashtable<String, Employer>(); // no
                                                                                // nulls
                                                                                // allowed

    // novyj
    Hashtable<String, NewEmployer> newEmployer = new Hashtable<String, NewEmployer>();

    All() {
        Employer e1 = new Employer();
        e1.setName("Vasya");
        Employer e2 = new Employer();
        e2.setName("Katya");
        e2.setBoss(e1);
        Employer e3 = new Employer();
        e3.setName("Jake");
        e3.setBoss(e1);
        Employer e4 = new Employer();
        e4.setName("Blake");
        e4.setBoss(e3);
        Employer e5 = new Employer();
        e5.setName("Lena");
        e5.setBoss(e3);

        employer.put(e1.getName(), e1);
        employer.put(e2.getName(), e2);
        employer.put(e3.getName(), e3);
        employer.put(e4.getName(), e4);
        employer.put(e5.getName(), e5);

        NewEmployer ne, neB;

        Iterator<String> iterator = employer.keySet().iterator();
        while (iterator.hasNext()) {
            ne = new NewEmployer(employer.get(iterator.next()));
            newEmployer.put(ne.getName(), ne);
        }

        // dobavlyaem sebya kak podchinennogo k bossu
        iterator = newEmployer.keySet().iterator();
        while (iterator.hasNext()) {
            ne = newEmployer.get(iterator.next());
            if (ne.boss != null) {
                neB = newEmployer.get(ne.boss.getName());
                neB.addSubordinate(ne.getEmployer());
            }
        }

        // risuem
        Container content = getContentPane();
        DefaultMutableTreeNode root = process(findTop(newEmployer.get("Katya")));
        JTree tree = new JTree(root);
        content.add(new JScrollPane(tree), BorderLayout.CENTER);
        setSize(275, 300);
        setVisible(true);
    }

    public NewEmployer findTop(NewEmployer e) {
        if (e.boss == null) { // bossa net, znachit eto boss
            return e;
        } else { // boss est', ischem bossa
            return findTop(newEmployer.get(e.boss.getName()));
        }
    }

    private DefaultMutableTreeNode process(NewEmployer top) {
        DefaultMutableTreeNode node = new DefaultMutableTreeNode(top);
        DefaultMutableTreeNode child = new DefaultMutableTreeNode(top);

        Iterator<String> iterator = top.subordinate.keySet().iterator();
        while (iterator.hasNext()) {
            Employer e = top.subordinate.get(iterator.next());
            child = process(newEmployer.get(e.getName()));
            node.add(child);
        }

        return (node);
    }

    public static void main(String[] args) {
        All a = new All();
        a.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    }

}

class NewEmployer {
    Employer employer;

    Employer boss;

    Hashtable<String, Employer> subordinate = new Hashtable<String, Employer>();

    public NewEmployer(Employer employer) {
        this.employer = employer;
        boss = employer.getBoss();
    }

    public void addSubordinate(Employer employer) {
        subordinate.put(employer.getName(), employer);
    }

    public String getName() {
        return employer.getName();
    }

    public Employer getEmployer() {
        return employer;
    }

    @Override
    public String toString() {
        return employer.getName();
    }
}

// eto dano, tut kucha polej kotorye menyat' nel'zya
class Employer {
    private Employer boss;

    private String name = "Vasya"; // pust' vse vasi dlya prostoty

    public Employer getBoss() {
        return boss;
    }

    public void setName(String name) {
        this.name = name;
    }

    public void setBoss(Employer boss) {
        this.boss = boss;
    }

    public String getName() {
        return name;
    }
}

Это сообщение отредактировал(а) niasilil - 5.9.2007, 15:53

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

SCJP 5.0, SCJD

niasilil

Дата 5.9.2007, 15:41 (ссылка)

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

Загрузка ...

Опытный

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

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

в методе findTop ошибочка была - поправил немного.

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

SCJP 5.0, SCJD

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