怎么找两棵树共同节点？？然后再找出树根1到数根2的路径？？

Question

具体。 已知2棵树的树根是相连的。
现在想找出，树根1到树根2的所有路径。目前想到是
1）遍历2个棵树，列出所有节点的 树根到该节点的路径。（简称根节点路径）
2）比较有没有相同节点。 并找出所有相同节点。
3）对于某个相同节点，把树根1的节点路径 + 反向（树根2的节点路径）Java用什么数据结构做好呢？？
最好能给出相应的代码支持。

Answer 1

再次惊见scbb同学啊～～～首先，“现在想找出，树根1到树根2的所有路径”，没能理解是想干啥。
树模型有两种常规结构：
A、父子连接关系，所谓： id, parentId
B、层级编码关系，所谓： 根.干.支.叶1）遍历2个棵树，列出所有节点的 树根到该节点的路径。（简称根节点路径）
—— B结构比较简单，code like '根*' 就能得到所有节点（Java代码的话是startsWith），且其层级编码就是路径；
—— A结构需要做父子连接，如果是Oracle的话，有关键字直接支持倒是比较简单。2）比较有没有相同节点。 并找出所有相同节点。
—— 不知道啥意思？相同的定义是啥？3）对于某个相同节点，把树根1的节点路径 + 反向（树根2的节点路径）
—— 由于前者定义不理解，所以改为：寻找两个节点的公共父（找到公共父节点自然就是联通路径了）
—— B结构下，就是层级查找相同的开始片段，这个比较简单；
—— A结构下，仍然要做父子连接，会比较麻烦些。

Answer 2

这个确实应该是图。
但是数据连不起来。 输入是只是2个树（其实更烦，是数据库里一些表的record），找到共同节点了才是图

Answer 3

因为我要记路径，有没有现成的Path类。
然后还支持反向取得path。

Answer 4

那看起来是非常适合于先进行预处理的了。可以考虑先将整个图，在内存中把模型都构造好，作为一个独立服务供路径查询了。现成Path类不知道你是指什么意思。

Answer 5

我自己写了一个。
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;public class NetworkPath implements Cloneable {
private LinkedList<String> path = new LinkedList<String>();

public List<String> getPath() {
return path;
} public List<String> getCrossNode(NetworkPath otherPath) {
List<String> ret = new LinkedList<String>(otherPath.getPath());
ret.retainAll(path);
return ret;
}

public NetworkPath reverse() {
List<String> reversePath = new LinkedList<String>();
Iterator<String> itr = path.descendingIterator();
while (itr.hasNext()) {
reversePath.add(itr.next());
}
NetworkPath ret = new NetworkPath();
ret.getPath().addAll(reversePath);
return ret;
}

public NetworkPath getSubPath(String nodeName, boolean isContained) {
int index = path.indexOf(nodeName);
if (index != -1) {
List<String> subPath;
if (isContained) {
subPath = path.subList(0, index + 1);
} else {
subPath = path.subList(0, index);
}
NetworkPath ret = new NetworkPath();
ret.getPath().addAll(subPath);
return ret;
}
return null;
}

public NetworkPath merge(NetworkPath nwp) {
NetworkPath ret = this.clone();
ret.getPath().addAll(nwp.getPath());
return ret;
}

public String getLastNodeName() {
try {
return path.getLast();
} catch (NoSuchElementException e) {
return null;
}
}

public boolean containNode(String nodeName) {
return path.contains(nodeName);
}

public void removeLast() {
if (path.size() > 0) {
path.remove(path.size() - 1);
}
}

@Override
public NetworkPath clone() {
NetworkPath ret = new NetworkPath();
ret.getPath().addAll(path);
return ret;

}

@Override
public String toString() {
return path.toString();
}

@Override
public boolean equals(Object obj) {
if (obj instanceof NetworkPath) {
NetworkPath nwp = (NetworkPath)obj;
return this.getPath().equals(nwp.getPath());
}
return false;
}}