数据库中树形图的用法

数据库中树形图的用法的用法你知道吗？下面我就跟你们详细介绍下数据库中树形图的用法的用法，希望对你们有用。

数据库中树形图的用法的用法如下：

树形图用于显示按照树形结构进行组织的数据，其用途比较广泛，如计算机中的文件系统(Windows中的资源管理器)、企业或公司的组成结构等。我们知道在Windows下VB、PB、Delphi等工具提供了一个功能很强的树型控件TreeView，利用Treeview控件可以方便地开发树形图。然而在网页上实现树形图就不那么容易了，现在在asp.net中利用微软提供的Internet Explorer WebControls它使得网页上的树形图开发与在Windows下一样的方便，一样的功能强大，甚至更灵活。

本文介绍用Internet Explorer WebControls开发树形图的方法，由于树形图结构较复杂，使用起来常不知如何下手。笔者结合最近刚为公司用ASP.NET编写的应用程序管理器这一具体实例，详细阐述在ASP.NET下如何将Internet Explorer WebControls的使用与数据库联系起来，实现数据分任意多层显示，方便地进行增加、修改、删除、移动 *** 作。笔者希望通过对该实例的阐述，达到抛砖引玉的效果，与各位同仁相互交流，共同进步。

Internet Explorer WebControls不在VS.NET的标准Server Control中，要到微软的站点上下载，下载地址是：

http://msdn.microsoft.com/downloads/samples/internet/default.asp?url=/Downloads/samples/Internet/ASP_DOT_NET_ServerControls/WebControls/default.asp

下载安装后第一次使用时，要右击工具箱Customize Toolbox…→.NET Framework Components中找到Micosoft.Web.UI.WebControls.Treeview后选中，这样Treeview控件就出现在工具箱中了。

一、树的建立

具体方法是：创建一个数据库，设计树图信息表TREE_INFO，包含NODEID、PARENTID、NODENAME、ADDErss、ICON字段，其它字段根据实际业务而定，节点名称NODENAME将在树型控件的节点上显示，NODEID字段保存节点的唯一标识号，PARENTID表示当前节点的父节点号，标识号组成了一个“链表”，记录了树上节点的结构。设计一个Web窗体其上放置TreeView控件。

PRivate Sub CreateDataSet()’建立数据集

Dim myConn As New SqlConnection()

Dim myCmd As New SqlCommand("select NODEID,NODENAME,PARENTID,ADDRESS,ICON from Tree_info", myConn)

Dim myDataAdapter As New SqlDataAdapter()

myConn.ConnectionString = application("connectstring")

myCmd.CommandText = ""

myCmd.Connection = myConn

myDataAdapter.SelectCommand = myCmd

myDataAdapter.Fill(ds, "tree")

End Sub

建树的基本思路是：从根节点开始递归调用显示子树

Private Sub Page_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load

CreateDataSet()

intiTree(TreeView1.Nodes, 0)

End Sub

Private Sub intiTree(ByRef Nds As TreeNodeCollection, ByVal parentId As Integer)

Dim dv As New DataView()

Dim drv As DataRowView

Dim tmpNd As TreeNode

Dim intId As Integer

dv.Table = ds.Tables("tree")

dv.RowFilter = "PARENTID=’" &parentId &"’"

For Each drv In dv

tmpNd = New TreeNode()

strId = drv("NODE_ID")

tmpNd.ID = strId

tmpNd.Text = drv("NODE_NAME ")

tmpNd.ImageUrl = drv("ICON").ToString

Nds.Add(tmpNd)

intiTree(Nds(Nds.Count - 1).Nodes, intId)

Next

End Sub

二、增加、删除树节点

单纯在Treeview 上增加、删除、修改节点只需用Nodes属性的Add、 Remove、等方法即可，值得注意的地方是VS.NET中Treeview的Nodes集合与VS6.0中的区别，VS6.0中的是一个大的集合，而VS.NET中的是分层的每个Node下都有Nodes属性。增加、删除、修改树节点时与VS6.0相比有很大差别，特别是删除时。

Private Sub ButAdd_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles ButAdd.Click’在选定的节点下添加子节点

Dim tmpNd As New TreeNode(), NdSel As TreeNode

tmpNd.ID = GetNewId()

NdSel = TreeView1.GetNodeFromIndex(TreeView1.SelectedNodeIndex)’选中的节点

tmpNd.Text = "新节点"

NdSel.Nodes.Add(tmpNd)

Dim myRow As DataRow

myRow = ds.Tables("tree").NewRow()

myRow("NODE_NAME") = tmpNd.ID

myRow("NODE_DESCRipT") = "新节点" &tmpNd.ID &"_" &NdSel.ID

myRow("PARENT_NAME") = NdSel.ID

ds.Tables("tree").Rows.Add(myRow)

End Sub

