我创建了一个程序,到目前为止,它为 Huffman 编码程序创建了一个节点的二叉树。出于某种原因,当调试器到达它测试两个孩子是否等于 Null 的地步(因此树上有一个实际字符而不仅仅是一个父级)时,程序会冻结。Codes 是每个对象的代码数组,由具有两个成员变量的 Code 结构组成。
void Huff::traverse(Node* root, vector<Code>* code, string code_base){
if(root->childL == NULL && root->childR == NULL){ //stops here
Code c;
c.content = root->litteral;
c.symbol = code_base;
code->push_back(c);
}else{
if (root->childL != NULL)
traverse(root->childL, code, code_base + '0');
if (root->childR != NULL)
traverse(root->childR, code, code_base + '1');
}
}
调用这个的函数是(它在最后被调用):
vector<Code>* Huff::compress(){
//-------GETTING WEIGHTS/FREQUENCIES------
vector<Node *>* nodes = new vector<Node*>; // Vector of nodes for later use
map<char, int>* freq = new map<char, int>; // Map to find weight of nodes
for(unsigned int i = 0; i < content.length(); i++)
(*freq)[content[i]]++;
CopyTo copyto(nodes); //sets vector<Node*> to copy to
for_each(freq->begin(), freq->end(), copyto); // Copies
delete freq;
vector<Node *>::iterator beg = nodes->begin();
//-------SETTING UP TO BUILD TREE------
if(nodes->size() % 2 == 1){ //makes sure there are an even number of nodes
Node* fill = new Node;
fill->set_node(0, '*', NULL, NULL);
nodes->push_back(fill);
}
huff_sort(nodes); // sort nodes by weight
//-------BUILDING TREE------
while(nodes->size() != 1){ //Sorts nodes by weight and then removes two of them and replaces them with one
int w= (**beg).weight + (**(beg+1)).weight;
Node* p = new Node;
p->set_node(w, '*', *nodes->begin(), *(nodes->begin()+1)); //making it the parent node of the two lowest nodes
nodes->erase(nodes->begin(), nodes->begin()+2);
unsigned int i = 0;
while(w > (*nodes)[i]->weight && i <= nodes->size()){ //finds where to insert the parent node based on weight
i++;
}
if(i > nodes->size()) //if it needs to be inserted at the end
nodes->push_back(p);
else
nodes->insert(nodes->begin()+i, p);
delete p;
}
//-------TRAVERSING TREE------
Node* root = (*nodes)[0];
delete nodes;
vector<Code>* codes;
traverse(root, codes , "");
delete root;
return codes;
}
注意:遍历树代码块之前的while循环是创建树的地方