Хранение промежуточных данных при обходе дерева

[sashulyT]

Есть задача обойти ветки дерева, начальные данные хранятся в виде таблицы из двух колонок (узел1 - Узел2).
Вопрос заключается в том, как лучше хранить данные по каждой ветки в процессе обхода всего дерева. Так что б можно было оперативно получить информацию о узлах и их количестве.

Добавлено через 1 минуту
п.с. если что, реализовыватся будет на делфи.

[stcherny]

Посмотри:
http://algolist.ru/ds/walk.php

[minimus]

Цитата: Сообщение от sashulyT Есть задача обойти ветки дерева, начальные данные хранятся в виде таблицы из двух колонок (узел1 - Узел2). Вопрос заключается в том, как лучше хранить данные по каждой ветки в процессе обхода всего дерева. Так что б можно было оперативно получить информацию о узлах и их количестве.

Если ты имеешь дело с базой данных, то хранить промежуточные результаты нет необходимости. Вот реально работающий код для SQL Server (полный файл):

USE [MainBase]
GO
/****** Объект:  UserDefinedFunction [dbo].[EvalUnitsLevels]    Дата сценария: 23/11/2007 18:12:03 ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO

-- =============================================
-- Author:	      Константин Леонов
-- Create date: 23.11.2007
-- Description:  Сканирование входящих узлов на всех уровнях.
-- =============================================
CREATE FUNCTION [dbo].[EvalUnitsLevels](@Drawing [varchar](100), @Name [varchar](200))
RETURNS 
 @retUnits TABLE 
(
	Drawing [varchar](100), 
	[Name] [varchar](200),
    Usage int
)
AS
BEGIN
	WITH MasterUnits(Drawing, [Name], Usage) AS
    (
       SELECT lst.Drawing, lst.[Name], 1 as Usage
       FROM [Production].[List] lst
       WHERE (lst.Drawing = @Drawing) AND (lst.[Name] = @Name)
       UNION ALL
       SELECT pl.SlaveDrawing as Drawing, pl.SlaveName AS [Name], (pl.[Usage] * mu.Usage)
       FROM [Production].[ListSlave] pl
         INNER JOIN MasterUnits mu
         ON (pl.Drawing = mu.Drawing) AND (pl.[Name] = mu.[Name])
    )
    INSERT @retUnits
    SELECT Drawing, [Name], SUM(Usage) AS UUsage
    FROM MasterUnits
    GROUP BY Drawing, [Name]
    ORDER BY Drawing, [Name]
	RETURN 
END

Примечание:
1. Каждый узел задаётся парой полей ("Чертёжный номер", "Наименование"), соответственно связка - двумя парами полей. Надеюсь тебе не составит труда переделать под свою задачу;
2. Количество узлов - Usage. Понятно, что для корня Usage = 1;
3. Код работает для любого уровня вложенности узлов (если узел С входит в узел А, а также ещё один узел С входит в узел В, а узел В входит в узел А, то на выходе мы получим А=1, В=1, С=2);
4. Параметры функции (возвращающей таблицу) нужны для привязки к "родительскому" узлу через параметры SQL в Delphi или Visual Studio
5. По условиям задачи (моей) все узлы равноправны и хранятся в одной куче (таблице (List)), т.к. могут поставляться как самостоятельно, так и в составе других узлов. Во вспомогательной таблице (ListSlave) хранятся связи с "дочерними" узлами первого уровня. Узлы всех уровней расчитываются с помощью вышеуказанной функции.

Картинки:


Связка List->ListSlave


Связка List->EvalUnitsLevels

Добавлено через 19 минут
Если интересно, можем поговорить о том, как не дать юзеру создать циклическую ссылку при таком раскладе ...

[sashulyT]

minimus, картинки не отображаются

[minimus]

Цитата: Сообщение от sashulyT minimus, картинки не отображаются

Странно! У меня отображаются ...
Если интересно посмотреть на картинки, а в данном контексте это действительно должно быть интересно , то вот тебе прямые ссылки на картинки:

List->ListSlave: http://i279.photobucket.com/albums/k...nitsLevels.jpg

List->EvalUnitsLevels: http://i279.photobucket.com/albums/k.../ListSlave.jpg

P.S. Извини, что перепутал названия картинок, когда сохранял ...