答复: java最优算法讨论

这是我的论坛某一篇回复。虽然与楼主要求不一致，但这种结构在实际开发中很常见，比较有代表意义，因此收入博客。
原问题是这样的

有一字符串，格式为
   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);
	}
}

评论

1 楼 yangguo 2010-09-07  

用我的study方法就可以了。