0

我有一棵树，叶子用 L 标记，非叶子节点用 I 标记。我得到了树的前序遍历。一个例子是 IIILLILILLLIIILLLIILILLL。我必须为这个包含的字符串构建霍夫曼树。我最初为我的参数传入了一个新的 Root()、0 和我的 treeString。TreeString 将是上面粘贴了 I 和 L 的字符串。出于某种原因，我的代码会导致引发 StackOverflow 异常。我的 makeTree 方法的代码如下：

public static void makeTree (BinaryNodeInterface<Character> root, int start, String treeString)
{
    if (treeString.charAt(start)=='L'){

        root.setLeftChild(null);
        root.setRightChild(null);
        return;
    }
    BinaryNodeInterface<Character> leftSide = new BinaryNode<Character>();
    root.setLeftChild(leftSide);
    makeTree(root.getLeftChild(), start++, treeString);
    BinaryNodeInterface<Character> rightSide = new BinaryNode<Character>();
    root.setRightChild(rightSide);
    makeTree(root.getRightChild(), start++, treeString);
}

我不知道是什么导致了 stackoverflow 异常被抛出。我认为我一开始的基本情况会返回并处理它。

4

2 回答 2

0

我相信这是问题所在：

makeTree(root.getLeftChild(), start++, treeString);

我不确定您的方法是什么，但看起来如果您看到一个I，您的计划是转到左侧节点，并从下一个字符开始检查字符串。

无限递归的原因是它start++是一个后增量运算符，这意味着它给你当前的值，start然后递增它。因此，每次makeTree调用自身时，它都使用相同版本的 调用自身，因此在输入字符串中start看起来相同。I

但是，将其更改为++start不会使事情正常进行。 （它可能会避免堆栈溢出，但它不会正常工作。）原因是当你调用时makeTree，你想给它你希望递归调用开始查找的字符串的起始位置——但你也希望递归调用告诉它它消耗了多少字符串。这是必要的，因为在makeTree递归调用自身 on之后getLeftChild，您将再次调用它 on getRightChild，并且您需要以正确的起点调用它。

请注意，每个递归调用都有自己的start. 因此，当makeTree调用自身时，第二个makeTree增量，这对第一个看到start的没有影响。startmakeTree

您会以某种方式需要每个递归makeTree来告诉它的调用者它消耗了多少字符串。可能，最简单的方法是将返回类型更改为int; 您可以决定是否希望函数结果是消耗的字符数，或者停止扫描的索引，或类似的东西。然后，makeTree递归调用后，使用函数结果调整start参数。确保makeTree在叶子和非叶子情况下返回正确的结果。小心避免一个接一个的错误。

于 2014-12-07T01:29:14.167 回答
0

您不能仅从 preOrder 列表中创建树。至少您还需要中序遍历，或者如果是完整的树，那么您也可以使用 posrorder。

于 2014-12-07T04:44:24.500 回答