算法问题１００分
怎么能把一个数据表里的数据，遍历成二叉树的形式显示出来，并且可以以任一节点查询这个节点以下的数据。
问题点数：100、回复次数：22Top
1 楼qianlukuan（akuan）回复于 2004-08-04 20:39:51 得分 0
设立父亲结点和子结点，是不是啊？Top
2 楼mjpclab（有只大猫猫 mjpclab.net）回复于 2004-08-04 22:21:59 得分 10
一种方法是打开哪个节点，就读取该节点下的数据
一种方法是一次读取所有记录，在本地缓存，所要做的就是用指针连接各记录Top
3 楼qlwqz（草农）回复于 2004-08-04 23:00:22 得分 10
用递归，输入（函数的参数）你要显示的根节点，然后显示下面的树就好了Top
4 楼look4sword（觅剑 | 劈柴、喂马、周游世界。）回复于 2004-08-05 07:54:10 得分 0
markTop
5 楼xzhy80（算了吧，散了吧）回复于 2004-08-05 08:18:22 得分 0
upTop
6 楼javasam（中晟时空（www.see168.net））回复于 2004-08-05 08:27:13 得分 0
建索引Top
7 楼angeldjd（邪恶天使）回复于 2004-08-05 09:01:00 得分 0
本人很菜，能不能给一个详细的算法。。小弟在这先谢过了。。。Top
8 楼shunzi110（顺子）回复于 2004-08-05 09:03:39 得分 0
不懂Top
9 楼whb147（苦乐随缘）回复于 2004-08-05 09:06:07 得分 0
根据节点ID然后遍历它的所有子节点
Top
10 楼jervis82（我是海绵.吸.吸.吸...）回复于 2004-08-05 09:11:34 得分 50
希望这个资料对你有点帮助吧。是关于遍历的。
===============================================================================
树型结构在ASP中的简单解决
树型结构在我们应用程序中还是很常见的，比如文件目录，BBS，权限设置，部门设置等。这些数
据信息都采用层次型结构，而在我们现在的关系型数据库中很难清淅表达。那么要在程序中遇到树型
结构问题该如何处理呢？
最近笔者通过一个ASP权限管理的程序轻松解决了一这问题，现在将其整理出来以飨读者。
首先，要将层次型数据模型转化为关系型数据模型。也就是说如何在我们的ACCESS，SQL SERVER
，ORACLE等关系型数据库中设计这个数据结构。
拿个实例来讲吧，譬如下面一个数据：
文档管理 1
|----新建文档 2
|----文档修改 3
|----文档归档 4
| |----查看归档信息 5
| |----删除归档信息 6
| | |----删除历史文档 7
| | |----删除正式文档 8
|----系统管理 9
|----用户管理 10
人事管理 11
行政管理 12
财务管理 13
这是一个很典型的层次型结构数据，那么大家想一想，如何将其通过二维表的形式来表达呢？初
看上去很难，是吧。可是仔细推敲一番还是有门路可钻的。
可以这样，将上面所有的权限视为一个权限字段，那么这个权限字段肯定是要有一个ID值的。我
们再给这个关系型数据表再强行加一个字段——隶属ID字段，也就是表明这个权限是属于哪一级权限
之下的，即这个ID值隶属于哪一个ID值。比如：“查看归档信息”权限ID值为“5”,它是隶属于“文
档归档”权限之下的，那么它的隶属ID字段的值就应该是“4”。OK，如果这一点能理解的话，那么我
们的关系转化工作也就算基本完成了。
下面我们就开始设计这张关系型数据表（以Sql Server 7.0 为例）：
+-----------+-----------+-----------+-----------+----------+
| 字段名 | 字段含义 | 字段类型 | 字段大小 | 字段属性 |
+-----------+-----------+-----------+-----------+----------+
| SelfID | 权限ID | Int | 4 | PK |
| PowerName | 权限名 | Varchar | 50 | Not Null |
| PowerInfo | 权限信息 | Varchar | 500 | |
| BelongID | 隶属ID | Int | 4 | |
+-----------+-----------+-----------+-----------+----------+
好了，结构设计好你就可以轻松输入你的测试数据了。
然后，我们就针对如何在网页中模仿层次结构显示这功能的ASP程序，这也是最关键的一步了。
程序清单：powerlist.asp
<%
'数据库连接
set conn=Server.CreateObject("ADODB.Connection")
conn.open "driver={SQL Server};server=chaiwei;DATABASE=chaiwei;UID=sa;PWD="
'打开所有父层数据
set rs=Server.CreateObject("ADODB.Recordset")
rs.Open "select * from powers where belongid is null order by powerid",conn,1,3
'层次数表态变量赋初值
format_i=1
'列表主程序段
do while not rs.eof
'打印父层数据信息
response.write "<a href='powerlist.asp?SelfID=" & rs("powerid") & "&BelongID=" & rs("belongid") & "'>" & rs("powername") & "</a>"
response.write "<br>"
'子程序调用，子层数据处理
Call ListSubPower(rs("powerid"))
rs.movenext
loop
'关闭父层数据集
rs.close
set rs=nothing
'子层数据处理子程序
Sub ListSubPower(id)
'打开隶属于上层 powerid 的所有子层数据信息
set rs_sub=Server.CreateObject("ADODB.Recordset")
rs_sub.Open "select * from powers where belongid=" & id & " order by powerid",conn,1,3
'列子层数据
do while not rs_sub.eof
'层次数表态变量递进累加
format_i=format_i+1
'循环缩进格式控制，因为顶层与二层不需要缩进，所以从第三层开始引用此程序段
for i=format_i to 3 step -1
response.write " |"
response.write " "
next
'打印子层数据信息
response.write " |----"
response.write "<a href='powerlist.asp?SelfID=" & rs_sub("powerid") & "&BelongID=" & rs_sub("belongid") &"'>" & rs_sub("powername") & "</a>"
response.write "<br>"
'递归调用子程序本身，对子层数据进行逐渐处理
ListSubPower(rs_sub("powerid"))
rs_sub.movenext
loop
'层次数表态变量递退累减
format_i=format_i-1
'关闭子层数据集
rs_sub.close
set rs_sub=nothing
End Sub
%>
powerlist.asp程序中，我们先打开顶层数据，在循环中显示出来；然后又设计一个子程序ListSubPower，通过递归算法在循环中调用，以此来打开子层数据信息，并且在子程序内部循环中又反复调用自己，以此来逐层展开深层数据。
另外，在程序中还用了一个静态变量format_i来控制缩进显示格式。
本文就树型结构在数据设计、程序控制方面做简单尝试，目的在于抛砖引玉，希望读者通过本文得到更多启示。
Top
11 楼angeldjd（邪恶天使）回复于 2004-08-05 09:31:19 得分 0
先研究一下，希望得到更多办法。Top
12 楼programmer11（程序员）回复于 2004-08-05 09:42:09 得分 0
不清楚你要做的树的级次关系，根据什么条件来定是LChild还是RChild啊Top
13 楼pfc001（pfc001）回复于 2004-08-05 13:05:22 得分 10
打开哪个节点，就读取该节点下的数据
一次读取所有记录，在本地缓存，所要做的就是用指针连接各记录
Top
14 楼angeldjd（邪恶天使）回复于 2004-08-06 08:51:18 得分 0
再顶一下。Top
15 楼superdullwolf（超级大笨狼,每天要自强,MVP）回复于 2004-08-06 09:13:46 得分 10
用xmlTop
16 楼angeldjd（邪恶天使）回复于 2004-08-09 11:24:03 得分 0
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
是一个这样的二叉树，每个结点可以看做一个用户，当我用任一用户登陆的时候我可以看到这个结点以下的所有结点。每页显层三层用户，如果最底层有用户显示下一页，如果没有显示空。谁能帮我解决啊，我可以另送200分。Top
17 楼QQgenie（妖魔鬼怪）回复于 2004-08-09 11:50:47 得分 10
传俏方式,MLM的权限管理Top
18 楼sunjiujiu（绿茶狂人@抵制日货）回复于 2004-08-09 12:29:22 得分 0
关注!Top
19 楼superdullwolf（超级大笨狼,每天要自强,MVP）回复于 2004-08-11 22:13:42 得分 0
<html>
<head>
<style>
table
{
border-collapse: collapse;
border-width: 4;
border-style: double;
border-color:#15336F;
font-size:12px;
}
body
{
font-size:12px;
}
div
{
width:100%;
height:9;
border-style:solid;
border-width:1;
border-color:#eeeeee;
vertical-align:top;
font-size:12;
cursor:hand;
}
</style>
<title>笨狼树状节点查看器</title>
</head>
<body>
<INPUT type="file" id=file1 name=file1>请输入xml文件路径
<INPUT type="button" value="确定" onclick = "vbs:analyse ">
<SELECT id="select1" >
<OPTION value="nodeName" >显示标签</OPTION>
<OPTION value="text" >显示文字</OPTION>
<OPTION value="attribute" >显示属性</OPTION>
</SELECT>
<DIV id="oList" style="padding-left:0"></DIV>
</body>
<script language="vbScript" >
'**************************************
'****作者： 超级大笨狼 superdullwolf****
'**************************************
public dic,favour,anything ,doc
favour = select1.value
set doc = CreateObject("Microsoft.XMLDOM")
doc.async=False
sub analyse()
dim myTR
favour = select1.value
removeDIV
if not doc.load(file1.value) then
alert "文件加载失败，请检查文件是否存在！"
else
Set rootNode = doc.DocumentElement
set rootDIV = document.createElement("DIV")
oList.setAttribute "XPath",rootNode.nodeName
oList.setAttribute "parsed",false
appendDIV oList,rootNode
end if
end sub
sub appendDIV(myDIV,myNode)
dim myChild ,newDIV,ChildID
ChildID = 0
for each myChild in myNode.childNodes
set newDIV = document.createElement("DIV")
myDIV.appendChild newDIV
addPx newDIV, myDIV,10
newDIV.setAttribute "XPath",getXPath(myDIV,myChild.nodeName,ChildID)
newDIV.setAttribute "parsed",false
newDIV.innerText = getText(myChild)
newDIV.title = newDIV.getAttribute("XPath")
if myChild.childNodes.length>0 then
if myChild.nodeName <> "#text" then
newDIV.attachEvent "onclick",GetRef("attachOnclick")
end if
end if
ChildID = ChildID + 1
if isobject(myChild.previousSibling) then
else
if myChild.previousSibling.nodeName <> myChild.nodeName then
ChildID =0
end if
end if
next
myDIV.setAttribute "parsed",true
end sub
function getXPath(myDIV,name,index)
getXPath = myDIV.getAttribute("XPath") & "/" & name & "[" & index & "]"
end function
sub removeDIV()
dim oldDIV
for each oldDIV in oList.childNodes
oldDIV.removeNode(true)
next
end sub
sub attachOnclick()
dim obj ,nodeXPath
set obj=window.event.srcElement
nodeXPath = obj.getAttribute("XPath")
if instr(nodeXPath,"#") then
window.event.cancelBubble = true
exit sub
end if
if not obj.getAttribute("parsed")= true then
appendDIV obj ,doc.selectSingleNode(nodeXPath)
end if
window.event.cancelBubble = true
end sub
function getText(myNode)
select case favour
case "text"
if not isnull(myNode.text) then
getText = myNode.text
else
getText = "空文字"
end if
case "nodeName"
getText = myNode.nodeName
case "attribute"
dim myAttribute
for each myAttribute in myNode.attributes
getText = "," & getText & myAttribute.value
next
if trim(getText) ="" then getText ="空" else getText = mid(getText,2)
end select
if trim(getText) ="" then getText ="空"
end function
sub addPx(newDIV,oldDIV,num)
dim re,myString
set re = new RegExp
re.Global = true
re.Pattern = "[^\d]*"
myString = re.Replace(oldDIV.style.paddingLeft, "")
if myString ="" then myString = "0"
myString = (cint(myString) + num ) & "px"
newDIV.style.paddingLeft = myString
set re = nothing
end sub
</script>
</html>Top
20 楼superdullwolf（超级大笨狼,每天要自强,MVP）回复于 2004-08-11 23:10:10 得分 0
更正
<html>
<head>
<style>
table
{
border-collapse: collapse;
border-width: 4;
border-style: double;
border-color:#15336F;
font-size:12px;
}
body
{
font-size:12px;
}
div
{
width:100%;
height:9;
border-style:solid;
border-width:1;
border-color:#eeeeee;
vertical-align:top;
font-size:12;
cursor:hand;
}
</style>
<title>笨狼树状节点查看器</title>
</head>
<body>
<INPUT type="file" id=file1 name=file1>请输入xml文件路径
<INPUT type="button" value="确定" onclick = "vbs:analyse ">
<SELECT id="select1" onchange="vbs:analyse">
<OPTION value="nodeName" >显示标签</OPTION>
<OPTION value="text" >显示文字</OPTION>
<OPTION value="attribute" >显示属性</OPTION>
<OPTION value="attributename" >显示属性名</OPTION>
<OPTION value="XPath" >显示XPath</OPTION>
</SELECT>
<DIV id="oList" style="padding-left:0"></DIV>
</body>
<script language="vbScript" >
'**************************************
'****作者： 超级大笨狼 superdullwolf****
'**************************************
public dic,favour,anything ,doc
set doc = CreateObject("Microsoft.XMLDOM")
doc.async=False
sub analyse()
dim myTR
favour = select1.value
removeDIV
if not doc.load(file1.value) then
alert "文件加载失败，请检查文件是否存在！"
else
Set rootNode = doc.DocumentElement
set rootDIV = document.createElement("DIV")
oList.setAttribute "XPath",rootNode.nodeName
oList.setAttribute "parsed",false
appendDIV oList,rootNode
end if
end sub
sub appendDIV(myDIV,myNode)
dim myChild ,newDIV,ChildID,thisID
ChildID = 0
for each myChild in myNode.childNodes
set newDIV = document.createElement("DIV")
myDIV.appendChild newDIV
addPx newDIV, myDIV,10
if ChildID>0 then
if myChild.previousSibling.nodeName <> myChild.nodeName then
ChildID =0
end if
end if
newDIV.setAttribute "XPath",getXPath(myDIV,myChild.nodeName,ChildID)
newDIV.setAttribute "parsed",false
newDIV.title = newDIV.getAttribute("XPath")
newDIV.innerText = getText(myChild,newDIV)
if myChild.childNodes.length>0 then
if myChild.nodeName <> "#text" then
newDIV.attachEvent "onclick",GetRef("attachOnclick")
end if
end if
ChildID = ChildID + 1
next
myDIV.setAttribute "parsed",true
end sub
function getXPath(myDIV,name,index)
getXPath = myDIV.getAttribute("XPath") & "/" & name & "[" & index & "]"
end function
sub removeDIV()
dim oldDIV
for each oldDIV in oList.childNodes
oldDIV.removeNode(true)
next
end sub
sub attachOnclick()
dim obj ,nodeXPath
set obj=window.event.srcElement
nodeXPath = obj.getAttribute("XPath")
if instr(nodeXPath,"#") then
window.event.cancelBubble = true
exit sub
end if
if not obj.getAttribute("parsed")= true then
appendDIV obj ,doc.selectSingleNode(nodeXPath)
end if
window.event.cancelBubble = true
end sub
function getText(myNode,oDIV)
dim myAttribute
select case favour
case "text"
if not isnull(myNode.text) then
getText = myNode.text
else
getText = "空文字"
end if
case "nodeName"
getText = myNode.nodeName
case "attribute"
for each myAttribute in myNode.attributes
getText = "," & getText & myAttribute.value
next
if trim(getText) ="" then getText ="空" else getText = mid(getText,2)
case "attributename"
for each myAttribute in myNode.attributes
getText = "," & getText & myAttribute.name
next
if trim(getText) ="" then getText ="空" else getText = mid(getText,2)
case "XPath"
getText = oDIV.title
end select
if trim(getText) ="" then getText ="空"
end function
sub addPx(newDIV,oldDIV,num)
dim re,myString
set re = new RegExp
re.Global = true
re.Pattern = "[^\d]*"
myString = re.Replace(oldDIV.style.paddingLeft, "")
if myString ="" then myString = "0"
myString = (cint(myString) + num ) & "px"
newDIV.style.paddingLeft = myString
set re = nothing
end sub
</script>
</html>Top
21 楼superdullwolf（超级大笨狼,每天要自强,MVP）回复于 2004-08-11 23:32:17 得分 0
再更正：
<html>
<head>
<style>
table
{
border-collapse: collapse;
border-width: 4;
border-style: double;
border-color:#15336F;
font-size:12px;
}
body
{
font-size:12px;
}
div
{
width:100%;
height:9;
border-style:solid;
border-width:1;
border-color:#eeeeee;
vertical-align:top;
font-size:12;
cursor:hand;
}
</style>
<title>笨狼树状节点查看器</title>
</head>
<body>
<INPUT type="file" id=file1 name=file1>请输入xml文件路径
<INPUT type="button" value="确定" onclick = "vbs:analyse ">
<SELECT id="select1" onchange="vbs:analyse">
<OPTION value="nodeName" >显示标签</OPTION>
<OPTION value="text" >显示文字</OPTION>
<OPTION value="attribute" >显示属性</OPTION>
<OPTION value="XPath" >显示XPath</OPTION>
</SELECT>
<DIV id="oList" style="padding-left:0"></DIV>
</body>
<script language="vbScript" >
'**************************************
'****作者： 超级大笨狼 superdullwolf****
'**************************************
public dic,favour,anything ,doc
set doc = CreateObject("Microsoft.XMLDOM")
doc.async=False
sub analyse()
dim myTR
favour = select1.value
removeDIV
if not doc.load(file1.value) then
alert "文件加载失败，请检查文件是否存在！"
else
Set rootNode = doc.DocumentElement
set rootDIV = document.createElement("DIV")
oList.setAttribute "XPath",rootNode.nodeName
oList.setAttribute "parsed",false
appendDIV oList,rootNode
end if
end sub
sub appendDIV(myDIV,myNode)
dim myChild ,newDIV,ChildID,thisID
ChildID = 0
for each myChild in myNode.childNodes
set newDIV = document.createElement("DIV")
myDIV.appendChild newDIV
addPx newDIV, myDIV,10
if ChildID>0 then
if myChild.previousSibling.nodeName <> myChild.nodeName then
ChildID =0
end if
end if
newDIV.setAttribute "XPath",getXPath(myDIV,myChild.nodeName,ChildID)
newDIV.setAttribute "parsed",false
newDIV.title = newDIV.getAttribute("XPath")
newDIV.innerText = getText(myChild,newDIV)
if myChild.childNodes.length>0 then
if myChild.nodeName <> "#text" then
newDIV.attachEvent "onclick",GetRef("attachOnclick")
end if
end if
ChildID = ChildID + 1
next
myDIV.setAttribute "parsed",true
end sub
function getXPath(myDIV,name,index)
getXPath = myDIV.getAttribute("XPath") & "/" & name & "[" & index & "]"
end function
sub removeDIV()
dim oldDIV
for each oldDIV in oList.childNodes
oldDIV.removeNode(true)
next
end sub
sub attachOnclick()
dim obj ,nodeXPath
set obj=window.event.srcElement
nodeXPath = obj.getAttribute("XPath")
if instr(nodeXPath,"#") then
window.event.cancelBubble = true
exit sub
end if
if not obj.getAttribute("parsed")= true then
appendDIV obj ,doc.selectSingleNode(nodeXPath)
end if
window.event.cancelBubble = true
end sub
function getText(myNode,oDIV)
dim myAttribute
getText = ""
select case favour
case "text"
if not isnull(myNode.text) then
getText = myNode.text
else
getText = "空文字"
end if
case "nodeName"
getText = myNode.nodeName
case "attribute"
if myNode.nodeName <>"#text" then
for each myAttribute in myNode.attributes
getText =getText & myAttribute.name
getText = getText & "=" & chr(34)
getText = getText & myAttribute.value & chr(34) & " "
next
getText = trim(getText)
end if
case "XPath"
getText = oDIV.title
end select
if trim(getText) ="" then getText ="空"
end function
sub addPx(newDIV,oldDIV,num)
dim re,myString
set re = new RegExp
re.Global = true
re.Pattern = "[^\d]*"
myString = re.Replace(oldDIV.style.paddingLeft, "")
if myString ="" then myString = "0"
myString = (cint(myString) + num ) & "px"
newDIV.style.paddingLeft = myString
set re = nothing
end sub
</script>
</html>Top
22 楼xjdawu（无法界定）回复于 2004-08-12 15:00:58 得分 0
静态变量format_i在递归里面的自加（format_i=format_i+1）应该放在遍历记录集之前
Top
