2014-01-19 53 views
0

這是我的班級節點,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); 
} 

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

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

在你的第二個版本
+1

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

回答

1

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

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

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

+0

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

+0

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

+1

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

0

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

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

+0

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

+0

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

0

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