java实现树的节点之间距离;向下递归,注意找到一个满足条件的节点要break
import java.util.ArrayList;
import java.util.List;
public class NodeofTreeDistance {
static class Tree {
private List<Node> list = new ArrayList<Node>();
/**
* 内部类
*
* @author buaa-pc
*
*/
class Node {
String data;
String parent;
}
public void add(String parent, String child) {
Node n = new Node();
n.data = child;
n.parent = parent;
list.add(n);
}
/**
* 获取父节点
*
* @param x
* @return
*/
public String getParent(String x) {
for (int i = 0; i < list.size(); i++) {
if (list.get(i).data.equals(x)) {// 比较内容
return list.get(i).parent;
}
}
return null;
}
public List<String> getChild(String x) {
List<String> newList = new ArrayList<String>();
for (int i = 0; i < list.size(); i++) {
if (list.get(i).parent.equals(x)) {
newList.add(list.get(i).data);
}
}
return newList;
}
public int distance(Tree t,String x,String y) {
int distance=0;
for (int i = 0; i < t.getChild(x).size(); i++) {
if (t.getChild(x).toString().contains(y)) {
distance=1;
break;
}
else {
String city=t.getChild(x).get(i);
int z=distance(t,t.getChild(x).get(i),y);
if (z!=0) {//这里判断下,如果先前有节点已经包含了就跳出来
distance=z+1;
break;
}
}
}
return distance;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Tree a = new Tree();
a.add("世界", "欧洲");
a.add("世界", "亚洲");
a.add("世界", "美洲");
a.add("亚洲", "中国");
a.add("亚洲", "日本");
a.add("亚洲", "韩国");
a.add("中国", "北京");
a.add("中国", "江苏");
a.add("中国", "上海");
a.add("中国", "安徽");
//求世界到安徽的节点距离
System.out.println("世界与安徽的距离为"+a.distance(a, "世界","安徽"));
//求亚洲到安徽的节点距离
System.out.println("世界与安徽的距离为"+a.distance(a, "亚洲","安徽"));
}
}
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。