java - AVL树: solving a StackOverflowError

Question

基本上，我通过从文本文件中读取一组整数来实现 AVL 树，然后使用 add() 方法填充树。另外，程序应该按顺序打印整数集。

当我运行该程序时，会弹出 StackOverflowError。我认为这个错误是由于 add() 方法中出现故障而触发的。

如果有人帮助我，我真的很感激，因为我是这种类型的编程新手。

这是主类的一部分:

 public static void main(String[] args) throws FileNotFoundException
   {

            AVL s1 = new AVL();

            Scanner file = new Scanner(new File("C:\\Users\\Dell\\Desktop\\integers.txt"));

            while(file.hasNext())
            {
               // String str = file.next();

                //int b = Integer.parseInt(str);
                int b = file.nextInt();
                s1.add(b);

            }

            v1.PrintInOrder(v1.root); 

这些是 add() 和 PrintInOrder() 方法:

public boolean add(int key)
 {
        root = add(root, key);
        return true;
 }

private Node add(Node b1, int key)
 {

     if(b1 == null)
     {
        return new Node(key);
     }

     if(key < b1.element){
            b1.left = add(b1.left, key);
     }
     else
     {
            b1.right = add(b1.right, key);
     }

     int Left_Height = getHeight(b1.left);
     int Right_Height = getHeight(b1.right);

     // a height imbalance requires that two subtrees differ by two
     if(Math.abs(LeftHeight - RightHeight )== 2)
         return Balance(n1);
     else
     {
        n1.ResetHeight();
        return b1;
     }
 }

   public void PrintInOrder(Node b1){
      if(b1 != null){
        PrintInOrder(b1.left);
        System.out.println(b1.element);
        PrintInOrder(b1.right);
      }
 }

这是 Node 类:

public class Node {

Node left;
Node right;
int element;
int height;

public Node(int keys){
    this(keys, null, null);
}

public Node(int d, Node right1, Node left1){
    element = d;
    height = 0;
    left = left1;
    right = right1;
}


// This method recalculates the height if the right or left subtrees have been altered
 public void ResetHeight(){

    int LeftHeight = AVL.getHeight(left);
    int RightHeight = AVL.getHeight(right);
    height = 1 + Math.max(LeftHeight,RightHeight);
}

Answer 1

由于递归中经常发生堆栈溢出。使用 IDE 并在已执行递归的位置设置中断，然后进行调试。逐步完成它。