這個遍歷二叉樹的遞歸方法在一些遞歸之後崩潰！爲什麼？

這是我的班級節點，Traverse是一種訪問Huffman二叉樹並保存.txt文件字符代碼的方法。 Codes是我保存代碼的字符串向量。 Temp是我將字符的代碼保存到代碼中的臨時字符串。這個遍歷二叉樹的遞歸方法在一些遞歸之後崩潰！爲什麼？

我不明白爲什麼Traverse的第一個版本很好，而第二個在一些遞歸之後崩潰。

typedef class Node *NODE; 

class Node { 
    private: 
     int Key; 
     NODE L; 
     NODE R; 
    public: 
     Node() { L = NULL; R = NULL}; 
     Node(int, NODE, NODE); 
     ~Node() { delete L; delete R;}; 
     NODE Left(); 
     NODE Right(); 
     int GetKey(); 
     void SetKey(int); 
     void Traverse(vector<string>, string) 
     void Traverse(NODE, vector<string>, string) 
};

第一個版本：

void Node::Traverse(vector<string> &Codes, string Temp = "") 
{ 
    if (L != NULL) 
    { 
     L->Traverse(Codes, Temp + "0"); 
     R->Traverse(Codes, Temp + "1"); 
    } 
    else 
    { 
     Codes[Ch] = Temp; 
     Temp.clear(); 
    } 
}

第二個版本：

void Node::Traverse(NODE p, vector<string> &Codes, string Temp = "") 
{ 
    if (p->Left() != NULL) 
    { 
     Traverse(p->Left(), Codes, Temp + "0"); 
     Traverse(p->Right(), Codes, Temp + "1"); 
    } 
    else 
    { 
     Codes[p->GetChar()] = Temp; 
     Temp.clear(); 
    } 
}

主營：

int main() 
{ 
    // I Create the Huffman tree and save it's root into H_Tree pointer to Node. 

    // It works great! 
    H_Tree->Traverse(Codes, Temp); 

    // It doesn't work! 
    H_Tree->Traverse(H_Tree, Codes, Temp); 
}

我在你的答案信任。謝謝。

編輯：我已經試圖檢查是否正確的孩子是空的，但它總是無法正常工作。

在你的第二個版本

來源

2014-01-19 Maghio

你有沒有崩潰的callstack？你知道它正在崩潰的確切指令嗎？ – tumdum

您檢查當前節點的左節點：

if (p->Left() != NULL)

，然後你遍歷左，右節點，但你不檢查是否正確的節點不是null和此遞歸調用的右節點將再次檢查p->Left，但由於p可能爲空（當您到達樹葉時），該方法將崩潰。

來源

2014-01-19 15:46:30 giorashc

我已經嘗試檢查正確的孩子，但它始終不起作用。你的版本也崩潰了。無論如何謝謝你很多。 – Maghio

我刪除了我的解決方案，因爲我注意到如果Codes [p-> GetChar（）]超出範圍，它可能會崩潰。這不會拋出異常，但可能會導致您將temp分配給受保護的內存地址，從而可能導致程序崩潰。 – giorashc

**我解決了問題！**在上面的'class Node'中，我忘記寫入'Ch'成員，並且它的'GetChar（）'方法。 'Ch'是一個** unsigned char **，而方法'GetChar（）'返回一個** char **，所以在特殊字符的情況下，當我調用'Codes [p-> GetChar（）]'時，它會崩潰！ – Maghio

這兩個版本都被破壞了 - 在遍歷它之前，你忘記檢查右邊的子樹是否爲空。

第一個版本似乎工作只是運氣不好，它將給你一些輸入問題。

來源

2014-01-19 15:54:38 molbdnilo

我已經嘗試檢查正確的孩子，但它始終不起作用。 – Maghio

**我解決了！**在上面的'class Node'中，我忘了寫'Ch'成員和它的'GetChar（）'方法。 'Ch'是一個** unsigned char **，而方法'GetChar（）'返回一個** char **，所以在特殊字符的情況下，當我調用'Codes [p-> GetChar（）]'時，它會崩潰！我將在8h運行時寫回答。 – Maghio

我解決了！在上面的class Node中，我忘了寫Ch成員及其GetChar()方法。 Ch是無符號的字符而GetChar()中的特殊字符Codes[p->GetChar()]崩潰的情況下返回焦炭，因此該方法！

來源

2014-01-20 23:54:12 Maghio

這個遍歷二叉樹的遞歸方法在一些遞歸之後崩潰！爲什麼？

回答

相關問題