c++ - 这种遍历二叉树的递归方法在一些递归后崩溃了!为什么？

Question

这是我的 Node 类，Traverse 是一种访问霍夫曼二叉树并保存 .txt 文件字符代码的方法。 Codes 是我保存代码的字符串 vector 。 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);
}

我相信您的回答。谢谢。

编辑:我已经尝试检查右 child 是否为空，但它总是行不通。

Answer 1

在你的第二个版本中，你检查当前节点的左节点:

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

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