求四叉树树高的问题

Question

具体说明: 假设目前有一个返回int类型的getHeight()方法，没有输入参数，在这个方法里应该如何实现获取四叉树的树高呢？我目前的做法是打算用递归的方式来处理这个问题，因为getHeight()不能有参数，貌似不能直接在里面用递归，所以我就自己写了个helper method，具体代码如下：private int countTreeHeight(QTreeIterator QTreeit){
if(QTreeit.current == null)
return 0;

if(QTreeit.current == root)
tempheight = 1;

for(int i=0; i<=3; i++){    //感觉这个循环有问题，因为只能遍历到children[0]的情况，children[1]到children[3]都遍历不到
if(QTreeit.current.children[i] != null){
QTreeit.child(i);
tempheight = 1 + countTreeHeight(QTreeit);
}
}
return tempheight;
}代码说明：
QuadTreeIterator是一个内部类，实现对四叉树的各种操作。 
QTreeit.current表示指向的当前结点。
QTreeit.child（i）表示从当前结点向下移动到其第i个孩子结点上。
这个方法其实是有问题的，还是无法得到正确的树高，不过我现在也没什么想法了，不知道应怎么修改上面这段代码，所以希望各位高手能否指点小弟一下，当然，如果有其他的方法，也请分享一下，谢谢咯。

Answer 1

楼主的程序问题出在，1个节点的高度应该等于该节点的四棵子树的最大高度加1.
   height(Node)=max( height(Node.childs) )+1;    private int countTreeHeight(QTreeIterator QTreeit){
        if(QTreeit.current == null)
            return 0;
        
        //这句话应该是多余的
        //if(QTreeit.current == root)
        //    tempheight = 1;
        
        int[] childHeight=new int[4];//记录四棵子树的树高。
        for(int i=0; i<=3; i++){    
            //if(QTreeit.current.children[i] != null){   //这句不需要吧，就算current.children[i]==null,进入该节点时，
                                                                 //会因为if(QTreeit.current == null)  return 0;
                QTreeit.child(i);
                childHeight[i]= 1 + countTreeHeight(QTreeit);
            //}
        }
        //求四棵子树的最大树高
        tempheight=childHeight[0];
        for(int i=1;i<4;i++)
            if(childHeight[i]>tempheight)
                tempheight=childHeight[i];
        return tempheight;
    }
 

Answer 2

我按照你提的这个方法试过了，不过结果还是不正确，没有进行递归，得到的高度都为1，是不是还是逻辑不对呢？另外提一下，当只有一个根节点的时候，树高默认为1，应该从1开始计数，不是0。还有就是，if(QTreeit.current.children[i] != null)这句话觉得还是应该保留的,否则QTreeit.child(i)碰到叶结点，就会throw exception,嗯，至少child（）方法里是这么定义的。希望大家再来看看，帮个忙吧。

Answer 3

我觉得我的方法的逻辑应该没有问题，可能是因为我不太清楚那几个方法是怎么实现的吧，比如QTreeIterator.child()。
1.当四叉树只有一个根结点时，height(root)=max(height(root.childs))+1, 由于根结点没有子节点，所以root.child(i)==null,树高返回0,所以根结点的四棵子树的最大树高为0，则height(root)=0+1=1。所以，不需要if(QTreeit.current == root) 也可以从1开始计数。
                                                      tempheight = 1; 2.我不知道QTreeit.child(i)碰到叶结点，就会throw exception。我觉得child()方法不应该这么定义，因为当这么定义时，如果1个节点比如叶节点leafNode，它的子节点都是null，所以按照你的方法，就不会进入方法countTreeHeight(leafNode.children[i]),就不会产生递归了，返回的tempheight也是不对的。
如果就想要QTreeit.child(i)碰到叶结点，就会throw exception。你需要加个判断，当某个节点的所有子节点都是null时，tempheight=1，这样应该可以了吧。

Answer 4

我觉得这样还是不清楚，
楼主可否把QTreeIterator.child()发上来，供大家讨论。 

Answer 5

 child()的代码如下:
