|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Grandalf Gray 2:5020/400 23 Feb 2002 05:05:10
To : ‘ҐаЈҐ© „ў®ап楢
Subject : Re: Построение дерева
--------------------------------------------------------------------------------
> У меня есть линейный одномерный массив с элементами типа <(Index),
(Parent),
> ...>
> Index - уникальные значения, а Parent - значение Index элемента-предка
> Hужен быстрый алгоритм формирования дерева из этих элементов.
> Может кто пнет в нужном направлении?
> --
> С уважением, Сергей Дворянцев.
1. сортируешь массив по parent(по возрастанию)
2. берешь первый эл-т массива(у него parent=index) это будет твой root
3. берешь следующий эл-т ищешь в дереве родительский узел(index которого
равен parent данного эл-та), добавляешь к найденному эл-ту
потомка(рассматриваемый эл-т)
4. переходишь к 3 пока не дойдешь до конца массива...
Описанный алгоритм позволяет на основе твоего массива построить "списочную
структуру" которая и будет искомым представлением твоего дерева. Я в
качестве
этой структуры использовал бинарное дерево, это наиболее удобный способ,
хотя существует множество способов представления дерева в памяти... в
принципе твой массив это уже есть представление дерева в памяти и ним можно
ничего особо не делать, а просто написать функции для работы с ним...(если
тебе не нужно будет к нему добавлять произвольное число вершин, то оставляй
массив, в противном случае... нужно использовать другое представление...)
--- ifmail v.2.15dev5
* Origin: Golden Telecom (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
