Delphi - сбориник статей


Неограниченное дерево


Фиксированное дерево очень удобно в работе. Но что делать, если по условию задачи невозможно ограничить максимальную глубину дерева? В этом случае придется задавать отношения между узлами более привычным способом. Родительские и дочерние узлы находятся в отношении many-to-many (каждому родительскому узлу может соответствовать множество дочерних, а каждому дочернему -- множество родительских, начиная с непосредственного предка и кончая корнем всего дерева). В соответствии с теорией, такое отношение реализуется вводом дополнительной таблицы.

Таблица MainTable

Название поля Тип поля Комментарий
ID Autoincrement Первичный ключ
Name Char Название узла

Таблица LinkTable

Название поля Тип поля Комментарий
ParentID Integer Ссылка на родительский узел
ChildID Integer Ссылка на дочерний узел
Distance Integer Расстояние между узлами

Значение поля Distance равно 0, если ParentID и ChildID совпадают. В противном случае оно равно порядковому номеру узла ChildID при движении к нему по дереву от узла ParentID. procedure OutTree(Root : Integer); var L : Integer; procedure MakeLevel(ParentID : Integer; const ParentName : String); var S : String; Q : TQuery; begin OutNode(ParentID,L,ParentName); Inc(L); S:='SELECT ID,Name FROM MainTable AS M JOIN LinkTable AS L ON (M.ID=L.ChildID) '+ 'WHERE (L.ParentID=%d) AND (L.Distance=1) ORDER BY ID'; Q:=OpenQuery(Format(S,[ParentID])); while NOT Q.Eof do begin MakeLevel(Q.FieldByName('ID').AsInteger,Q.FieldByName('Name').AsString); Q.Next; end; Dec(L); end; begin L:=0; with OpenQuery('SELECT Name FROM MainTable WHERE ID='+IntToStr(Root)) do MakeLevel(Root,FieldByName('Name').AsString); end; procedure AddNode(Parent : Integer; const Name : String); var S : String; NewNode : Integer; begin ExecQuery(Format('INSERT INTO MainTable (Name) VALUES ("%s")',[Name])); NewNode:=LastInsertID; // Следующий запрос не будет работать в Local SQL. S:='INSERT INTO LinkTable (ParentID,ChildID,Distance) '+ 'SELECT ParentID,%d,Distance FROM LinkTable '+ 'WHERE ChildID=%d'; ExecQuery(Format(S,[NewNode,Parent])); S:='INSERT INTO LinkTable (ParentID,ChildID,Distance) VALUES (%d,%0:d,0)'; ExecQuery(Format(S,[NewNode])); end; procedure DeleteNode(Node : Integer); var S : String; begin S:='DELETE FROM MainTable '+ 'WHERE ID IN (SELECT ChildID FROM LinkTable WHERE ParentID=%d)'; ExecQuery(Format(S,[Node])); S:='DELETE FROM LinkTable '+ 'WHERE ChildID IN (SELECT ChildID FROM LinkTable WHERE ParentID=%d)'; ExecQuery(Format(S,[Node])); end; function NodeInSubtree(Node,Parent : Integer) : Boolean; var S : String; Q : TQuery; begin S:='SELECT Count(*) FROM LinkTable WHERE (ParentID=%d) AND (ChildID=%d)'; Q:=OpenQuery(Format(S,[Parent,Node])); Result:=(Q.Fields[0].AsInteger > 0); end; procedure SetParent(Node,Parent : Integer); var S : String; Parents,Subtree : String; begin Parents:=Format('SELECT ParentID FROM LinkTable '+ 'WHERE (ChildID=%d) AND (ParentID<>%0:d)',[Node]); Subtree:=Format('SELECT ChildID FROM LinkTable '+ 'WHERE ParentID=%d',[Node]); S:='DELETE FROM LinkTable '+ 'WHERE (ParentID IN ('+Parents+')) AND (ChildID IN ('+Subtree+'))'; ExecQuery(S); // Следующий запрос не будет работать в Local SQL. S:='INSERT INTO LinkTable (ParentID,ChildID,Distance) '+ 'SELECT T1.ParentID,T2.ChildID,T1.Distance+T2.Distance+1 '+ 'FROM LinkTable AS T1,LinkTable AS T2 '+ 'WHERE (T1.ChildID=%d) AND (T2.ParentID=%d)'; ExecQuery(Format(S,[Parent,Node])); end;

Как нетрудно заметить, для неограниченного дерева хорошо реализуются все операции за исключением вывода поддерева: получить одним запросом все узлы, входящие в поддерево, достаточно легко, но вот упорядочить их так, чтобы получилось дерево, мне не удалось. Если кто знает способ, как можно представить неограниченное дерево в БД, чтобы любое поддерево можно было вывести одним запросом с учетом правильного порядка, то мне это по-прежнему очень интересно.




Начало  Назад  Вперед