Private Sub ButDele_Click(ByVal sender As Object, ByVal e As System.EventArgs) Handles ButDele.Click’删除选中的节点

Dim idx As String = TreeView1.SelectedNodeIndex()

GetNdCol(idx).Remove(TreeView1.GetNodeFromIndex(idx))

Dim dv As New DataView(), recNo As Integer

dv.Table = ds.Tables("tree")

dv.RowFilter= "NODEID=" &NdId

dv.Delete(0)

End Sub

Private Function GetNdCol(ByVal idx As String) As TreeNodeCollection

‘获得选中节点的父节点的Nodes集合

Dim cnt As Integer, i As Integer

Dim tmpNds As TreeNodeCollection

Dim idxs() As String

idxs = Split(idx, ".")

cnt = UBound(idxs)

If cnt = 0 Then

tmpNds = TreeView1.Nodes

Else

tmpNds = TreeView1.Nodes(CInt(idxs(0))).Nodes

For i = 1 To cnt - 1

tmpNds = tmpNds(CInt(idxs(i))).Nodes

Next

End If

Return tmpNds

End Function

三、修改、移动树节点

由于服务器控件不支持鼠标拖动事件，所以不能象Windows程序那样通过拖动移动节点，这里是通过选择父节点的方式。移动是通过在原位置删除，新位置添加实现的，要注意在删除时先保存节点信息。

Private Sub TreeView1_SelectedIndexChange(ByVal sender As Object, ByVal e As Microsoft.Web.UI.WebControls.TreeViewSelectEventArgs) Handles TreeView1.SelectedIndexChange

Dim dv As New DataView()

dv.Table = ds.Tables("tree")

Dim tmpNd As TreeNode = TreeNdSel(e.OldNode), tmpNds As TreeNodeCollection

dv.RowFilter= "NODEID=" &tmpNd.ID

dv(0)("NODE_DESCRIPT") = Me.TextBox1.Text

dv(0)("ADDRESS") = Me.TextBox2.Text

dv(0)("TARGET") = Me.TextBox3.Text

dv(0)("ICON") = Me.TextBox4.Text

If dv(0)("PARENTID").ToString <>Me.DropDownList1.SelectedItem.Value Then

‘移动节点

dv(0)("PARENT_NAME") = Me.DropDownList1.SelectedItem.Value

If Me.DropDownList1.SelectedItem.Value = "ROOT" Then

tmpNds = TreeView1.Nodes

Else

tmpNds = FromIdToNode(Me.DropDownList1.SelectedItem.Value, TreeView1.Nodes).Nodes’新的父节点的Nodes集合

End If

GetNdCol(e.OldNode).Remove(tmpNd)

tmpNds.Add(tmpNd)

End If

tmpNd.Text = Me.TextBox1.Text

tmpNd.ImageUrl = Me.TextBox4.Text

tmpNd = TreeView1.GetNodeFromIndex(TreeView1.SelectedNodeIndex)

dv.RowFilter= "NODEID=" &tmpNd.ID

Me.TextBox1.Text = dv(0)("NODENAME").ToString

Me.TextBox2.Text = dv(0)("ADDRESS").ToString

Me.TextBox3.Text = dv(0)("TARGET").ToString

Me.TextBox4.Text = dv(0)("ICON").ToString

End Sub

Private Function FromIdToNode(ByVal ID As String, ByVal Nds As TreeNodeCollection) As TreeNode

‘由关键字查找节点

Dim i As Integer

Dim tmpNd As TreeNode, tmpNd1 As TreeNode

For Each tmpNd In Nds

If tmpNd.ID = ID Then

Return tmpNd

Exit Function

End If

tmpNd1 = FromIdToNode(ID, tmpNd.Nodes)

If Not (tmpNd1 Is Nothing) Then

Return tmpNd1

Exit Function

End If

Next

Return Nothing

End Function

1、首先第一步若节点右左子树，则左链域lchild指示其左孩子（ltag=0）,否则，令左链域指示其前驱（ltag=1）。若结点有右子树，则右链域rchild指示其右孩子（rtag=0）,否则，令右链域指示其后继（rtag=1）。

2、然后击亅实现这一过程，设指针p指向当前结点，pre始终指向刚刚访问过的结点，即p的前驱，以便于修改pre的后继线索和p的前驱线索。在线索化算法中访问当前结点p来进行处理。

3、最后几是结点p的左指针域为空，则将其标志位置为1，并使p->lchild指向中序前驱结点pre（即左线索化）；结点pre的右指针域为空，则将其标志位置为1，并使pre->rchild指向中序后继结点p（即右线索化）；将pre指向刚刚访问过的结点p（即pre=p），线索化p的右子树。

树状结构的数据保存在数据库中的常用方法有一下两种：

1、邻接表(adjacency list model)

2、预排序遍历树算法(modified preorder tree traversal algorithm)

用一下的例子讨论这两种方法的差异：

