N树的高度

Question

我试着写一个叫做getHeight()N-ary树的高度的方法.我的尝试不起作用.这是我正在使用的树接口:

public interface MyTree  {
    Tree getSubTree(int i) ;//returns a subtree
    boolean isLeaf() ;//returns true if the node is a leaf
    int getDegree() ; 
}   

这是我写的代码片段:

public int getHeight(){

    for(int i = 0 ; i<getDegree()-1 ; ++i){  

        if(isLeaf()){
            return 0; 

        }else{
            return 1 + Math.Max(getSubtree(i).getHeight() , getSubtree(i+1).getHeight() ; 
        }
    }
}

我该如何解决这个问题呢？

Answer 1

你的问题在这里:

 return 1 + getSubtree(i).getHeight(); 

一旦计算出1 +单个子树的高度,就会从该方法返回.你真正需要做的是调用getHeight()每个子树,并返回1 +每个子树的最大值.(如果您的树有任何平衡属性,这可以简化.)

例如,如果您调用此树的树有三个子树,高度为2,4和5,则代码将调用getHeight()第一个子树并查看2,然后立即返回3,而不是检查getHeight()剩余的子树以查找有一个较高的子树(高度为5的子树).