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