用递归生成树的算法和数据库设计

时间:2021-11-27 12:59:16
1.用递归生成树的算法和数据库设计
(1)递归说明
    程序调用自身的编程方法称为递归(recursion)。在树的生成以及图的遍历中,递归用的很多。经典的算法求   n!   (求n的阶乘)中,用的就是递归方法。递归算法的优点就是简洁,可扩充性好。但是缺点也很明显:低效。因为递归就是程序不断调用自身,对系统的资源消耗比较大。随着节点的增多,执行效率会变的很低。  
    为了解决树在生成过程中的层树不定的问题,同时也是为了让树的扩展性更好。树的生成使用了递归的方法。生成树的代码一旦写成,可以不改动源代码,生成无限级层次的树。树的结构完全由数据库中表的数据决定。
(2)数据库设计
    创建一个数据库,设计树图信息表Treetable,表中属性包含Nodeid、Parentid、Nodename、Address等字段(分别用于表示节点的ID、父节点ID、节点名称、链接地址),其它属性根据实际用户需求和设计而定。节点名称Nodename将在树型控件的节点上显示,Nodeid字段保存节点的唯一标识号,Parentid表示当前节点的父节点ID号(例如有两个节点是父子关系,孩子节点的Parentid值就是其父节点的Nodeid),节点号父子相接组成了一个“链表”,表征并记录了树上节点的层次结构。
表具体设计如下:(简化模型,实际使用的要复杂一些)

主键 属性名 类型 长度 可空 属性含义
  是  Nodeid    int       6       否      节点ID
       Parentid   int       6       否      父节点ID 
  Nodename   char  50     否       节点名称
      Address    char  80      可       链接地址

备注:链接地址   主要是用在:   树在框架中使用的环境。链接可以指向其他框架页中的地址或是带不同的参数。


(3)程序代码
――――――――――――递归函数――――――――――――
        '生成树的函数
        Private   Sub   inittree(ByRef   Nds   As   Microsoft.Web.UI.WebControls.TreeNodeCollection,   ByVal   parentId   As   Integer)
                Dim   dv   As   New   DataView()
                Dim   dvrow   As   DataRowView
                Dim   tmpNode   As   Microsoft.Web.UI.WebControls.TreeNode
                'intId为数值型变量,其作用是记录并传递当前记录的ID,做为它子节点的PARENTID值
                Dim   intId   As   Integer
                dv.Table   =   mySet.Tables( "paybasic ")
                'parentId传递的是   additem函数中的intId.下面语句的作用是找出当前节点的子孩子集合。  
                dv.RowFilter   =   "parentID= ' "   &   parentId   &   " ' "
                '如果当前节点有孩子,则遍历所有的孩子,并调用递归函数。
                For   Each   dvrow   In   dv
                        tmpNode   =   New   Microsoft.Web.UI.WebControls.TreeNode()
                        '为当前节点的各个属性赋值。
                        tmpNode.ID   =   dvrow( "nodeID ")
                        tmpNode.Text   =   dvrow( "nodename ")
                        tmpNode.NavigateUrl   =   dvrow( "Address ")
                        intId   =   dvrow( "parentID ")
                        '添加一个节点
                        Nds.Add(tmpNode)
                        '调用递归函数
                        inittree(Nds(Nds.Count   -   1).Nodes,   intId)
                Next
End   Sub
――――――――――――――――调用递归函数――――――――――――――――――
CreateReaderDataSet()
inittree(Treepaybasic.Nodes,   999)
―――――――――――――――――生成数据集―――――――――――――――――――
        '生成数据集的函数
        Private   Sub   CreateReaderDataSet()
                '在运行时连接,并设置连接属性
                MyConn   =   New   System.Data.OleDb.OleDbConnection( "Provider=MSDAORA.1;Data   Source=oracle9;User   ID=user;Password=****; ")
                '设置SelectCommand命令
                myAdapter.SelectCommand   =   New   System.Data.OleDb.OleDbCommand( "select   *   from   treenode ",   MyConn)
                '填充数据集
                myAdapter.Fill(mySet,   "treenode ")
        End   Sub