public void child(int p) throws TreeException{
if(!isLeaf() && (p >= 0 && p <= 3)){
current.parent = current;
current = current.children[p];
}
else throw new TreeException("the current node is a leaf node or p is out of range.");
}
说明:  参数p表示child的位置,p应该在0-3之间,比如p=0,则表示找第1个孩子,以此类推.
另外,再提供一个parent()的方法，这个方法可以让iterator向当前结点的父结点移动，代码如下:
public void parent() throws TreeException{
if(!isRoot()){
current = current.parent;
}
else throw new TreeException("the current node is the root");
}说明:  如果是在root的话，throw exception, 否则去移动current到parent结点

Answer 6

楼主试一试这样行不行。
把child方法改成可以访问叶节点的子节点，只不过它们都是null而已。
然后再按照3楼，我说方法试试，看可不可以。public void child(int p) throws TreeException{
    if(current!=null && (p >= 0 && p <= 3)){  //isLeaf()应该是判断current是不是叶节点。
         current.parent = current;
         current = current.children[p];
    }
    else throw new TreeException("the current node is null or p is out of range.");
}

Answer 7

我写了一个简易的程序，楼主看一下吧。可以递归计算树高
/**
 *
 * @author KILLer
 */
public class QTree 
{
        private QTreeNode root;
        ///以这种方式构造了一棵树
public QTree(){
root=new QTreeNode(new Integer(1),null);
root.children[0]=new QTreeNode(new Integer(2),root);
root.children[1]=new QTreeNode(new Integer(3),root);
root.children[2]=new QTreeNode(new Integer(4),root);
root.children[3]=new QTreeNode(new Integer(5),root);
root.children[0].children[0]=new QTreeNode(new Integer(6),root);
root.children[0].children[1]=new QTreeNode(new Integer(7),root);
root.children[0].children[1].children[0]=new QTreeNode(new Integer(8),root);
}
        //计算以node为根的子树的高度。如果node==null树高为0
public int QTreeHeight(QTreeNode node){
        if(node==null)
             return 0;
        int[] childHeight=new int[4];//记录四棵子树的树高。
                   for(int i=0; i<=3; i++) 
                    childHeight[i]= 1 + QTreeHeight(node.child(i));
                //求四棵子树的最大树高
                  int tempheight=childHeight[0];
                for(int i=1;i<4;i++)
                if(childHeight[i]>tempheight)
                    tempheight=childHeight[i];
                return tempheight;
}
public int QTreeHeight(){
            return QTreeHeight(root);
}
        
        //四叉树节点内部类
        private class QTreeNode
        {
            public QTreeNode[] children;
            private Object data;
            private QTreeNode parent;
            public QTreeNode(Object data,QTreeNode parent){
                this.data=data;
this.parent=parent;
children=new QTreeNode[4];
            }
        }
public static void main(String[] args) 
{
QTree tree=new QTree();
System.out.println(tree.QTreeHeight());
}
}

Answer 8

刚才太急了，误删了一个函数，汗~///在QTreeNode类中添加
public QTreeNode child(int p){
    return children[i];
}

Answer 9

嗯，非常感谢chosenOne的帮助呵，贴了详细的代码上来，thanks very much

Answer 10

嗯，另外，关于我自己在9楼帖出来的2段代码，我目前已经重新改过了，仔细看原来的实际上是有问题的，主要是parent()不对，因为没有更新current.parent的引用，原来我调用parent()只能往父结点走一次，要再继续向上走就不行了，我现在改写的代码如下（用了Stack储存父结点）：
child方法public void child(int p) throws TreeException{
if(!isLeaf() && (p >= 0 && p <= 3)){
current.parent = current;
parentstack.push(current);
current = current.children[p];
}
else throw new TreeException("the current node is a leaf node or p is out of range.");
}
parent方法public void parent() throws TreeException{
if(!isRoot()){
current = parentstack.pop();
current.parent = parentstack.pop();
}
else throw new TreeException("the current node is the root");
}
这样的话，回归父结点就可以正常实现了。