Есть дерево. Но не бинарное. :)

← →
Sat7 (2002-04-12 11:59) [0]

Кто предложит оптимальную древовидную структуру для хранения (извиняюсь за каламбур) структуры директорий на винте и их поиска?
Задачка сводится к следующему: спроектировать класс, который хранит в себе структуру каталогов винта и функции их поиска. Единственное условие - поиск нужной директории в структуре должен идти рекурсивно. Я все-таки склоняюсь к связному списку, но здесь есть некоторые трудности. У бинарного дерева две ветки - правая и левая, по нему легко пройтись рекурсией. А обход дерева каталогов...
Подскажите, если кто-то имел с этим дело.

← →
Anatoly Podgoretsky (2002-04-12 12:09) [1]

Используй двухсвязный список, поля prev, next можешь назвать right, left

← →
Alx2 (2002-04-12 12:12) [2]

Связный список веток в глубину. мультидерево такое вот.

← →
Виктор Щербаков (2002-04-12 12:12) [3]

Может поможет:
http://algolist.manual.ru/ds/index.php

← →
vovochka (2002-04-12 12:17) [4]

TNode = record
Parent:TNode;
prev,next:TNode;
FirstChild,LastChild:TNode;

......

end;
У?

← →
Бурундук (2002-04-12 12:17) [5]

А почему всё-таки не бинарное? (firstchild, nextbrother)

← →
Sat7 (2002-04-12 12:29) [6]

vovochka © (12.04.02 12:17)

примерно то же самое я и делал.
Работает медленно, а именно в данном случае скорость очень важна...

← →
vovochka (2002-04-12 12:36) [7]

А где были тормоза?
HASH пробывал?

← →
Sat7 (2002-04-12 12:45) [8]

vovochka © (12.04.02 12:36)

Проблема в том, что поля parent, FirstChild и LastChild- чуть-чуть не то. Я ведь не знаю заранее сколько поддиректорий будет в директории, т.е. чтобы узнать это мне нужно их все перебрать и посмотреть, parent нужный или нет. Вот здесь тормоза и есть.

← →
Игорь Шевченко (2002-04-12 12:58) [9]

День добрый,

А TStringList не подходит, у которого в Objects для каждого каталога находится аналогичный TStringList с подкаталогами и так далее... ?

С уважением,

← →
vovochka (2002-04-12 13:28) [10]

2Sat7

Чёто я тебя совсем непонимаю.
По-моему это один из самых лучших вариантов. Что-то типа однонаправленного графа.
Где будут тормоза: при создании, поиске или где?

← →
Sat7 (2002-04-12 14:01) [11]

vovochka © (12.04.02 13:28)

Давай более общий случай рассмотрим. Представь, что тебе нужно сначала заполнить дерево, а потом посчитать сумму в узлах дерева, обойти все эти узлы. Но не обычного дерева - "Радость первокурсника", а дерева, у которого из одного узла отходит не две ветки, а заранее неизвестно сколько. Получается, что у нас есть: деревце, в узлах которого находятся значения, общую сумму которых нужно посчитать, и, собственно, узлы, из которых отходит несколько веток. Сколько веток будет - до заполнения не знаешь. Как ты станешь делать заполнение и обход узлов (подсчет суммы)?

← →
vovochka (2002-04-12 14:19) [12]

Ля, это просто список типа "радост первокурсника"! Обходишь все узлы по рекурсии и всё!

будет что-то типа:

function Calc(n:TNode):integer;
var
pc:TNode;
begin
result:=0;
pc:=n.FirstChild;
while pc<>nil do
begin
result:=result+pc.value;
if pc.FirstChild<>nil then result:=result+Calc(pc);
pc:=pc.next;
end;
//По моему всё должно работать.
end;

Так надо или мы друг друга непонимаем?

← →
Бурундук (2002-04-12 14:21) [13]

Любое дерево можно преобразовать в бинарное.
Собственно, в таком виде, как это предлагает vovochka ©
оно уже бинарное
(От каждого узла дерева отходят две ветки - FirstChild и Next).

Есть дерево. Но не бинарное. :) Найти похожие ветки