из массива в дерево

[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

Буду рад любым советам, в т.ч. ссылкам, исходникам (паскаль, с, джава)

[Kolinus]

Книга Вирта "Алгоритмы и структуры данных" если не ошибаюсь в названии там есть все
только у тебя не совсем дерево если честно. - у дерева корень ОДИН

[BAHTY3]

Не обязательно... дерево есть гарф, а граф может быть несвязным...

[evgeny_d]

Не обязательно... дерево есть гарф, а граф может быть несвязным...

Ага. Окунь есть рыба, а рыба может быть селедкой.

Ежели мне не изменяет память, то дерево - это связный граф без циклов.

У слову в теории графов есть специальный термин: лес - для графа состоящего из нескольких связных подграфов - деревьев, который в свою очередь деревом не является.

[swentorog]

у меня есть ОДИН корень. данный массив "принадлежит" этому корню.

[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 не сохраняет порядка.