Java BinarySearchTree 和变量中的递归

Question

我在理解以下内容时遇到问题:

public int sort(char[] arr, int index)
{
    if(!isEmpty())
    {
        index = leftChild.sort(arr,index);
        arr[index++] = getContent().getToken();
        index = rightChild.sort(arr,index);

    }
    return index;
}

为什么这个有效，但这个不行:

public void sort(char[] arr, int index)
{
    if(!isEmpty())
    {
        leftChild.sort(arr,index);
        arr[index++] = getContent().getToken();
        rightChild.sort(arr,index);

    }
}

我也不明白这一点:index = leftChild.sort(arr,index);这是做什么的？你们能给我举个例子吗？感谢您的帮助，

基马里

还有一个问题，我有一种方法可以打印从二叉树的根到叶子的最长路径:

public int height()
{
if ( !isEmpty() )
{
    int leftHeight = leftChild.height();
    int rightHeight = rightChild.height();
    if ( leftHeight > rightHeight )
    {
        return leftHeight + 1;
    } else {
        return rightHeight + 1;
    }
} else {
    return 0;
}

}

但是如果没有人有值，如何做到 leftHeight > rightHeight 呢？它们都是零或者什么，那么他如何比较呢？谢谢!

Answer 1

您的方法执行二叉搜索树的中序遍历。

第一个片段首先调用leftChild.sort(arr,index)，它将左子树分配给输入数组。它返回要分配的下一个索引。

然后将当前节点的getContent().getToken()分配给arr[index]

然后调用 rightChild.sort(arr,index) 将右子树分配给输入数组，并返回要分配的下一个 index。

如果您忽略递归调用返回的index(正如您在第二个代码片段中所做的那样)，arr[index++] = getContent().getToken();将始终为数组的 0 索引分配一个值(假设初始调用为 (sort(arr,0)))。

您必须将返回的索引分配给本地 index 变量，以便将 getContent().getToken() 分配给正确的 index数组的。