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

Question

我有三个类似于此示例的数组：

左右数组为当前索引左右children的索引号。如果其中一个为 -1，则 child 不存在。如果两者都为 -1，则索引处的节点是叶节点。我知道这在 real-world 场景中实施并没有多大意义，但这是针对作业的。

无论如何，我正在尝试在 class 中实现一个 remove 方法来实现这个想法。除了节点有两个 children 的情况外，我让它适用于所有情况。我这里的问题是，我正在调用一个递归方法（我创建的所有方法都必须是递归的），该方法应该 return 包含我要删除的节点的左子树中最大节点的索引。我需要这个，因为这是将要用两个正在删除的 children 替换节点的节点。

我当前的代码 return 是它在子树中看到的第一个节点的索引，因为我的 return 基本上被覆盖了。看这里：

//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;
}

这是我实现的删除方法：

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);
        }
    }
}

class 的属性和构造函数：

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 方法递归工作，而不会覆盖上次调用 returned 的内容。我了解这里发生的错误，但我不知道如何实现这样一个仍然可以具有 non-void return 类型的函数。

Answer 1

findNew 的问题在于，当您进行递归调用时，您不会对该递归调用 return 执行任何操作。该值将被忽略，在所有情况下，您 return index。这使得递归调用无用。

您实际上应该捕获那个 return 值，然后 return 再次将其返回给调用者，以便该索引从递归调用中冒出，直到它到达原始调用者。

我还建议给这个函数起一个更具描述性的名称：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;
}

这解决了您提出的问题。但是你仍然需要完成你写的部分“在此处实现其余的删除”。我建议你在这方面努力。如果您在执行此操作时遇到具体问题，请随时提出新问题。

最后，请确保在许多不同的场景中彻底测试您的解决方案，然后再决定是否一切正常。

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

How to find the index of the maximum value in a Binary Search Tree array implementation?

java

arrays

binary-search-tree