java - Java中使用数组的二叉搜索树

Question

我正在尝试用 Java 编写二叉搜索树的数组实现。为此，我有以下两种方法负责确保所有数据正确添加到数组中

private int[] testData = {50, 25, 75, 10, 15, 5, 53, 29, 79, 78, 111, 33};
private int[] tree = new int[100];
private final int ROOT = tree.length / 2; //Root is at the center of the array

public void insert(int key)
{
    if(tree[ROOT] == 0)
    {
        tree[ROOT] = key;
    }
    else
    {
        int locToInsert = findLocationToInsert(ROOT, key);
        if(locToInsert == -1)
        {
            System.out.println("Error: Tree branch full");
        }
        else
        {
            tree[locToInsert] = key;
        }
    }
}

public int findLocationToInsert(int c, int key)
{
    if(tree[c] != 0) //If current c is not empty
    {
        if(key > tree[c]) //Go right to find an empty c
        {
            findLocationToInsert(c + c/2, key);
        }
        else //Go left to find an empty c
        {
            findLocationToInsert(c - c/2, key);
        }
    }
    return c;
}

但是，我的递归 findLocationToInsert 方法始终返回根。如何修复此实现以返回它找到的第一个空位置？

Answer 1

您的递归函数不会对其递归调用的结果执行任何操作。

       findLocationToInsert(c + c/2, key);

如您所见，您没有将返回值分配给任何内容，因此它只是被丢弃。

因此，在执行 if 或 else 后，它只是转到 return c 行并返回原始的 c 它得到的 - 这是根。

在决定如何处理递归调用的值之前，您应该解决另一个问题:没有停止条件。

如果你真的填充了你的树，你应该根据你的其他方法返回-1。但是您的函数中没有任何地方返回 -1。如果树已满，它将陷入无限循环，并且会出现堆栈溢出。