java - 尝试构建完全左偏二叉树 - 出现堆栈溢出错误

Question

我不明白为什么我的递归调用很糟糕。有人可以阐明我做错了什么以及如何纠正这个问题吗？我感谢任何和所有的帮助。

我有一个充满随机整数的数组，正在尝试构建一个完全左偏的二叉树。

主要:

    public static void main(String[] args) {


        //Declare New Array to Store Integer Values
        int[] array1 = new int[26];
        randArray(array1, 1, 50);

        for(int x=0; x < array1.length; x++)
            System.out.print(array1[x] + " ");

        //Build Skewed Tree
        BinaryTree tree1 = new BinaryTree(array1[0]);
        for(int x=1; x < array1.length; x++)
            tree1.addLeft(new BinaryTree(array1[x]));

        tree1.print();


    }

    public static void randArray(int[] list, int low, int up) {
        Random rand = new Random();
        for (int i = 0; i < list.length; i++) {
            list[i] = rand.nextInt(up - low + 1) + low;
        }
    }
}

添加左:

  public void addLeft(BinaryTree subtree){
        if(leftChild != null){
            addLeft(leftChild);
        }

        leftChild = subtree;
    }

Answer 1

您的 addLeft 函数很可能应如下所示:

public void addLeft(BinaryTree subtree){
   if(leftChild != null){
      leftChild.addLeft(subtree);
   }

   leftChild = subtree;
}

注意:这实际上并没有对任何东西进行排序。如果您想要一个排序的左偏二叉树，该函数应该如下所示:

public void addLeft(BinaryTree subtree){
   if (subtree.value < value)
   {
      int tmp = value;
      value = subtree.value;
      subtree.value = tmp;
   }

   if(leftChild != null){
      leftChild.addLeft(subtree);
   }

   leftChild = subtree;
}

由于您实现这棵树的方式，我通过交换值来做到这一点。如果这是一个真正的左右二叉树，您可以将节点转储到左侧和右侧并以这种方式对它们进行排序。