根据数据库表中记录自动构造一棵结构树的一种高效算法

一、前言：
    在好多场合下，都存在着很多像树一样的结构；如公司机构、军队职务、图书管理等，甚至好多论坛上的信息都是以树形的结构显示出来的。由于这样的结构存在无限子类、无限级别、信息多变的特点。无法由一开始就设计好一种结构，而往往这种结构是随时都可能改变的。这样，就需要有一种可以根据一批信息自动构造一棵结构树的算法。
    当今绝大多数信息是以数据库的形式保存起来的，下面我们就以数据库为操作源，以Delphi为编程工具，介绍一种根据数据库表中记录自动构造一棵结构树的一种高效算法。

二、数据库表结构设计：
    数据库表的结构设计关系到构造树的难易程序与速度，所以数据库表结构一定要设计合理，巧妙！在本算法中，数据库表结构关系到构造树的有三个字段，它们分别是：

字 段 名	代 表 意 义	字段类型	其它说明
NodeID	结点自身ID号	自动编号	关键字
NodeName	结点名称	字符类型	不能为空
PNodeID	父结点ID号	长整形	不能为空，默认值为0表示为一级结点

    当然还可以加入其它字段作为实际意义的信息记录，不过构造一棵结构树只需要用到上面所提到的三个字段。下面是一张数据库表的例子：

三、数据结构设计：
    同样，为了使构造好的一棵树中每一个结点都能对应到实际表中的相应记录（即当选择某结点时，表指针能自动指向相应的记录），必须设计一个结构体；结构体如下（Pascal描述）：
// 定义树结点与数据库表记录对应的结构体
type
  PNode = ^TNode;
  TNode = record
    FID:integer;                 // 记录的ID号
    FBM:TBookMark;        // 定位记录的指针（书签）
end;

四、算法：
  1、首先，数据库必须打开，使用一个查询得到要构造树的表，得到的表已经按一定的规则排好序；其SQL执行语句如下：
select * from Department order by PNodeID,NodeID
  2、为了构造一棵属于自已的子树，可以选构造一棵属于自已的一级子树，然后采用递归算法，以子结点为子树的根结点，逐个构造它们的一级子树；逐层构造，递归，这样就形成了一棵我们想要得到的结构树；
  3、为了构造一棵属于自已的一级子树，我们可以用一个Select 语句查询得到所有属于自已的子结点记录，但是我们不这样做，因为这样会反复执行好多次Select 语句，造成多次进行磁盘操作甚至网络访问，导致速度变慢，而且不方便结点与记录的感应；在这里，我们充分的利用了已打开表已经排好序的特点，利用DataSet 的Local方法找到第一个子结点的记录，然而表已按父结点排好序，如果有兄弟结点，肯定是紧跟其后；当我们找到第一个子结点后，再一条一条的下移一条记录，如果有相同的父结点，我们加入到树中，如果没有了或已到表结尾了，构造一级子树完毕，就返回（此时，记得将记录回滚到上一条）。
  4、在把表记录作为树结点添加的同时，在内存中分配一个存放TNode结构的空间，并存入记录ID号和记录在数据库表中的位置（即书签），并把树结点的数据指针指向该内存地址。
  5、到此，一棵结构树自动构造成功。

五、流程图：

六、源代码：
unit BuildTreeUnit;
 
interface
 
uses
  DB, ADODB, ComCtrls;
 
// 定义树结点对数据库表记录对应的结构体
type
  PNode = ^TNode;
  TNode = record
    FID:integer;    // 记录的ID号
    FBM:TBookMark;  // 定位记录的指针（书签）
end;
 
function BuildTree(DataSet: TADODataSet; TV: TTreeView; SelfField,SelfName,ParentField:String):boolean;
 
implementation
 
function BuildTree(DataSet: TADODataSet; TV: TTreeView; SelfField,SelfName,ParentField:String):boolean;
  { 以下子函数为在表中查找第一个PNode=AIndex的记录}
  function FindKey(AIndex: integer; FFirst:boolean): boolean;
  begin
    Result:=DataSet.Locate(ParentField,AIndex,[loCaseInsensitive]);
  end;
  { 以下函数在FindKey的基础上找出下一个符合的记录}
  function FindNext(AIndex: integer): boolean;
  begin
    DataSet.Next;
    if DataSet.Eof then
      Result:=false
    else
      Result:=DataSet.FieldValues[ParentField]=AIndex;
    if not Result then DataSet.Prior;
  end;
  { 以下函数据构造当前结点的一级子树 }
  function GetChildNode(index: integer; ANode: TTreeNode):integer;
  var
    MyNode:PNode;
    Node:TTreeNode;
  begin
    if FindKey(index,true) then
    begin
      new(MyNode);
      with DataSet do
      begin
        MyNode^.FID :=FieldValues[SelfField];
        MyNode^.FBM :=GetBookmark;
      end;
      Node:=TV.Items.AddChild(ANode,DataSet.FieldValues[SelfName]);
      Node.Data:=MyNode;
      Result:=1;
      while FindNext(index) do
      begin
        new(MyNode);
        with DataSet do
        begin
          MyNode^.FID :=FieldValues[SelfField];
          MyNode^.FBM :=GetBookmark;
        end;
        Node:=TV.Items.AddChild(ANode,DataSet.FieldValues[SelfName]);
        Node.Data:=MyNode;
        Result:=Result+1;
      end;
    end
    else
      Result:=0;
  end;
  { 以下函数据以ANode 为结当，构造一棵属于自己的子树}
  procedure BuildMe(AIndex: integer; ANode: TTreeNode);
  var
    NodeNum:integer;
    Node:TTreeNode;
    i:integer;
  begin
    NodeNum:=GetChildNode(AIndex,ANode);
    if NodeNum>0 then
    begin
      if ANode=nil then Node:=TV.Items.GetFirstNode
      else
        Node:=ANode.getFirstChild;
      for i:=1 to NodeNum do
      begin
        BuildMe(PNode(Node.Data)^.FID,Node);
        Node:=ANode.GetNextChild(Node);
      end;
    end;
  end;
  // 组合部份
begin
  if (DataSet=nil) or (DataSet.Active =false) then
    Result:=false
  else if (TV=nil) then
    Result:=false
  else begin
    TV.Items.Clear;
    BuildMe(0,nil);
    Result:=true;
  end;
end;
 
end.