java - 查找树高时的stackoverflow

Question

我正在编写一个简单的函数来查找节点的高度，当树有大约 50 个节点(AVL 树，平衡)时它工作正常，但是一旦树增长到一定大小，我得到一个 线程“主”java.lang.StackOverflowError 中的异常，跟踪到行 rSHeight = this.right.height()+1; &lSHeight = this.left.height ()+1;，我认为这是因为我对递归的实现很糟糕，

public int height() {
    int lSHeight,rSHeight;
    if (this.left != null) {
        lSHeight = this.left.height()+1;
    } else {
        lSHeight = 0;
    }
    if (this.right != null) {
        rSHeight = this.right.height()+1;
    }else {
        rSHeight = 0;
    }
    if (lSHeight ==0 && rSHeight ==0) {
        return 0;
    } else {
        int ret = Math.max(lSHeight, rSHeight);
        return ret;
    }
}

我想知道是否有人可以告诉我如何在树的节点数超过 1000 之前避免 stackoverflowerror？ (不假设高度变量，因为此函数用于 BaseNode 类，实际 AVLnode 派生自该类)感谢大家阅读我的帖子，按照建议，这是我的实现，基本思想是让 BaseNode 实现树的最基本功能，这样我就可以实现我刚刚学习的其他树类型来练习.AVLnode 是我目前正在研究的，以 trial 开头的方法都是我编写的用于检查功能的测试，

