首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >java n叉树深度

java n叉树深度
EN

Stack Overflow用户
提问于 2015-03-24 20:23:31
回答 1查看 706关注 0票数 0

下面是我的树节点类:

代码语言:javascript
复制
public class Generalization extends Class_object {
private List<Generalization> superClasses;
private List<Generalization> subClasses;

public boolean isRoot() {
    return superClasses.size() == 0;
}

public boolean isLeaf() {
    return subClasses.size() == 0;
}

// path length to root
public String getDIT() {
    return Integer.toString(recuDIT(this));
}

public int recuDIT(Generalization g) {
    if (g.isRoot())
        return 0;
    else {
        int maxLength = 0;
        for (Generalization gen : superClasses) {
            maxLength = Math.max(maxLength, recuDIT(gen));
        }
        return maxLength + 1;
    }
}

// path length to leaf
public String getCLD() {
    return Integer.toString(recuCLD(this));
}

public int recuCLD(Generalization g) {
    if (g.isLeaf())
        return 0;
    else {
        int maxLength = 0;
        for (Generalization gen : subClasses) {
            maxLength = Math.max(maxLength, recuCLD(gen));
        }
        return maxLength + 1;
    }
}
}

每个节点都有其父节点和子节点。但是,当我执行程序时,它在递归函数(CLD和DIT)中给出了堆栈溢出错误。有人能告诉我他们为什么会无限地循环吗?谢谢。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2015-03-24 20:52:27

代码语言:javascript
复制
public class Generalization {
    private List<Generalization> superClasses;
    private List<Generalization> subClasses;

    public Generalization(){
        superClasses = new ArrayList<Generalization>();
        subClasses = new ArrayList<Generalization>();
    }

    public boolean isRoot() {
        return superClasses.size() == 0;
    }

    public boolean isLeaf() {
        return subClasses.size() == 0;
    }

    // path length to root
    public String getDIT() {
        return Integer.toString(recuDIT(this));
    }

    public int recuDIT(Generalization g) {
        if (g.isRoot())
            return 0;
        else {
            int maxLength = 0;
            for(int i = 0 ; i < g.superClasses.size(); i++){
                maxLength = Math.max(maxLength, recuDIT(g.superClasses.get(i)));
            }
            return maxLength + 1;
        }
    }

    // path length to leaf
    public String getCLD() {
        return Integer.toString(recuCLD(this));
    }

    public int recuCLD(Generalization g) {
        if (g.isLeaf())
            return 0;
        else {
            int maxLength = 0;
            for(int i = 0 ; i < g.subClasses.size(); i++){
            maxLength = Math.max(maxLength, recuCLD(g.subClasses.get(i)));
            }
            return maxLength + 1;
        }
    }

public static void main(String[] args){
    Generalization root = new Generalization();

    Generalization ch1 = new Generalization();
    Generalization ch2 = new Generalization();

    root.subClasses.add(ch1);
    root.subClasses.add(ch2);

    Generalization gc1 = new Generalization();
    Generalization gc2 = new Generalization();
    Generalization gc3 = new Generalization();

    ch2.superClasses.add(root); 
    ch2.subClasses.add(gc1);
    ch2.subClasses.add(gc2);

    ch1.subClasses.add(gc3);
    ch1.superClasses.add(root);

    Generalization ggc1 = new Generalization();

    gc3.subClasses.add(ggc1);
    gc3.superClasses.add(ch1);

    gc2.superClasses.add(ch2);
    gc1.superClasses.add(ch2);

    ggc1.superClasses.add(gc3);

    System.out.println(ggc1.getDIT());
    System.out.println(root.getCLD());



}
}

不知道我是否正确地设置了树,或者真的测试了那么多,这对我来说是有效的。主要问题是您在方法中使用的是recuDIT/CLD类,而不是泛化对象g。因此,您经常递归地遍历相同的列表,而不从第一个索引开始。我还将您的for每个循环更改为for循环,因为它更容易查看和调试。

除此之外,这给了我3的长度与根和叶的长度,我相信这是正确的。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/29242174

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档