来个难度高点的：用最快的方法找出一个树内距离最远的两个节点间的距离

lee1892

yiyiyicz 发表于 2014-11-23 09:08
接58楼，58楼编辑太困难了
看红色虚线内，也就是第一步
分析压缩后的三个结点，他们的路径长度只可能有三 ...

真是大手笔呀！前半部分我大致看明白了，可要是一个完全树，这前面的都用不上啊。

对了，所谓完全树是指节点处分支数量固定，比如2个或者3个或者别的数量，对所有节点要么其子节点数量为零要么为这个固定的数量。

接下来这个一圈一圈去找还是不能理解呀，这树里木有圈呀～

嗯，代码越短越是有漏洞！又学到一招。

yiyiyicz

lee1892 发表于 2014-11-23 09:56
真是大手笔呀！前半部分我大致看明白了，可要是一个完全树，这前面的都用不上啊。

对了，所谓完全树是 ...

叶节点，是网络最外围了。这不就构成一个圈子吗？比较抽象，这个圈子不圆。
树形图，是网络图的一种。
你说的对，树形图中不能有“环”，也就是无环图。一般不叫圈

可以大略的想～
树形图，也是网络图的一种
叶节点，是可以清楚定义的一种结点，他们处于网络的最外
按照前面的叙述，处理一个叶节点，就向网络内部深入了一步，而且露出新的叶节点
旧的叶节点删除之后，新的叶节点又组成了新的外围
随着叶节点一圈一圈的除掉，最后就逼近了网络的核心。这个核心可能不只一个
所以，还要记录处理过的结点。防止从左面处理一次后，再从右面再处理一次

树形图在压缩后，不再变型，将简化不少

lee1892

yiyiyicz 发表于 2014-11-23 10:16
叶节点，是网络最外围了。这不就构成一个圈子吗？比较抽象，这个圈子不圆。
树形图，是网络图的一种。 ...

这可不能大略的想，一定要想清楚想明白的~

要接着讲解逼近了网络的核心以后还要做些什么，毕竟这是要找出两个距离最远的节点间的距离，到目前为止我还没弄明白这距离值在哪~

继续继续~

树形图不再变形是好事呀！

yiyiyicz

用代理（回调函数）的方法实现继承的帖子在这里
http://club.excelhome.net/thread-1142863-1-1.html

这不是多态，是函数调用函数，利用委托方式实现继承
其中被调用的函数，应该是一种地址，而在程序中并没有显式给出，符合VBA的推荐
要想实现多重继承，这种方法+关系矩阵
具体到解决楼主的问题，用自上而下的方式，计算出路径长度。
压缩后的树形图，非叶节点下有若干个结点，处理的方式可以写成函数或者对象
而关系矩阵就是前面说的邻接矩阵
这样，就可以用继承的方法计算出来了。代码少
切记，树形图的特点，每个结点只能有一个父节点。正是因为这个特点，所以树形图不会存在环；因此，编程可以简化。不用网络变型也简单
之前的XML树的方法，是自下而上。那个方法更简单

lee1892

yiyiyicz 发表于 2014-11-25 17:13
用代理（回调函数）的方法实现继承的帖子在这里
http://club.excelhome.net/thread-1142863-1-1.html

这…这又是一堆…

距离值到底在哪呢？我咋越看越晕啊～？

太深了！～

还是直接说一楼的题目怎么找到距离最远的两个节点间的距离值吧！

yiyiyicz

lee1892 发表于 2014-11-25 19:31
这…这又是一堆…

距离值到底在哪呢？我咋越看越晕啊～？

“怎么找到距离最远的两个节点间的距离值”
前面讲的自底向上的方法，已经说的很清楚了，概念清楚，逻辑清楚，只差编程了。注意树形图的特点：任意结点只能有一个父节点（根结点除外），因此不可能成环；任意两个叶节点之间的通路只能有一条（按照要求，通路不能有公共边，也就是同一条边不能走两次及以上），同理从根结点到任意叶节点之间的通路也只能有一条。
关于两个叶节点之间路径长度、结点列表的结果放在哪里的问题。前面多次讲过，放在结点的属性里。XML结点属性可以有n个，并且可以添加、删除、修改；同理，XML结点也可以添加、删除、修改。这些在MSXML中都有说明，也就是编程没有问题。
矩阵方法是可行的，但是计算量比较大，而且10000个结点的矩阵能不能用VBA代码来计算，也就是10000X10000的矩阵计算，这还真不知道
代码，等有时间再写

"所谓完全树是指节点处分支数量固定，比如2个或者3个或者别的数量，对所有节点要么其子节点数量为零要么为这个固定的数量。"
这些概念不是很清楚，二叉树的定义好像是每个结点不能超过两个子节点。
按照一楼的说法，树形图是随机生成的。只要满足树形图的定义，如何生成还有限制吗？我画的树形图是图省事，对于分叉没有刻意限定
为了大家不要南辕北辙，能得出正确的结果，你还真得认认真真的给出定义

lee1892

