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

yiyiyicz

代码见70楼，图见68楼
测试见附件

思路描述看前面的回帖。用的是自下而上的方式
最大路径长度为103，路径经过的结点26,24,21,19,3,4,5,7,11。也就是两个叶结点26,11之间的路径，经过根结点1
树形图是随意画的，这个结果不代表最长路径一定要结果根结点1。比如可以把叶节点或者中间结点边的权值加大，就可以看到不需要经过根结点的最长路径。
代码只是找出一条最长路径。修改后，也可以找出所有的最大路径，及其所有路径
代码是用msxml写的。基本上没用XPath语句（用XPath的地方已经标出，这个也可以不用）。代码还可以加速
忘了说明：代码中没有加压缩树形图功能。如果会msxml，这个不难
这样，似乎需要修改代码才能适应没有压缩的树形图。不过这样将大大增加代码执行速度
所以，修改代码时注意要用压缩后的树形图
所谓压缩，就是把没有分叉的结点，统统用边的权值代表

调试时可以变更附件的sheet1中A/B两列的数据，观察结果。切记，修改数据不可违反树形图的规则
sheet1右侧的数据是调试中记录下来的，可以参考
附件
xmltree.rar (60.95 KB, 下载次数: 58)

2014-12-5 18:10 上传

点击文件名下载附件

lee1892

yiyiyicz 发表于 2014-12-5 16:55

你最好用17楼、34楼、35楼的代码作为树的输入，这样容易对比。

yiyiyicz

lee1892 发表于 2014-12-5 17:23
你最好用17楼、34楼、35楼的代码作为树的输入，这样容易对比。

我没有看出你所说的符合树形图的规则
而且35楼的下头有人指出了问题
“一个儿子怎么能有两个爸爸”
一定要遵守：一个结点只能有一个父结点

yiyiyicz

上面的代码，似乎应该检查：父结点有几个

lee1892

yiyiyicz 发表于 2014-12-5 18:15
上面的代码，似乎应该检查：父结点有几个

很简单呀，你就认为一个连接里，数字小的那个是父节点好了。

yiyiyicz

lee1892 发表于 2014-12-5 18:33
很简单呀，你就认为一个连接里，数字小的那个是父节点好了。

如果这样，你就按照sheet1中，父子关系的格式（A/B两列），生成数据（参考那张图）
如果不熟悉MSXML，可以用treeview控件，把没有分叉的统统转换成边的权值，然后用我的代码算一下，看看结果对不对

yiyiyicz

这个代码不困难吧，几乎没有XPath
如果是算一下，下载附件，在sheet1中放入数据就可以了
其实，你需要的是测试你的想法。只用随机生成的数据，怎么会正好符合一些极端的设想呢？
如果说要测试速度，那就是另外的事情了
我的代码，如果有一连串的没有分叉的结点，会出错。这时可以修改代码，在两层for循环之前改一下父节点下子节点集合那里改；或者把两层for循环改成一层，仅仅比较子节点的edge属性值大小，一层循环需要功夫了，这里就可以把没有分叉的结点考虑进去；或者在生成xml树后面，再处理压缩
前面的树生成代码，不能保证所有结点只有一个父节点

yiyiyicz

我的代码有错误，坐等证明！
没工夫陪你

lee1892

yiyiyicz 发表于 2014-12-6 17:02
我的代码有错误，坐等证明！
没工夫陪你

这不是你的原话吗？

我的代码，如果有一连串的没有分叉的结点，会出错。

你这爱好还真是......口味独特的紧

我是不是应该说求求你陪陪我嘛？

龙城飞将III

好精彩的论战！{:soso_e163:}