这种遍历二叉树的递归方法在一些递归后崩溃！为什么?

Question

这是我的类节点，Traverse是一种访问霍夫曼二叉树并保存.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);
}

我相信你的答案。 谢谢。

编辑：我已经尝试检查正确的孩子是否为空，但它总是不起作用。

Answer 1

在第二个版本中，您检查当前节点的左侧节点：

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

然后你遍历左节点和右节点，但你不检查右节点是否未null，对于这个右节点，递归调用将再次检查p->Left，但由于 p 可能为 null(当你到达树叶时)，该方法将崩溃。

Answer 2

两个版本都已损坏 - 您忘记在遍历之前检查正确的子树是否为 null。

第一个版本似乎有效只是运气不好，它会给你一些输入带来问题。

Answer 3

我解决了！在上面的class Node中，我忘了写Ch成员及其GetChar()方法。Ch是一个无符号的字符，而该方法GetChar()返回一个字符，所以在特殊字符的情况下Codes[p->GetChar()]崩溃！