讨论：根据数据库构造一棵树的最佳算法！版主与高手请进！

Question

设计一个数据库结构，再结合TreeView控件，把数据库里的记录读出来写到树型控件中。可是我一直找不到一种好的方法，现有网上的算法都有缺限的。我自已写了种算法，构造一棵含有20,000个节点（五层）的树，结果花了7分多钟。有谁有更好的算法贡献一下，1000分相送！要求：记录数100,000条左右，构造时间不超过30秒；不限分级层次；

Answer 1

有一些系統的菜單就是直動生成的,
CSDN 的"我感興趣論壇"的設置應該就是同一原理.
在設計數據庫時候的時候,要記錄好隸屬關系,可以加一個字段進行區別,下面是本人用到的一個結構,供參考.
CREATE TABLE dbo.pu_prglist
              (SysNo varchar(10) NOT NULL,    --->系統代號
              PrgNo varchar(10) NOT NULL,    --->程式代號
              prgname varchar(40) NULL,      --->程式名稱
              sp_kind varchar(1) NULL,       ---->系統 & 程式
              Ord_no numeric(9,0) NULL,      ---->排序
              level numeric(3,0) NULL        ---->層次
       , CONSTRAINT pu_prglist_pkey
        PRIMARY KEY  NONCLUSTERED
       (SysNo,
       PrgNo)) ;

Answer 2

我觉得好像速度方面的话是比较难提高了，因为你是一下子把所有的数据结构全构造好。
我这有一个建议就是，第一步首先只创建根节点，然后再进行对点击事件进行判断处理，
当此节点只要是第一下点击事件的时候就再创建此节点的下一层结构，依此类推下去，所以
不必要将所有的节点都要一次性创建完，这样应该是最好的解决办法。不然你一下创建
就花了好几分钟，还有谁能接受的呢？像CSDN中的树好像也就是一样，点一层，创建一
层。
你还是自己考虑一下吧。

Answer 3

to: dofly(巴山夜雨) 
请给出算法to:goldpony(金马)
我原先也就用你所说的方法，但是有两个问题无法解决
一、无法根据该结点是否还有子结点来决定图标
二、如果有个命令要全部展开的话，开销会更大

Answer 4

我觉得树只要三个就已经描述清楚了
IP NAME PID
这已经足已
建树的时候要记住层层建，而不要一次全部建完！

Answer 5

呵呵，看看我以前写的算法，几万条数据也不过几秒钟，唉，可惜此算法没人欣尝：
一、前言：
    在好多场合下，都存在着很多像树一样的结构；如公司机构、军队职务、图书管理等，甚至好多论坛上的信息都是以树形的结构显示出来的。由于这样的结构存在无限子类、无限级别、信息多变的特点。无法由一开始就设计好一种结构，而往往这种结构是随时都可能改变的。这样，就需要有一种可以根据一批信息自动构造一棵结构树的算法。
    当今绝大多数信息是以数据库的形式保存起来的，下面我们就以数据库为操作源，以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 :=GetBook;
      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 :=GetBook;
        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.