高分求救查询树形结构中某节点逆展开所有路径问题
比如有一个表结构
id parent child
A 1 3
B 2 3
C 3 4
D 5 4
E 6 4
F 7 5
G 8 4
如何取得所有root节点到节点4的所有路径的id
放到map中，key为parent，value为list<id>
如上表应该有5条路径
1) 1 > 3 > 4 map.put(1 : C,A)
2) 2 > 3 > 4 map.put(2 : C,B)
3) 7 > 5 > 4 map.put(7 : F,D)
4) 6 > 4 map.put(6 : E)
5) 8 > 4 map.put(8 : G)
请大家帮忙解决一下，谢谢了。。。
[最优解释]
Map<Integer, List<String>> result = new HashMap<Integer, List<String>>();
Map<Integer, Integer> temp1 = new HashMap<Integer, Integer>();
temp1.put(1, 3);
temp1.put(2, 3);
temp1.put(3, 4);
temp1.put(5, 4);
temp1.put(6, 4);
temp1.put(7, 5);
temp1.put(8, 4);
Map<Integer, Integer> temp2 = new HashMap<Integer, Integer>();
temp2.put(3, 1);
temp2.put(3, 2);
temp2.put(4, 3);
temp2.put(4, 5);
temp2.put(4, 6);
temp2.put(5, 7);
temp2.put(4, 8);
Map<Integer, String> temp3 = new HashMap<Integer, String>();
temp3.put(1, "A");
temp3.put(2, "B");
temp3.put(3, "C");
temp3.put(5, "D");
temp3.put(6, "E");
temp3.put(7, "F");
temp3.put(8, "G");
Iterator<Integer> it = temp1.keySet().iterator();
while (it.hasNext()) {
Integer pid = it.next();
if (!temp2.containsKey(pid)) {
List<String> list = new ArrayList<String>();
result.put(pid, list);
list.add(temp3.get(pid));
Integer id = temp1.get(pid);
while (temp1.containsKey(id)) {
list.add(temp3.get(id));
id = temp1.get(id);
}
}
}
System.out.println(result);
result:{2=[B, C], 8=[G], 6=[E], 1=[A, C], 7=[F, D]}
为啥结果会不同？
[其他解释]
这种存储方式就是一个简单的链接表存储图的顶点和边，当然可以使用图搜索算法。
但是由于问题的简单性，可以直接使用深度搜索到目标的路径。
package com.tur.demo;
import java.util.*;
public class Hello {
public static void main(String[] args) {
/*
id parent next
A 1 3
B 2 3
C 3 4
D 5 4
E 6 4
F 7 5
G 8 4
*/
List<String> paths = new ArrayList<String>();
Pair target = new Pair(4, 0);
Map<Integer, Pair> foo = new HashMap<Integer, Pair>();
foo.put(1, new Pair(1, 3));
foo.put(2, new Pair(2, 3));
foo.put(3, new Pair(3, 4));
foo.put(5, new Pair(5, 4));
foo.put(6, new Pair(6, 4));
foo.put(7, new Pair(7, 5));
foo.put(8, new Pair(8, 4));
for (Map.Entry<Integer, Pair> e : foo.entrySet()) {
List<Pair> path = findPath(foo, e.getValue(), target);
if (isValidPath(path, target)) {
String pathStr = representPath(path);
// 如果短路径在长路径中，去掉短路径
boolean included = false;
for (int i = 0; i < paths.size(); ++i) {
String str = paths.get(i);
if (str.endsWith(pathStr)) {
paths.set(i, str);
included = true;
break;
} else if (pathStr.endsWith(str)) {
paths.set(i, pathStr);
included = true;
break;
}
}
if (!included) {
paths.add(pathStr);
}
}
}
// 输出路径
for (String path : paths) {
System.out.println(path);
}
}
/**
* 判断给定的节点集合是否合法的路径
* 注：更通用的做法是检查整个路径链是否合法，而不只是检查最后一个节点
* @param path
* @param target
* @return
*/
public static boolean isValidPath(List<Pair> path, Pair target) {
return path.size() > 0 && target.equals(path.get(path.size() - 1));
}
/**
* 深度搜索起始节点到目标节点的路径
* @param foo 包含所有节点的集合
* @param start 起始节点
* @param target 目标节点
* @return 返回起始节点到目标节点的路径
*/
public static List findPath(Map<Integer, Pair> foo, Pair start, Pair target) {
List<Pair> path = new ArrayList<Pair>();
if (start == null) { return path; }
do {
path.add(start);
start = foo.get(start.next);
} while (start != null && !path.contains(target) && !path.contains(start));
if (path.get(path.size() - 1).next == target.code) {
path.add(target);
}
return path;
}
/**
* 自定义路径的显示方式
* @param path
* @return
*/
public static String representPath(List<Pair> path) {
String pathStr = "";
for (Pair p : path) {
pathStr = pathStr + p.code + "->";
}
pathStr = pathStr.replaceAll("->$", "");
return pathStr;
}
}
class Pair {
public int code;
public int next;
public Pair(int code, int next) {
this.code = code;
this.next = next;
}
@Override
public int hashCode() {
return code;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null
[其他解释]
听起来你应该反向构造这棵树，也就是把 4 当作根节点，然后反向找它的叶子节点，也即：
3、5、6、8
继续递归找这几子节点的页节点：
3 -> 1, 2
5 -> 7
继续递归，直到找不到了，那么你就得到一颗完整的以4为根的树。
这棵树的所有深度遍历路径就是你要的解。
[其他解释]
Dijkstra算法不能解决么?
[其他解释]
可以看看这个文章
http://www.sitepoint.com/hierarchical-data-database-2/
也可以在google查how to store hierarchies in SQL databases
用一个left一个right值描述树的轮廓，每个节点都有一个left和right值，然后查找时通过这两个值可以轻松找到所有parents
[其他解释]
人呢，
有没有精妙的解决方案。。。
