從預先遍歷構建二叉樹：堆棧溢出錯誤

我有一棵樹，樹葉標記爲L，非葉節點標記爲I.我給出樹的前序遍歷。一個例子是IIILLILILLIIILLLIILILLL。我必須爲這個包含的字符串構建huffman樹。我最初傳入一個新的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); 
}

我不知道是什麼原因造成的計算器引發異常。我認爲我的基本情況在一開始就會返回並處理它。

來源

2014-12-07 ComicStix

我認爲這就是問題所在：

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

我不知道你的方法是什麼，但它看起來像如果你看到一個I，你的計劃是去左節點，並啓動檢查從下一個字符開始的字符串。

無限遞歸的原因是start++是一個後增加運算符，這意味着它給你當前值start，然後遞增它。因此，每調用一次makeTree調用它自己，就會調用它自己的start相同版本，因此在輸入字符串中查看相同的I。

但是，將其更改爲++start不會使事情順利進行。（它可能會避免堆棧溢出，但它不會正常工作。）原因是，當您撥打makeTree時，您想要給它一個您希望遞歸調用開始查找的字符串的起始位置 - 但你也需要遞歸調用來告訴它它消耗了多少字符串。這是必要的，因爲在makeTree在getLeftChild上遞歸調用本身之後，您將在getRightChild上再次調用它，並且您需要用正確的起點調用它。

請注意，每個遞歸調用都有自己的副本start。因此，當makeTree自己調用，而第二個makeTree增量爲start時，這對第一個makeTree看到的start沒有影響。

您將需要每次遞歸makeTree告訴其調用者它消耗了多少字符串。可能最簡單的方法是將返回類型更改爲int;您可以決定是否要將函數結果作爲消耗的字符數或停止掃描的索引或類似內容。然後，遞歸調用makeTree後，使用函數結果調整start參數。確保makeTree在葉子和非葉子情況下均返回正確的結果。小心避免逐個錯誤。

來源

2014-12-07 01:29:14 ajb

不得不完全重新做我的樹，但它結束了工作。謝謝。我不記得後和增量運營商之間的差異 – ComicStix 2014-12-17 04:58:09

只能從預訂列表中創建樹。至少你需要遍歷以及如果是完整的樹，那麼你也可以使用posror。

來源

2014-12-07 04:44:24 Ouney

從預先遍歷構建二叉樹：堆棧溢出錯誤

回答

相關問題