yiyiyicz 发表于 2014-11-27 07:50
“怎么找到距离最远的两个节点间的距离值”
前面讲的自底向上的方法，已经说的很清楚了，概念清楚，逻 ...

第一段，只好等您代码了，实在是我觉得看代码肯定比看您文字描述更容易些。

第二段，举这个完全树的例子是为了告诉你，你之前提到的什么压缩节点的步骤，对于完全树没有意义。题目没有限制树的形式，那么完全树作为一个特例满足题目要求。
让您为此疑惑实在怪我没解释清楚，我本以为下面这个逻辑是不言自明的：如果一个算法中的一部分对于问题中的某特例没有任何作用，那这部分的存在价值是有待商榷的。

yiyiyicz

看树形图，严格按照任意结点只有一个父节点（除根结点）

jsxjd

lee1892 发表于 2014-11-7 12:17
2，最长路经是否必然经过根节点？

这个概念根节点是不明确的
同一分支不必经过根节点

yiyiyicz

1. Sub t02()
   
2. '** 添加引用 microsoft xml v6.0 **
   
3. Dim Arr, nrr
   
4. Dim Dic, K, T
   
5. Dim Tt As New MSXML2.DOMDocument, Rt As IXMLDOMElement, Ndt As IXMLDOMElement, Nlt As IXMLDOMNode
   
6. Dim Nlist As MSXML2.IXMLDOMNodeList
   
7. Dim Routelist As String, Routemax As Integer, Tempmax As Integer
   
8.     Set Tt = CreateObject("msxml2.domdocument")
   
9.     Tt.setProperty "SelectionLanguage", "XPath"
   
10.     lastrow = Sheet1.Range("a65536").End(xlUp).Row
    
11.     Arr = Sheet1.Range("a2:c" & lastrow)
    
12.     Set Tt = New MSXML2.DOMDocument
    
13.     Set Rt = Tt.createElement("xmltree")
    
14.     Set Tt.documentElement = Rt '//xml树之根节点
    
15.    
    
16.     '=== 建立xml树 ===
    
17.     Set Ndt = Tt.createElement("s" & Arr(1, 1)) '//添加树形图根节点“1”。由于xml的原因，自然数前要加字母变为“s1”
    
18.     Call Ndt.setAttribute("edge", "10") '//设定相邻两结点之间的边长（属性）
    
19.     Call Ndt.setAttribute("route", "s1") '//设定路径属性，记录路径上的所有结点
    
20.     Call Ndt.setAttribute("tleaf", "tt") '//设定叶结点属性，初始标注为叶结点
    
21.     Call Ndt.setAttribute("branchedge", "0") '存叶结点之间的最大路径长度
    
22.     Call Ndt.setAttribute("branchroute", "") '存叶结点之间的最大路径长度的结点编号集合
    
23.     Rt.appendChild Ndt
    
24.     For i = 1 To UBound(Arr) '添加所有的子节点
    
25.         tempt = "s" & Arr(i, 1)
    
26.         Set Nlist = Tt.getElementsByTagName(tempt)
    
27.         If Nlist.Length > 1 Then MsgBox "结点重复": Exit Sub
    
28.         Set Rt = Nlist.Item(0)
    
29.         Rt.removeAttribute ("tleaf") '//删除标注为叶节点属性
    
30.         Call Rt.setAttribute("fleaf", "ff") '//新增非叶结点的属性，是为非叶结点的标识
    
31.         Set Ndt = Tt.createElement("s" & Arr(i, 2))
    
32.         Rt.appendChild Ndt
    
33.         Call Ndt.setAttribute("edge", Arr(i, 3)) '由根节点到叶结点的累加路径长度
    
34.         Call Ndt.setAttribute("route", "s" & Arr(i, 2)) '结点编号（存结点编号集合）
    
35.         Call Ndt.setAttribute("tleaf", "tt") '标识叶结点
    
36.     Next i
    
37.     'Tt.Save "F:\creatxml.xml"'##调试用
    
38.    
    
39.     '=== 处理xml树，找最长路径 ===
    
40.     Set Nlist = Tt.selectNodes("//*[@tleaf]") '列出叶叶结点集合，属性为tleaf的元素结点。此处为Xpath语句
    
41.     '====== 逐层、逐个处理叶结点 ======
    
42.     Do Until Nlist.Length = 1 '当只剩一个tleaf属性时，逐层、逐个处理叶结点过程结束
    
43.         Set Dic = CreateObject("Scripting.Dictionary")
    
44.         For Each Nlt In Nlist '该循环后，得到叶结点的父结点的子结点数量。如果叶结点的父结点的子结点数量多于叶结点的数量，暂不处理
    
45.             Dic(Nlt.parentNode.nodeName) = Dic(Nlt.parentNode.nodeName) + 1 '叶结点的父结点出现的次数，即叶结点的父结点的子结点数量
    
46.         Next
    
47.         For Each Nlt In Nlist '该循环后，保留符合处理条件的叶结点的父结点
    
48.             Set Nlist = Nlt.parentNode.childNodes '叶结点的兄弟结点集合
    