public abstract class BaseNode <T extends BaseNode<T>>{
int val;
T parent;
T left;
T right;

public boolean insert(T tender) {
    if ((tender.val < this.val) && (this.left != null)){
        return this.left.insert(tender);
    } else if ((tender.val < this.val)&& (this.left == null)){
        this.left = tender;
        tender.parent = (T) this; 
        // host instance will be the exact type, no real cast involved
        return true;
    } else if((tender.val>this.val)&&(this.right!=null)) {
        return this.right.insert(tender);
    } else if ((tender.val>this.val)&&(this.right == null)) {
        this.right = tender;
        tender.parent = (T) this;
        return true;
    } else {
        return false;
    }
}


public BaseNode<?> min(){
    if (this.left != null) {
        return this.left.min();
    } else {
        return this;
    }
}


public BaseNode<?> successor(){
    if (this.right != null) {
        return this.right.min();
    } else {
        boolean spot = true;
        BaseNode tempt = this;
        while(spot) {
            if (tempt.parent == null) {
                return null;
            }
            else if (tempt == tempt.parent.left) {
                spot = false;
                return tempt.parent;
            } else {
                tempt = tempt.parent;
            }
        }
    }
    return null;
}

public BaseNode<?> search(int key){
    if ((key < this.val) && (this.left != null)){
        return this.left.search(key);
    } else if ((key < this.val)&& (this.left == null)){
        return null;
    } else if((key>this.val)&&(this.right!=null)) {
        return this.right.search(key);
    } else if ((key>this.val)&&(this.right == null)) {
        return null;
    } else {
        return this;
    }   
}


//replace the host node with jim in the Tree
//certainly not a good practice to just change the value
public void swapIn(BaseNode jim) {
    //the connections on New Node side are done here
    //the connections on other Nodes side are done in 'adopt'
    jim.parent = this.parent;
    if(this.left != jim) {
        jim.left = this.left;
    }
    if (this.right!=jim) {
        jim.right=this.right;
    }
    this.adopt(jim);
}


public void adopt(BaseNode stepK) {
    if(this.parent!=null) {
        if (this == this.parent.left) {
            this.parent.left = (T) stepK;
        } else {
            this.parent.right = (T) stepK;
        }
    }
    if(this.left != stepK && this.left != null) {
        this.left.parent = (T) stepK;
    }
    if (this.right!= stepK && this.right!=null) {
        this.right.parent = (T) stepK;
    }
}



public boolean delete(int key) {
    BaseNode sp = this.search(key);
    if (sp==null) {
        return false;
    }else {
        if ((sp.left==null)&&(sp.right==null)) {
            sp.swapIn(null);
        } else if((sp.left==null)^(sp.right==null)) {
            if (sp.left==null) {
                sp.swapIn(sp.right);
            } else {
                sp.swapIn(sp.left);
            }
        } else {
            BaseNode hinch =sp.successor();   //it's not possible to have hinch== null here
            if(hinch.right!=null) {
                hinch.swapIn(hinch.right);
            }
            sp.swapIn(hinch);
            //sp.findRoot().delete(hinch.val);
        }
        return true;
    }
}


//A recursive algorithm the returns height
public int height() {
    int lSHeight,rSHeight;
    if (this.left != null) {
        lSHeight = this.left.height()+1;
    } else {
        lSHeight = 0;
    }
    if (this.right != null) {
        rSHeight = this.right.height()+1;
    }else {
        rSHeight = 0;
    }
    if (lSHeight ==0 && rSHeight ==0) {
        return 0;
    } else {
        int ret = Math.max(lSHeight, rSHeight);
        return ret;
    }
}

//Recursively put tree rooted at hose instance into array 'rack' as a heap
public void stashBST(T rack[],int idx){
//rack was created as subclass array, the host is also a subclass 
object, proper cast
    rack[idx] = (T) this;
    if(this.left!=null) {
        this.left.stashBST(rack, idx*2+1);
    }
    if (this.right != null) {
        this.right.stashBST(rack, idx*2+2);
    }
}

//return val of host as a string object with 'toklen' length
public String printableNode(int tokLen) {
    String signi = Integer.toString(this.val);
    try {
        if (signi.length()<= tokLen) {
            int gap = tokLen - signi.length();
            int front = gap/2;
            int back = gap - front;
            String pre ="";
            String post= "";
            for(int i =0;i< front;i++) {
                pre = pre+ " ";
            }
            for(int i =0;i< back;i++) {
                post = post+ " ";
            }
            String ret = pre+signi+post;
            return ret;
        } else {
            throw new RuntimeException("the number is too big!");
        }
    } catch (RuntimeException e) {
        return null;    
    }
}


public BaseNode findRoot() {
    if(this.parent!=null) {
        return this.parent.findRoot();
    } else {
        return this;
    }
}

public boolean fost(T nbie) {
    if (this.parent != null){
        if (this == this.parent.left) {
            this.parent.left = nbie;
            nbie.parent = this.parent;
        } else {
            this.parent.right = nbie;
            nbie.parent = this.parent;
        }
        return true;
    } else {
        nbie.parent = null;
        return false;
    }
}

public boolean leftRot() {
    if(this.right == null) {
        return false;
    } else {
        this.fost(this.right);
        this.parent = this.right;
        T tempD = this.right.left;
        this.right.left = (T) this;
        this.right = tempD;
        return true;
    }
}

public boolean rightRot() {
    if(this.left == null) {
        return false;
    } else {
        this.fost(this.left);
        this.parent = this.left;
        T tempD = this.left.right;
        this.left.right = (T) this;
        this.left = tempD;
        return true;
    }   
}

//print a tree rooted at host 
public void printTree() {
    int height =  this.height();
//Hvae Array of BaseNode doesn't hurt, it's just reference, we can cast 
it back if needed
    BaseNode rack[]=new BaseNode[(int) Math.pow(2, height+1)];
    this.stashBST((T[]) rack, 0);
    int TokCap = (int)Math.pow(2, height);
    int maxWidth = TokCap*5;
    for (int i=0;i<height+1;i++) {
        int numLv =(int) Math.pow(2, i);
        int widthLv = maxWidth/numLv;
        for(int j =(int)Math.pow(2, i)-1; j<(int)Math.pow(2, i+1)-1;j++) {
            if(rack[j]!= null) {
                if (rack[j].val==1){
                    int begal = 15;
                }
                System.out.print(rack[j].printableNode(widthLv));
            } else {
                String temp = "";
                for(int k=0;k<widthLv;k++) {
                    temp = temp+" ";
                }
                System.out.print(temp);
            }
        }
        System.out.println(""); 
    }
}

}

这是树类:

