如何在二叉搜索树数组实现中找到最大值的索引？

Question

左右数组是当前索引的左右子级的索引号。如果其中一个为-1，则该子代不存在。如果两者都为-1，则索引处的节点是叶节点。我知道这在现实世界中不太可能实现，但这是一项任务。

不管怎样，我正试图在一个实现这个想法的类中实现一个remove方法。除了一个节点有两个子节点的情况，我让它适用于所有情况。这里的问题是，我调用了一个递归方法(我创建的所有方法都必须是递归的),该方法应该返回包含我要删除的节点的左子树中最大节点的索引。我需要这个，因为这个节点将替换被删除的带有两个子节点的节点。

我的当前代码返回它在子树中看到的第一个节点的索引，因为我的返回实际上被覆盖了。请参见此处：

//find largest node in left subtree and return its index
private int findNew(int index) {
    int r = right[index];
    if(r != -1) {
        findNew(r);
    }
    return index;
}

下面是我实现的remove方法：

private void remove(int d, int index) {
    //we found the data to remove
    if(data[index] == d){
    //removes
        //if the node is a leaf
        if(left[index] == -1 && right[index] == -1) {
            data[index] = -1;
            if(free == -1) {
                free = index;
            } else {
                freeUpdate(index);
            }
            currentSize--;
        }
        //the node has a left child
        else if(left[index] != -1 && right[index] == -1) {
            int l = left[index];
            data[index] = data[l];
            left[index] = left[l];
            right[index] = right[l];
            if(free == -1) {
                free = l;
            } else {
                freeUpdate(l);
            }
            //delete stuff in node that moved
            data[l] = -1;
            right[l] = -1;
            currentSize--;
        }
        //the node has a right child
        else if(left[index] == -1 && right[index] != -1) {
            int r = right[index];
            data[index] = data[r];
            left[index] = left[r];
            right[index] = right[r];
            if(free == -1) {
                free = r;
            } else {
                freeUpdate(r);
            }
            //delete stuff in node that moved
            data[r] = -1;
            right[r] = -1;
            currentSize--;
        }
        //the node has two children
        else {
            int l = left[index];
            int r = right[index];
            int newParent = findNew(l);
            //implement the rest of the remove here
            currentSize--;
        }
    } else {
        //if we have searched the entire tree
        if(index == data.length) {
            return;
        } else {
            //keep searching for d
            remove(d, index + 1);
        }
    }
}

类的属性和构造函数：

private int root;
private int free;
private int left[];
private int data[];
private int right[];
private int currentSize;

public BoundedBST(int size) {
    root = -1;
    free = -1;
    left = new int[size];
    data = new int[size];
    right = new int[size];
    currentSize = 0;
}

public boolean full() {
    return free == -1 && currentSize == data.length;
}

我知道这个实现没有多大意义，但这就是我正在做的。我知道findNew方法可以很容易地通过使用一个循环来实现，但是我在这里做不到。

本质上，我只是想找到一种方法，让我的findNew方法递归地工作，而不覆盖最后一次调用返回的内容。我理解这里发生的错误，但我不知道如何实现这样一个仍然可以具有非无效返回类型的函数。

Answer 1

findNew的问题是，当您进行递归调用时，您不会对递归调用返回的内容进行任何处理。该值被忽略，并且在所有情况下都返回索引。这使得递归调用无用。

实际上，您应该捕获该返回值，并将其再次返回给调用方，以便此索引从递归调用中冒出气泡，直到到达原始调用方。

我还建议给这个函数一个更具描述性的名字：findGreatest：

private int findGreatest(int index) { // Use a better name
    int r = right[index];
    if (r != -1) {
        return findGreatest(r); // Must do something with the value returned!
    }
    return index;
}

这解决了您询问的问题。但是您仍然需要完成您编写的“在此处实现删除的其余部分”的部分。我建议您继续努力。如果您在这样做时遇到特定问题，请随时提出有关此的新问题。

最后，在决定一切都好之前，请确保在许多不同的场景中彻底测试您的解决方案。