现有一棵树如下：

邻接表模式：

这种模式我们经常用到，很多的教程和书中也介绍过。我们通过给每个节点增加一个属性 parent 来表示这个节点的父节点从而将整个树状结构通过平面的表描述出来。根据这个原则，例子中的数据可以转化成如下的表:

我们看到 Pear 是Green的一个子节点，Green是Fruit的一个子节点。而根节点'Food'没有父节点。 为了简单地描述这个问题， 这个例子中只用了name来表示一个记录。 在实际的数据库中，你需要用数字的id来标示每个节点，数据库的表结构大概应该像这样：id, parent_id, name, description。

以下是代码：

<?php

// $parent is the parent of the children we want to see

// $level is increased when we go deeper into the tree,

//used to display a nice indented tree

function display_children($parent, $level)

{

// 获得一个 父节点 $parent 的所有子节点

$result = mysql_query('SELECT name FROM tree '.

'WHERE parent="'.$parent.'"')

// 显示每个子节点

while ($row = mysql_fetch_array($result))

{

// 缩进显示节点名称

echo str_repeat(' ',$level).$row['name']."n"

//再次调用这个函数显示子节点的子节点

display_children($row['name'], $level+1)

}

}

?>

对整个结构的根节点（Food）使用这个函数就可以打印出整个多级树结构，由于Food是根节点它的父节点是空的，所以这样调用: display_children('',0)。将显示整个树的内容：

Food

Fruit

Red

Cherry

Yellow

Banana

Meat

Beef

Pork

如果你只想显示整个结构中的一部分，比如说水果部分，就可以这样调用：display_children('Fruit',0)

几乎使用同样的方法我们可以知道从根节点到任意节点的路径。比如 Cherry 的路径是　"Food >Fruit >Red"。 为了得到这样的一个路径我们需要从最深的一级"Cherry"开始， 查询得到它的父节点"Red"把它添加到路径中， 然后我们再查询Red的父节点并把它也添加到路径中，以此类推直到最高层的"Food"

以下是代码：

<?php

// $node 是那个最深的节点

function get_path($node)

{

// 查询这个节点的父节点

$result = mysql_query('SELECT parent FROM tree '.

'WHERE name="'.$node.'"')

$row = mysql_fetch_array($result)

// 用一个数组保存路径

$path = array()

// 如果不是根节点则继续向上查询

// (根节点没有父节点)

if ($row['parent']!='')

{

// the last part of the path to $node, is the name

// of the parent of $node

$path[] = $row['parent']

// we should add the path to the parent of this node

// to the path

$path = array_merge(get_path($row['parent']), $path)

}

// return the path

return $path

}

?>

如果对"Cherry"使用这个函数：print_r(get_path('Cherry'))，就会得到这样的一个数组了：

Array

(

[0] =>Food

[1] =>Fruit

[2] =>Red

)

接下来如何把它打印成你希望的格式，就是你的事情了。

缺点：

这种方法很简单，容易理解，好上手。但是也有一些缺点。主要是因为运行速度很慢，由于得到每个节点都需要进行数据库查询，数据量大的时候要进行很多查询才能完成一个树。另外由于要进行递归运算，递归的每一级都需要占用一些内存所以在空间利用上效率也比较低。

预排序遍历树算法

现在让我们看一看另外一种不使用递归计算，更加快速的方法，这就是预排序遍历树算法(modified preorder tree traversal algorithm) 这种方法大家可能接触的比较少，初次使用也不像上面的方法容易理解，但是由于这种方法不使用递归查询算法，有更高的查询效率。

我们首先将多级数据按照下面的方式画在纸上，在根节点Food的左侧写上 1 然后沿着这个树继续向下 在 Fruit 的左侧写上 2 然后继续前进，沿着整个树的边缘给每一个节点都标上左侧和右侧的数字。最后一个数字是标在Food 右侧的 18。 在下面的这张图中你可以看到整个标好了数字的多级结构。（没有看懂？用你的手指指着数字从1数到18就明白怎么回事了。还不明白，再数一遍，注意移动你的手指）。

这些数字标明了各个节点之间的关系，"Red"的号是3和6，它是 "Food" 1-18 的子孙节点。 同样，我们可以看到 所有左值大于2和右值小于11的节点 都是"Fruit" 2-11 的子孙节点

这样整个树状结构可以通过左右值来存储到数据库中。继续之前，我们看一看下面整理过的数据表。

注意：由于"left"和"right"在 SQL中有特殊的意义，所以我们需要用"lft"和"rgt"来表示左右字段。 另外这种结构中不再需要"parent"字段来表示树状结构。也就是 说下面这样的表结构就足够了。

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11

看到了吧，只要一个查询就可以得到所有这些节点。为了能够像上面的递归函数那样显示整个树状结构，我们还需要对这样的查询进行排序。用节点的左值进行排序：

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC

---