Страница 1 из 1
из массива в дерево
Добавлено: 06 дек 2005, 10:37
swentorog
Добрый день!
может кто сталкивался с проблемой: нужно из массива сформировать дерево. Например из
Код: Выделить всё
1|a|itm01
1|a|itm02
1|a|itm03
1|b|itm04
1|b|itm05
1|c|itm06
2|a|itm07
2|b|itm08
2|c|itm09
3|b|itm10
3|b|itm11
сформировать дерево
Код: Выделить всё
1
a
itm01
itm02
itm03
b
itm04
itm05
c
itm06
2
a
itm07
b
itm08
c
itm09
3
b
itm10
itm11
Буду рад любым советам, в т.ч. ссылкам, исходникам (паскаль, с, джава)
Добавлено: 06 дек 2005, 14:27
Kolinus
Книга Вирта "Алгоритмы и структуры данных" если не ошибаюсь в названии
там есть все
только у тебя не совсем дерево если честно. - у дерева корень ОДИН
Добавлено: 07 дек 2005, 02:42
BAHTY3
Не обязательно... дерево есть гарф, а граф может быть несвязным...
Добавлено: 07 дек 2005, 06:44
evgeny_d
Не обязательно... дерево есть гарф, а граф может быть несвязным...
Ага. Окунь есть рыба, а рыба может быть селедкой.
Ежели мне не изменяет память, то дерево - это связный граф без циклов.
У слову в теории графов есть специальный термин:
лес - для графа состоящего из нескольких
связных подграфов - деревьев, который в свою очередь деревом не является.
Добавлено: 07 дек 2005, 09:58
swentorog
у меня есть ОДИН корень. данный массив "принадлежит" этому корню.
Добавлено: 11 дек 2005, 19:40
Oscar
Java 1.5
Код: Выделить всё
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Hashtable;
public class Test {
public static void main(String[] args) {
ArrayList<String> array = new ArrayList<String>();
array.add("1|a|itm01");
array.add("1|a|itm02");
array.add("1|a|itm03");
array.add("1|b|itm04");
array.add("1|b|itm05");
array.add("1|c|itm06");
array.add("2|a|itm07");
array.add("2|b|itm08");
array.add("2|c|itm09");
array.add("3|b|itm10");
array.add("3|b|itm11");
ArrayList<Hashtable<Character, ArrayList<String>>> tree = new ArrayList<Hashtable<Character, ArrayList<String>>>();
tree.add(0, new Hashtable<Character, ArrayList<String>>());
for(int i = 0; i < array.size(); i++) {
String[] one = array.get(i).split("\\|");
int first = Integer.parseInt(one[0]);
Character second = one[1].charAt(0);
String third = one[2];
Hashtable<Character, ArrayList<String>> secondLevel = null;
if (first >= tree.size()) {
secondLevel = new Hashtable<Character, ArrayList<String>>();
tree.add(first, secondLevel);
}
secondLevel = tree.get(first);
if (secondLevel == null)
secondLevel = new Hashtable<Character, ArrayList<String>>();
ArrayList<String> thirdLevel = secondLevel.get(second);
if (thirdLevel == null)
thirdLevel = new ArrayList<String>();
thirdLevel.add(third);
secondLevel.put(second, thirdLevel);
tree.set(first, secondLevel);
}
for(int first = 1; first < tree.size(); first++) {
System.out.println(first);
Hashtable<Character, ArrayList<String>> firstLevel = tree.get(first);
Enumeration<Character> secondLevel = firstLevel.keys();
while(secondLevel.hasMoreElements()) {
Character second = secondLevel.nextElement();
System.out.println("\t" + second);
ArrayList<String> thirdLevel = firstLevel.get(second);
for(int i = 0; i < thirdLevel.size(); i ++) {
String third = thirdLevel.get(i);
System.out.println("\t\t" + third);
}
}
}
}
}
Hashtable не сохраняет порядка.