一般树形结构 通路长度


题:一般树形结构_求通路长度
注意树形结构的特点:
从一个节点到另一个节点只有一条通路。

编程求a点到b点的通路长度。

源码NTree.java


package NTree;

import java.util.ArrayList;
import java.util.List;

public class NTree {
    private List<Node> lst = new ArrayList<Node>();
    class Node {
        String data;
        String parent;
    }

    public void add(String parent, String child) {
        Node t = new Node();
        t.data = child;
        t.parent = parent;
        lst.add(t);
    }

    public String getParent(String x) {
        for (int i=0; i<lst.size(); i++ ) {
            if (lst.get(i).data.equals(x)) {  
                return lst.get(i).parent;
            }
        }
        return null;
    }
    
    public List<String> getChild(String x) {
        List<String> t = new ArrayList<String>();
        for (int i=0; i<lst.size(); i++) {
            if (lst.get(i).parent.equals(x)) {
                t.add(lst.get(i).data);
            }
        }
        return t;
    }

    public int getDis(String begin,String end) {
        String a = begin;
        String b = end;
        int c = 0;
        int d = 0;
        while (a!=b && getParent(a)!=null) {
            d = 0;
            while (a!=b && getParent(b)!=null) {
                d++;
                b = getParent(b);
            }
            if (a!=b) {
                c++;
                a = getParent(a);
                b = end;
            }
        }
        if (getParent(a)==null) {
            return -1;
        }
        else {
            return c+d;
        }
    }
    
    public static void main(String[] args) {
        NTree a = new NTree();
        a.add("世界", "亚洲");
        a.add("世界", "欧洲");
        a.add("世界", "美洲");
        a.add("亚洲", "中国");
        a.add("亚洲", "日本");
        a.add("亚洲", "韩国");
        a.add("中国", "北京");
        a.add("中国", "河北");
        a.add("中国", "江苏");
        
        System.out.println(a.getParent("江苏"));
        System.out.println(a.getChild("中国"));
        System.out.println(a.getDis("韩国","江苏"));
        System.out.println(a.getDis("美","江苏"));
        System.out.println(a.getDis("江苏","江苏"));
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注