49.             If Dic.Exists(Nlt.parentNode.nodeName) Then
    
50.                 If Not Dic(Nlt.parentNode.nodeName) = Nlist.Length Then '叶结点的父结点的子结点的数量不等于叶结点的父结点出现的次数
    
51.                     Dic.Remove (Nlt.parentNode.nodeName) '删除该父结点，因为它的子节点数量不等于叶结点数量
    
52.                 End If
    
53.             End If
    
54.         Next
    
55.         K = Dic.keys
    
56.         For Each k1 In K
    
57.             Set Rt = Tt.getElementsByTagName(k1).Item(0) '找叶结点的父结点
    
58.             If Not Rt Is Nothing Then
    
59.                 Set Nlist = Rt.childNodes
    
60.                 Routemax = 0
    
61.                 Tempmax = 0
    
62.                 '==== 累加结点间的路径长度，添加路径结点集合 ====
    
63.                 For i = 1 To Nlist.Length - 1 '两层循环为找最长路径
    
64.                     For j = i + 1 To Nlist.Length
    
65.                         Tempmax = CInt(Rt.childNodes(i - 1).Attributes(0).nodeValue) _
    
66.                             + CInt(Rt.childNodes(j - 1).Attributes(0).nodeValue)
    
67.                         If Tempmax > Routemax Then
    
68.                             Routemax = Tempmax '最长路径值记入中间变量
    
69.                             Routelist = ""
    
70.                             Routelist = Rt.childNodes(i - 1).Attributes(1).nodeValue & Rt.childNodes(j - 1).Attributes(1).nodeValue   '最长路径路过的结点
    
71.                         End If
    
72.                     Next j
    
73.                 Next i
    
74.                 If CInt(Tt.getElementsByTagName("s1").Item(0).Attributes(2).nodeValue) < Routemax Then  '比较已有的
    
75.                     Tt.getElementsByTagName("s1").Item(0).Attributes(2).nodeValue = Routemax '最长路径值存入根结点属性中
    
76.                     Tt.getElementsByTagName("s1").Item(0).Attributes(3).nodeValue = Routelist '最长路径路过的结点存入根结点属性中
    
77.                 End If
    
78.                 Routemax = 0
    
79.                 Routelist = ""
    
80.                 '==== 累加根结点到叶结点间的路径长度，添加路径结点集合 ====
    
81.                 For i = 0 To Nlist.Length - 1
    
82.                     'MsgBox Rt.childNodes(i).Attributes(0).nodeValue & "," & Rt.childNodes(i).Attributes(0).nodeName & "," & Rt.childNodes(i).nodeName
    
83.                     If CInt(Rt.childNodes(i).Attributes(0).nodeValue) > Routemax Then
    
84.                         Routemax = Rt.childNodes(i).Attributes(0).nodeValue
    
85.                         Routelist = ""
    
86.                         Routelist = Rt.childNodes(i).Attributes(1).nodeValue
    
87.                     End If
    
88.                 Next i
    
89.                 Rt.Attributes(0).nodeValue = Rt.Attributes(0).nodeValue + Routemax
    
90.                 Rt.Attributes(1).nodeValue = Routelist & Rt.Attributes(1).nodeValue
    
91.                 '==== 删除处理过的叶节点并修改其父结点的非叶结点的标识为叶结点 ====
    
92.                 Rt.removeAttribute ("fleaf")
    
93.                 Call Rt.setAttribute("tleaf", "tt")
    
94.                 For i = 0 To Nlist.Length - 1
    
95.                     Set Ndt = Rt.childNodes(0) '注意：childNodes的Index只能设置为0
    
96.                     Call Ndt.parentNode.removeChild(Ndt)
    
97.                     Set Ndt = Nothing
    
98.                 Next i
    
99.             End If
    
100.         Next
     
101.         Tt.Save "F:\creatxml.xml"
     
102.         Set Nlist = Tt.selectNodes("//*[@tleaf]")
     
103.         Set Dic = Nothing
     
104.     Loop
     
105.     'Tt.Save "F:\creatxml.xml"'##调试用
     
106.     '比较"根节点到叶结点的累加路径长度"(edge)与"叶结点之间的最大路径长度"(branchedge)，谁大
     
107.     If CInt(Rt.Attributes(0).nodeValue) > CInt(Rt.Attributes(2).nodeValue) Then
     
108.         MsgBox Space(4) & "最大路径长度" & Chr(10) & Space(10) & Rt.Attributes(0).nodeValue _
     
109.             & Chr(10) & Space(4) & "最大路径结点集合列表" & Chr(10) & Space(10) & Rt.Attributes(1).nodeValue
     
110.     Else
     
111.         MsgBox Space(4) & "最大路径长度" & Chr(10) & Space(10) & Rt.Attributes(2).nodeValue _
     
112.             & Chr(10) & Space(4) & "最大路径结点集合列表" & Chr(10) & Space(10) & Rt.Attributes(3).nodeValue
     
113.     End If
     
114. End Sub
     

复制代码