Алгоритм построения дерева иерархии выглядит следующим образом.
Вход:
hList – линейный массив значений иерархии предварительно отсортированный по полю Code. Count – число элементов массива hList.
Выход:
hTree – двумерный массив, представляющий дерево иерархии. Внутри hTree хранятся ссылки на элементы hList. LevelCount – количество уровней иерархии и соответственно ширина массива hTree. Cnt – число узлов на каждом из уровней дерева hTree.
Часть 1. Заполнение поля Level для элементов иерархии, получение количества уровней. | ||
1 | LevelCount ← 0 | // количество уровней равно 0 |
2 | for i ← 0 to Count - 1 do | // обходятся все элементы |
begin | // списка значений иерархии | |
3 | idx ← i | // текущий элемент равен i |
4 | if hList[idx].Level < 0 then | // если узел не обработан, то |
begin | // обрабатываем | |
5 | if hList [idx].Parent < hList [idx].Code | // строим диапазон поиска |
then begin | // предка. Если Parent < Code, то | |
6 | is ← 0 | // диапазон поиска от 0 |
7 | ie ← Index – 1 | // до ТекущийЭлемент – 1 |
end else | ||
8 | if hList [idx].Parent > hList [idx].Code | // в обратном случае |
then begin | // диапазон поиска от | |
9 | is ← idx + 1 | // текущего элемента + 1 |
10 | ie ← Count – 1 | // до последнего элемента |
end else | // иначе элемент ссылается на | |
11 | return Error | // себя, и следовательно ошибка |
12 | Parent ← Find(hList [idx].Parent, is, ie) | // ищем предка в диапазоне |
13 | if (Parent = -1) or (hList [Parent].Level >= 0) | // если предок является корнем или уже обработан, то |
then begin | // выполняем след. действия: | |
14 | if Parent = - 1 then | // если предок корень, то |
15 | hList [idx].Level ← 0 else | // устанавливаем уровень в 0 |
16 | hList [idx].Level ← hList [Parent].Level + 1 | // иначе уровень равен уровню предка + 1 |
17 | LevelCount ← MAX(hList [idx].Level + 1, LevelCount) | // обновляем максимальное число уровней |
18 | hList [idx].Parent ← Parent | // присваиваем значение предка |
end else | // иначе если узел еще не | |
begin | // обработан, то | |
19 | Povtor2: hList [Parent].FirstChildIndex ← idx | // ставим метку и сохраняем значение текущего индекса в неиспользуемом пока поле |
20 | idx ← Parent | // текущий индекс выставляем по значению предка |
21 | if hList[idx].Parent < hList[idx].Code | // как в пунктах 5-11 |
then begin | // строим диапазон поиска | |
22 | is ← 0 | // предка |
23 | ie ← idx – 1 | |
24 | end else | |
25 | if hList[idx].Parent > hList[idx].Code | |
then begin | ||
26 | is ← idx + 1 | |
27 | ie ← Count – 1 | |
end else | ||
28 | return Error | |
29 | Parent ← Find(hList[idx].Parent, is, ie) | // ищем предка в построенном диапазоне |
Povtor: | // ставим метку | |
30 | if (Parent = -1) or (hList[Parent].Level >= 0) | // если этот предок обработан |
then begin | // то повторяем пункты 14-18 | |
31 | if Parent = -1 then | |
32 | hList[idx].Level ← 0 else | |
33 | hList[idx].Level ← hList[Parent].Level + 1 | |
34 | LevelCount ← MAX(hList [idx].Level + 1, LevelCount) | |
35 | hList [idx].Parent ← Parent | |
36 | if hList[idx].FirstChildIndex = -1 | // проверяем поле – есть нет |
37 | then continue | // сохранного значения, то прекращаем обработку текущего элемента |
38 | Parent ← idx | // иначе сохраняем в Parent текущее значение |
39 | idx ← hList[Parent].FirstChildIndex | // восстанавливаем текущее значение из сохраненного |
40 | hList[Parent].FirstChildIndex ← -1 | // сбрасываем сохраненное значение |
41 | goto Povtor | // и возвращаемся к пункту 30 |
end else | // если и этот предок не был обработан и не являлся корнем | |
42 | goto Povtor2 | // то возвращаемся в пункт 19 |
end | ||
end else | // если исходный узел уже был | |
43 | LevelCount ← MAX(hList [idx].Level + 1, LevelCount) | // обработан, то обновляем максимальное число уровней |
end | ||
Часть 2. Заполнение структуры дерева | ||
44 | for i ← 0 to count - 1 do | // обходятся все элементы |
begin | // списка значений иерархии | |
43 | cnt[hList[i].Level] ← cnt[hList[i].Level] + 1 | // увеличивается количество элементов на уровне |
44 | hTree[hList[i].Level][cnt[hList[i].Level] – 1] ← hList[i] | // узлу дерева присваивается ссылка на запись в списке |
end | ||
45 | for i ← 0 to LevelCount - 1 do | // восстановление Parent по |
begin | // значению из базы | |
46 | if i = 0 then | // для всех элементов нулевого |
begin | // уровня значения Parent | |
47 | for j ← 0 to cnt[i] - 1 do | // приравниваются к -1 |
48 | hTree[i][j].Parent ← -1 | |
end else | // для других уровней | |
49 | for j ← 0 to cnt[i] - 1 do | // значение получается из |
50 | hTree[i][j].Parent ← hList[hTree[i][j].Parent].LevelIndex | // заранее сохраненной в поле LevelIndex информации |
51 | SortLevel(i) | // внутри уровня i все элементы сортируются в алфавитном порядке |
52 | for j ← 0 to cnt[i] - 1 do | // внутри уровня обходятся все |
begin | // элементы | |
53 | hTree[i][j].LevelIndex ← j | // устанавливается значение индекса на уровне |
54 | if (i <> 0) and (if HierTree[i - 1] [HierTree[i][j].Parent].FirstChildIndex = -1) then | // для не нулевого уровня и еще не обработанных элементов |
55 | hTree[i - 1][hTree[i][j].Parent]. FirstChildIndex ← j | // устанавливается ссылка на первого потомка |
end | ||
end |
Сложность алгоритма
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 |
