优化——使用“二分法”快速建立数据树

标题：优化——使用“二分法”快速建立数据树

内容：

父子节点的数据量上万，花了一个晚上的时间对建树的算法做了优化。

比用循环查找父节点来建树的速度快多了。 ^_^

谨记之。

备注：对数据表中父子节点的数据如下形式的可以使用本算法。

DID PID FLMC
1 0 A
2 0 B
3 0 C
4 1 A1
5 1 A2
6 2 B1
7 2 B2
8 3 C1
9 3 C1
10 4 A11
11 4 A12

{====================================================================
功 能: 定义结构体，用来保存所有非叶子节点的DID和节点的唯一句柄。
节点的句柄用来查找节点。
Treeview.Items.GetNode(Handle)可以得到该节点。

备 注: HTreeItem的定义需要Uses Commctrl。

日 期: 2006/01/16 by JRQ
=====================================================================}

Uses Commctrl;

type
PTree_Node=^TTree_Node;
TTree_Node=record
DID : Integer; //非叶子节点的DID
Handle : HTreeItem; //非叶子节点的句柄
end;

var MyNode: PTree_Node; //自定以结构

{====================================================================
功 能: 使用“二分法”创建父子节点树。
通过TList保存数据表中所有的非叶子节点的序号和句柄。
然后遍历数据表中的数据一次即可生成树。
遍历数据时，需要确定此数据的父节点，此时使用二分法在TList中查找。
使用两分法搜索节点，比循环搜索父节点速度快，这是提高效率的基础。
当树的深度和广度的数值都较大时，其优越性尤为明显。

备 注: 2006/01/16 by JRQ
=====================================================================}

procedure BuildFLBTree(aTreeview: TTreeview; //对象树
Root:TTreeNode; //顶级根节点
aQuery:TADOQuery); //查询数据集

//GetDIDIndex为二分查找实现函数
function GetDIDIndex(aList:TList; nStart,nEnd:Integer; aDID:Integer):Integer;
var i:integer;
StartNode,EndNode:PTree_Node;

begin
Result:=-1;
if nEnd<nStart then
Exit;

StartNode:= aList.Items[nStart]; //起始
EndNode:= aList.Items[nEnd]; //末尾

if (nEnd=nStart) then
begin
if EndNode.DID =aDID then
Result:=nEnd; //返回非叶子节点的Index
Exit;
end;

if (aDID < StartNode.DID) or (aDID > EndNode.DID) then
Exit;

i:=((nStart+nEnd) shr 1); //右移动一位，相当于除以2

MyNode:= aList.Items[i];
if aDID = MyNode.DID then
Result:=i //找到非叶子节点的Index
else
if aDID > MyNode.DID then
Result:=GetDIDIndex(aList,i+1,nEnd,aDID)
else
if aDID < MyNode.DID then
Result:=GetDIDIndex(aList,nStart,i,aDID);
end;

var
i,PIDCount,aDID,aPID:Integer;
sName:String;
aNode:TTreeNode; //树节点
aList:TList;
begin
aList:=TList.Create;
try
with aQuery do
begin
Close;
SQL.Clear;
//检索非叶子节点的DID，这些DID都保存在PID中（除0以外的PID中保存的是全部非叶子节点的DID）
SQL.Add('Select PID From CLASSIFY Where PID<>''0'' Group By PID Order By PID ');
Open;

First;

//取出所有非叶子节点的DID，然后保存在List中，因为这些节点可能会重复使用。
//PID为0的节点是顶层节点。除0以外的PID中保存的是全部非叶子节点的DID。
while Not(Eof) do
begin
aPID:=FieldbyName('PID').AsInteger;

New(MyNode); //生成一个节点的记录
MyNode.DID:=aPID;
MyNode.Handle:=nil; //初试化 Handle 值为空
aList.Add(MyNode);
Next;
end; //while Not(Eof) do

PIDCount:=aList.Count; //保存TList中所有非叶子节点的个数

Close;
SQL.Clear;

//查询数据表中所有的父子节点记录，以PID和DID排序，这点非常重要。
//以PID和DID排序，这样能保证所有在树上的父节点都比子节点早建立。
SQL.Add('Select DID,PID,FLMC From D_CLASSIFY Order By PID,DID ');
Open;

First;

while Not(Eof) do //遍历一次查询结果，找到每个节点的根节点，然后构建父子节点树。
begin
aDID:=FieldbyName('DID').AsInteger;
aPID:=FieldbyName('PID').AsInteger;
sName:=Trim(FieldbyName('FLMC').AsString);

if (aPID=0) then //处理第一层根节点，第一层根节点其PID为0。
begin
aNode:=aTreeview.Items.AddChild(Root,sName); //添加节点
aNode.ImageIndex:= 0; //添加图标
aNode.SelectedIndex:= 1;

i:=GetDIDIndex(aList,0,PIDCount-1,aDID); //找到根节点，为其 Handle 赋值
if i>=0 then
Ptree_Node(aList.Items[i]).Handle:= aNode.ItemId; //为List中找到的节点的Handle赋值
end
else
begin //处理非第一层的节点
i:=GetDIDIndex(aList,0,PIDCount-1,aPID); //找到根节点的位置

//通过Handle在目录树上找到根节点
aNode:=aTreeview.Items.GetNode(Ptree_Node(aList.Items[i]).Handle);

if aNode<>nil then
begin
aNode:=aTreeview.Items.AddChild(aNode,sName); //将本节点添加到找到的根节点上
aNode.ImageIndex:= 0; //添加图标
aNode.SelectedIndex:= 1;
end;

i:=GetDIDIndex(aList,0,PIDCount-1,aDID); //在List中找本节点，判断本节点是否存在List中。

if i>=0 then //如果本节点在List中存在，则本节点还有下级节点。

//为List中找到的节点的 Handle赋值
PTree_Node(aList.Items[i]).Handle:= aNode.ItemId;

end;
Next;
end; //while Not(Eof) do
end;//with aQuery do

finally

//释放节点
for i:=0 to alist.Count-1 do
begin
MyNode:=alist.Items[i];
if MyNode<>nil then
Dispose(MyNode); //释放
end;
FreeAndNil(aList);//释放
end;
end;

－完－

By JRQ

2006/02/20 于穗