这是我的论坛某一篇回复。虽然与楼主要求不一致,但这种结构在实际开发中很常见,比较有代表意义,因此收入博客。
原问题是这样的
有一字符串,格式为
1,2@1,3@1,7@2@1,5@1,12@9@1,16@10@5@1
上面字符串每个逗号分隔开的单独部分都是一颗树形结构的层级关系表示。比如说5@1是说自己的节点id为5,父级节点id为1.其他类似。
问题是,怎么根据上面一个字符串构建出该字符串对应的tree来。
由此题扩展,回想起我3年前开发过的一个报表功能
该种报表是为了统计各部门盈利状况。其中各个部门之间有从属关系,类似于原题中的2@1;每个叶子部门在数据库中会有当月收入多少,支出多少这样的字段;然后统计出树状报表;来判断该酒店当月盈利亏损与否,与盈利亏损额多少。当时开发的时候采用的从叶子节点递推到根节点的方式。
与上面的报表应用场景不同的是,我如下的递归算法在MENU多级展开上有一定的适用性。总之思路类似。
package test;
import java.util.HashSet;
import java.util.Set;
public class Node {
public Node parent;
public String value;
public Set<Node> childs = new HashSet<Node>();
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((value == null) ? 0 : value.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (value == null) {
if (other.value != null)
return false;
} else if (!value.equals(other.value))
return false;
return true;
}
@Override
public String toString() {
return "Node [childs=" + childs + ", parent=" + parent + ", value="
+ value + "]";
}
}
package test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
public class Main {
public Node root;
private List<Node> nodes = new ArrayList<Node>();
public void init(String str) {
String[] strs = str.split(",");
for (int i = 0; i < strs.length; i++) {
int index = strs[i].indexOf("@");
if (index == -1) {
root = new Node();
root.value = strs[i];
nodes.add(root);
} else {
String[] ns = strs[i].split("@");
for (int j = 0; j < ns.length; j++) {
Node node = new Node();
node.value = ns[j];
if (!nodes.contains(node)) {
nodes.add(node);
}
}
create(Arrays.asList(ns), 0);
}
}
print(root, "");
}
public void print(Node node, String str) {
System.out.println(str + node.value);
for (Iterator<Node> iterator = node.childs.iterator(); iterator
.hasNext();) {
Node child = iterator.next();
print(child, leftPad(str));
}
}
public String leftPad(String str) {
return "--" + str;
}
public Node create(List<String> list, int index) {
Node node = null;
if (index < list.size()) {
node = getNodeByStr(list.get(index));
if (node.parent == null) {
node.parent = create(list, ++index);
}
if (node.parent != null) {
node.parent.childs.add(node);
}
}
return node;
}
public Node getNodeByStr(String str) {
for (int i = 0; i < nodes.size(); i++) {
Node node = nodes.get(i);
if (node.value.equals(str)) {
return node;
}
}
throw new RuntimeException("not such node " + str);
}
public static void main(String[] args) {
String str = "1,2@1,3@1,7@2@1,5@1,12@9@1,16@10@5@1";
new Main().init(str);
}
}
分享到:
相关推荐
动态规划算法 数据结构 最优算法 动态规划算法 数据结构 最优算法 动态规划算法 数据结构 最优算法
该代码很好的实现了用遗传算法寻优最优路径问题
寻找最短路径算法,进行多种算法叠加,选择最优算法,最快算法. 通过形成距阵.
RMS算法是最优算法的证明。 1.证明:RMS是最优算法 RMS的由来是从硬实时环境的初始定义开始的。
最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法
飞思卡尔智能小车光电组必备材料,有关于路径识别和PID算法的讨论!
程序还需要你自己编写,这只不过是一个指导性的公式,思路清晰,相信对于掌握基本的编程技术的朋友来说编写比较简单。
基于全局最优算法的应用研究,刘洋,,盲源分离算法大多计算复杂、迭代步多。针对该问题,本文研究了无须迭代的全局最优盲源分离算法,首先在非高斯源信号混合时使用该
算法分析作业答案:求最大娄与次大数的最优算法 题目:给定n个实数,试设计一人算法。。。
分算法二是在约束线上插入点时应用取三角形外接圆与特征线交点的方法并行剖分算法具有较好的加速性能"交点"插入算法考虑了 特征线的影响域及Delaunay三角形规则的边界条件在满足全局Delaunay三角剖分的前提下使插入...
彩票3D 的最优算法,用c#语言开发。包括复式算法(无重复算法) 、 组3全包、 组6全包等方法
百鸡问题最优算法,可以输入三个变量,并解出最优解
算法设计 horspool算法 最优 最差输入算法设计 horspool算法 最优 最差输入算法设计 horspool算法 最优 最差输入算法设计 horspool算法 最优 最差输入算法设计 horspool算法 最优 最差输入算法设计 horspool算法 ...
模型算法大全:最优化算法(6份),供大家学习参考: MATLAB优化工具箱.ppt 优化模型.ppt 数学建模:最优化模型(课件ppt).ppt 最优化方法及其Matlab程序设计.pdf 最优化方法课件.ppt 最优化算法.pdf
最优二叉树 最优二叉树算法
求马步图Hamilton圈的最优算法,非常好的一个算法
Essentials of Metaheuristics,用于最优算法的,很有用的东西,好好看看吧
2.内容:基于Qlearning算法最优路径规划算法matlab仿真,同时使用A星算法进行对比+代码操作视频 3.用处:用于Qlearning算法,A星算法编程学习 4.指向人群:本硕博等教研学习使用 5.运行注意事项: 使用matlab...
基于电子地图的路径最优算法研究,caj文件。
二分图最优算法KM 计算二分图最优匹配的目前最高效算法