Страница 1 из 1
Нужна помощь с деревьями
Добавлено: 12 май 2005, 11:21
BelieveMe
Проблема в следующем. Я никак не могу разобраться с деревьями, причем не бинарными, а с неограниченным количеством детей. Никак не могу найти ни нормальной литературы на эту тему, ни хотя бы исходников. Поэтому просьба, если кто знает, где можно почитать на эту тему или, если у кого есть функции добавления, удаления, поиска и обхода - не поленитесь, дайте ссылки и запостите функции. Заранее спасибо.
Добавлено: 12 май 2005, 16:04
Romeo
Я использовал следующие структуры, когда работал с дерьвями с недетермированным количеством дуг:
Код: Выделить всё
struct CEdge;
struct CVertex;
struct CEdge
{
<..> some data
CVertex *pDest;
CEdge *pNext;
CEdge *pPrev;
};
struct CVertex
{
<..> some data
CEdge *pEdges;
CVertex *pNext;
CVertex *pPrev;
};
Таким образом задание дерева можно свести к обычному двунаправленному списку его вершин, причём к каждой вершине прикреплён двунаправленный список из дуг, исходящих их этой вершины. Такое представление удобно ещё и тем, что вершины дерева можно обходить не только от корня к листьям (рекурсивно), но и линейным циклом.
Очень советую: хорошие показатели производительности.