public class tree <T extends BaseNode> {
T root;

public tree(T adam) {
    if (adam != null) {
        root = adam;
    } 
}

public void reCal() {
    while(root.parent != null) {
        root = (T) root.parent;
    }
}

public void showTree() {
    root.printTree();
}


public boolean insert(T nbie) {
    if (this.root != null){
        boolean res = this.root.insert(nbie);
        //this.reCal();

        if (root instanceof AVLnode) {
            ((AVLnode) nbie).fixProp();
        }
        this.reCal();
        return res;
    } else {
        //if empty tree, assume the we having a plain
        root = nbie;
        return true;
    }
}

public boolean delete(int key) {
    if (root.val == key) {
        if (root.right != null) {
            T temp = (T) root.successor();
            root.delete(key);
            this.root = temp;
            return true;
        } else {
            root.swapIn(root.left);
            this.root = (T) root.left;
            return true;
        }   
    } else {
        return root.delete(key);
    }
}

public T search(int key) {
    if(root == null) {
        return null;
    } else {
        return (T) root.search(key);
    }
}   

}


import java.util.Arrays;

这是 AVLnode 类:

public class AVLnode extends BaseNode<AVLnode>{
public int hMark;

public AVLnode(int key) {
    this.val = key;
    this.left = null;
    this.right = null;
    this.parent = null;
    this.hMark = 0;
}


public boolean insert(AVLnode nbie) {
    boolean result = super.insert(nbie);
    if (result == true) {
        if (((this.left == nbie) && (this.right ==null))||((this.right == nbie)&&(this.left==null))) {
            this.hMark = this.hMark + 1;
        } 
    } else {
        return result;
    }
    if (this.left == null) {
        this.hMark = this.right.hMark +1;
    } else if (this.right == null) {
        this.hMark = this.left.hMark + 1;
    } else {
        this.hMark = Math.max(this.left.hMark,this.right.hMark)+1;
    }
    return result;
}

public void fixProp() {
    int lh, rh;
    if(this.left == null) {
        lh = -1;
    } else {
        lh = this.left.hMark;
    }
    if (this.right == null) {
        rh=-1;
    } else {
        rh = this.right.hMark;
    }
    if(Math.abs(lh-rh) >1 ) {
        int llh,lrh,rrh,rlh;

        if (this.left!=null) {
            if (this.left.left == null) {
                llh = -1;
            } else {
                llh = this.left.left.hMark;
            }

            if(this.left.right == null) {
                lrh = -1;
            } else {
                lrh = this.left.right.hMark;
            }
        } else {
            llh = -1;
            lrh = -1;
        }

        if(this.right !=null ) {
            if(this.right.left == null) {
                rlh = -1;
            } else {
                rlh = this.right.left.hMark;
            }

            if(this.right.right == null) {
                rrh = -1;
            } else {
                rrh = this.right.right.hMark;
            }
        } else {
            rlh = -1;
            rrh = -1;
        }

        if((lh>rh) && (llh>lrh)){
            this.rightRot();

            if(this.parent.parent != null) {
                this.parent.parent.fixProp();
            } else {
                return;
            }
        } else if ((rh>lh)&&(rrh>rlh)) {
            this.leftRot();
            if(this.parent.parent != null) {
                this.parent.parent.fixProp();
            } else {
                return;
            }
        } else if ((lh>rh)&&(lrh>llh)) {
            this.left.leftRot();
            this.rightRot();
            if(this.parent.parent != null) {
                this.parent.parent.fixProp();
            } else {
                return;
            }
        } else if((rh>lh)&&(rlh>rrh)) {
            this.right.rightRot();
            this.leftRot();
            if(this.parent.parent != null) {
                this.parent.parent.fixProp();
            } else {
                return;
            }
        }       
    } else {
        if(this.parent != null) {
            this.parent.fixProp();
        } else {
            return;
        }
    }
}

public boolean heightFeatureCheck() {
    if (this.hMark == this.height()) {
        boolean lOut = true;
        boolean rOut = true;
        if (this.left!=null) {
            lOut = this.left.heightFeatureCheck();
        }
        if (this.right != null) {
            rOut = this.right.heightFeatureCheck();
        }
        return (lOut && rOut);
    } else {
        return false;
    }   
}



public static void trialInsertionAVL() {
    // for testing convenience, not gonna have a tree
    int statRack [] = new int [] {45,48,35,40,30,8};
    AVLnode adam = new AVLnode(statRack[0]);
    for(int i =1;i<statRack.length;i++) {
        AVLnode bitco = new AVLnode(statRack[i]);
        adam.insert(bitco);
    }
    adam.printTree();
    System.out.println("====================================================");
    //System.out.print(adam.heightFeatureCheck());
    AVLnode chris = (AVLnode) adam.search(8);
    AVLnode futKing = (AVLnode) adam.search(35);
    chris.fixProp();
    futKing.printTree();
}

public static void trialAVLTree() {
    int pool [] = new int [] {15, 42, 12, 29, 29, 44, 38, 29, 29, 33, 0,};
    AVLnode adam = new AVLnode(pool[0]);
    tree oak = new tree(adam);
    for(int i=1;i<pool.length;i++) {
        AVLnode son = new AVLnode(pool[i]);
        oak.insert(son);
        oak.showTree();
        System.out.println("++++++++++++++++++++++++++++++++++++++");
    }
    oak.showTree();
}

public static void trialDynamicAVL() {
    int pool [] = Node.rawGene();
    //System.out.println(Arrays.toString(pool));
    AVLnode adam = new AVLnode(pool[0]);
    tree oak = new tree(adam);
    for(int i=1;i<pool.length;i++) {
        AVLnode son = new AVLnode(pool[i]);
        oak.insert(son);
        oak.showTree();
        System.out.println("++++++++++++++++"+Integer.valueOf(i)+"++++++++++++++++++++++");
    }
    oak.showTree();
    System.out.println("this is it!!!!!!");
}

public static void main(String args[]) {
    trialDynamicAVL();
}

}

