#树算法#最奇葩的PYTHON代码
请查看原文：http://www.ibaiyang.org/2012/12/09/%E6%A0%91%E7%AE%97%E6%B3%95%E6%9C%80%E5%A5%87%E8%91%A9%E7%9A%84python%E4%BB%A3%E7%A0%81/
这一个月是最苦逼的日子，因为在深圳先进研究院的最后实习的日子里，我和我导师在为了siggraph奋斗着，也希望能在本科阶段发上一篇论文，哈哈。
空闲之余，来分享一下研究过程中用到的一个树的算法吧。本算法的目的非常简单，就是剔除树的中间节点，保留分支节点。如下图要求：
http://www.ibaiyang.org/wp-content/uploads/2012/12/original-259x600.png
转化如下
http://www.ibaiyang.org/wp-content/uploads/2012/12/reduced.png
以上图是由http://www.graphviz.org/doc/info/lang.html生成
附上代码：
view plaincopy to clipboardprint?
[*]def reduced_graph(subtree, v, graph):
[*] n = graph
[*] if len(n) == 0:
[*] v = []
[*] return
[*] elif len(n) == 1: #one child
[*] r = reduced_graph(n, v, graph)
[*] v = r
[*] if len(v]) == 1:
[*] del v]
[*] return v
[*] else:
[*] next_sub = []
[*] for c in n:
[*] r = reduced_graph(c, v, graph)
[*] next_sub.append(r)
[*] if len(v) == 1:
[*] del v
[*] v = next_sub
[*] return
调用方法：
view plaincopy to clipboardprint?
[*]v = {}
[*]graph = {0:, 1:, 2:, 3:, 4:, 5:, 6:, 9:[], 7:, 11:[], 8:[]}
[*]root = 0
[*]reduced_graph(root, v, graph)
图表示方法是：邻接矩阵表示法。
为什么说这个python代码非常奇怪呢，因为reduced_graph函数本身也返回值，其实参数V也是返回值。等项目结束后，希望能重构一下这个奇葩的代码。
在过程中还发现 len(n) == 0 没有 n==[] 高效，我也测试了二者的代码，后者快了N倍，可能是由于函数调用开销比较大吧。
-----------------打造高质量的文章 更多关注 把酒泯恩仇---------------
为了打造高质量的文章，请 推荐 一下吧。。。。谢谢了，请关注我后续的文章，会更精彩哦
请关注sina微博：http://weibo.com/baiyang26
把酒泯恩仇官方博客：http://www.ibaiyang.org 【推荐用google reader订阅】
把酒泯恩仇官方豆瓣：http://www.douban.com/people/baiyang26/
如果您想转载本博客，请注明出处
如果您对本文有意见或者建议，欢迎留言
页:
[1]