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

香川群子

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

最长路经必然经过根节点，但这个根节点不一定是=1（最初的父节点）

如：
       1
      /   \
     2     3
    /  \
   4   5
  /  \    \  
6    7    8
    /      /  \  
   9     10 11  

此图中，以2为根节点时，9-10 以及 9-11 距离都是=6
而经过父节点1的 3-10 和3-11的距离只是=5
…………
补充：
上图中，以2为根节点时，3和6、7、8等距离。

因此，可以认为最终结果（距离最大）的情形是：
以整个树中某一个点为根节点时，其中独立路径最大的两个末端节点之间的距离，即为楼主所求答案。
所谓独立路径是指：这两个末端节点之间必须通过这个特定的根节点，而不存在其它更短的路径相通。

呵呵。

香川群子

lee1892 发表于 2014-11-8 00:34
3、距离根节点最远的两个节点间是否距离最远？

距离根节点最远的两个节点间是否距离最远？

答： 不是，而且有可能是距离最近的。

如：
     上面省略
       /   
       8
    /     \  
   9     10  

9和10距离1最远，但9和10最近。

香川群子

楼主最好提供几个较大的树（即4;1,2;1,3;2,4 格式的 文本输入字符串）

然后在此基础上思考代码。

kangatang

不限于二叉树

lee1892

香川群子 发表于 2014-11-13 09:15
楼主最好提供几个较大的树（即4;1,2;1,3;2,4 格式的 文本输入字符串）

然后在此基础上思考代码。

暂不提供，自己琢磨琢磨先～

香川群子

根据11楼的分析，目前的初步结论是：

从每一个末端节点（只有一对父子关系）出发，各自向上（父级）回溯，
每到出现共同的节点时，就淘汰这一对端末节点……直到剩下最后一对。
则这一对端末节点，肯定是路径最大的一对，而这最后出现的共同节点，就是它们的根节点。（不一定是=1）

以上。

但是代码实现起来可能仍很困难。很多问题需要进一步思考。

lee1892

下述代码可以按题目格式生成一个随机树的字符串

1. Function RandomTree$()
   
2.     Dim nCnt%, i%, nInd%, nLast%, nChildNumMax%
   
3.     nCnt = Int(Rnd * 10000) + 1
   
4.     nChildNumMax = 10
   
5.     nInd = 1: nLast = 1: RandomTree = CStr(nCnt)
   
6.     Do
   
7.         For i = 1 To Int(Rnd * nChildNumMax) + 1
   
8.             nLast = nLast + 1
   
9.             If nLast > nCnt Then Exit Do
   
10.             RandomTree = RandomTree & ";" & CStr(nInd) & "," & CStr(nLast)
    
11.         Next
    
12.         nInd = nInd + 1
    
13.     Loop
    
14. End Function

复制代码

香川群子

改造为工作表单元格内可以直接引用的易失性随机函数：

1. Function RandomTree$(Optional nCnt% = 0)
   
2.     Dim i%, nInd%, nLast%, nChildNumMax%
   
3.     Application.Volatile
   
4.     If nCnt = 0 Then nCnt = Int(Rnd * 10000) + 1
   
5.     nChildNumMax = 10
   
6.     nInd = 1: nLast = 1: RandomTree = CStr(nCnt)
   
7.     Do
   
8.         For i = 1 To Int(Rnd * nChildNumMax) + 1
   
9.             nLast = nLast + 1
   
10.             If nLast > nCnt Then Exit Do
    
11.             RandomTree = RandomTree & ";" & CStr(nInd) & "," & CStr(nLast)
    
12.         Next
    
13.         nInd = nInd + 1
    
14.     Loop
    
15. End Function

复制代码

yiyiyicz

香川群子 发表于 2014-11-13 08:58
最长路经必然经过根节点，但这个根节点不一定是=1（最初的父节点）

如：

根据一楼的定义
“由一个节点到另一个节点所经过的不重复的边的数量---相距最远的两个节点的距离”
最长路经必然经过根节点的结论不对---最长路径中同一条边不能出现两次

根节点在树形结构是固定的。除非有其它的定义

yiyiyicz

这题意义不大
用现成的方法，用深度优先遍历，找没有兄弟的分支；用广度优先，排除公共边
或者将数据转到XML中，用Xpath也可以。
用邻接矩阵也可以，正好满足“根结点”任意变化的意思。VBA做10000个结点的邻接矩阵也受得了
10000个结点需要遍历，
主要的是设计算法巧妙，能节省时间

用邻接矩阵大概最合适，“根结点”可以任意拓扑，矩阵又适合模型讨论，矩阵方法灵活多变。这个思路最适合
编程正好也能用到“继承”，多层继承，用类模块实现回调函数