java - java中的递归函数用字典填充二叉树

Question

我正在尝试在 Java 中编写一个递归函数，它采用一个按字母顺序排列的包含单词的数组列表，并尽可能地填充树。据我所知，我遇到的问题是 java 没有通过引用传递，所以在我的递归函数中，我实际上从未更新树的左右分支指向的位置，这意味着树的顶部永远不会指向任何东西。有没有更好的(有效的)方法来做到这一点？我是否在一开始尝试填充树时完全错过了标记？

public void saveNode(BinaryTreeNode parent, int left, int right)
{
    int middle = (int) Math.ceil(((double)(right-left))/2.0);
    int curIndex;
    curIndex = middle+left;

    parent = new BinaryTreeNode(words.get(curIndex));

    if(middle != 1)
    {
        saveNode(parent.left, left, curIndex);
        saveNode(parent.right, curIndex, right);
    }
}

PS:我对java比较陌生

Answer 1

你的问题是当你执行

parent = new BinaryTreeNode(words.get(curIndex));

就调用者而言，这不会为 parent 赋值，因此它不会传播回调用堆栈。

你希望代码看起来像这样(去掉与问题无关的代码):

public static void main(String[] args) {
    // keep a reference to the root node so you can access the tree after loading
    BinaryTreeNode root = new BinaryTreeNode();
    // pass the root node into the first call to the recursive method
    saveNode(root, left, right);
}

public void saveNode(BinaryTreeNode parent, int left, int right) {
    // keep building your tree as you descend into it
    parent.left = new BinaryTreeNode();
    parent.right = new BinaryTreeNode();
    // pass the (new) branches into deeper calls     
    saveNode(parent.left, left, curIndex);
    saveNode(parent.right, curIndex, right);
}