这是节点类

import java.util.Arrays;
import java.util.Random;
import java.math.*;

public class Node extends BaseNode<Node>{



public Node(int key) {
    this.val = key;
    this.parent = null;
    this.left = null;
    this.right =null;
}


public static int[] rawGene() {
    int drizzy [] = new int [100];
    Random magic = new Random();
    for (int i=0;i<100;i++) {
        drizzy[i] = magic.nextInt(50);
    }
    System.out.println(Arrays.toString(drizzy));
    return drizzy;
}

public int bfsTrial(int counted) {
    counted++;
    System.out.println(this.val);
    if(this.left != null) {
        counted = this.left.bfsTrial(counted);          
    }
    if (this.right != null) {
        counted = this.right.bfsTrial(counted);
    }
    if ((this.left==null) && (this.right == null)) {
        return counted;
    }
    return counted;
}


public void bstInArray(Node yard [], int r_idx) {
    //the adam is the node we just discover, r_idx is the idx of the adam
    yard[r_idx] = this;
    if (this.left != null){
        this.left.bstInArray( yard, r_idx*2);
    }
    if(this.right != null) {
        this.right.bstInArray(yard, (r_idx*2+1));
    }
    if((this.left == null)&&(this.right==null)) {
        return;
    }

}

public static Node makeTree(int pool []) {
    Node root = new Node(pool[0]);
    for(int i =1;i<pool.length;i++) {
        Node bitco = new Node(pool[i]);
        root.insert(bitco);
    }
    return root;
}

public static Node makeTree() {
    int statRack [] = new int [] {45, 14, 5, 47, 20, 9, 4, 37, 30, 1};
    return makeTree(statRack);
}


//make an shuffled array of integer [1:size]
public static int[ ] shuffleArrGen(int size) {
    int rack [] = new int[size];
    Random r = new Random();
    for(int i=0;i<size;i++) {
        rack[i] = i+1;
    }
    for(int j=size-1;j>0;j--) {
        int idx = r.nextInt(j+1);
        int buff = rack[j];
        rack[j] = rack[idx];
        rack[idx] = buff;
    }
    return rack;
}

}

此外，正如您可能已经注意到的那样，我花费了大量的代码来检查某些内容是否为空，我想知道是否有更好的方法来做到这一点？我读过的一种解决方案是为所有节点的 null 子节点设置一个通用的“nil”节点。

Answer 1

Java 堆栈因平台(和 VM 标志)而异，但通常为 1MiB。即使假设每帧 1KiB，也就是 > 1000 帧，除非您的 VM 具有由标志设置的异常小的堆栈。

正如评论者已经指出的那样，这段代码在堆栈中保留的最大帧数是height(tree)。这意味着树可能有问题。

这个假设有一个简单的测试:向方法添加一个 int level 参数(显然将 level+1 传递给嵌套调用)并在每次调用时打印它看看它有多高。如果它达到 ~1000，则检查树。如果它保持在 ~10 左右，则检查堆栈大小。

无关:不需要对 (lSHeight ==0 && rSHeight ==0) 进行单独测试，因为 Math.max() 对此做了正确的事情案例已经。