c++ - Huffman Decoding Algorithm -

c++ - Huffman Decoding Algorithm -

i having problem building construction of huffman tree when decoding.

right encoding tree if has children making prefix 0 , if has no kid create 1.

for example, tree (a,b,c,d) encoded 001a1b01c1d , huffman code is

00|01|10|11

note: | added clarity , not in header.

here’s tree in graphical form:

/ \ /\ /\ b c d

right when trying rebuild tree using 001a1b01c1d, problem having problem recreating tree because unsure check when going tree (how far go up).

here code index added seek word 'random' doesn't work other cases. thinking of using depth of tree somehow

void tree::build(std::queue<char> encodedheader) { char currentchar; -> thisroot = new hcnode(0, '\0',0,0,0); hcnode * newroot = new hcnode (0,'\0',0,0,0); hcnode * childzero = new hcnode (0, '\0', 0,0,0); hcnode * childone = new hcnode (0, '\0', 0,0,0); childzero -> p = newroot; childone -> p = newroot; newroot -> c0 = childzero; newroot -> c1 = childone; -> foreverroot = newroot; while(!header.empty()) { currentchar = header.front(); header.pop(); if(currentchar != '\n') { if (currentchar == '0') { hcnode * childzero = new hcnode (0, '\0', 0,0,0); hcnode * childone = new hcnode (0, '\0', 0,0,0); child0 -> p = newroot; child1 -> p = newroot; newroot -> c0 = childzero; newroot -> c1 = childone; currentchar = header.front(); while (currentchar == '0') { newroot = newroot -> c0; header.pop(); currentchar = header.front(); hcnode * childzero = new hcnode (0, '\0', 0,0,0); hcnode * childone = new hcnode (0, '\0', 0,0,0); childzero -> p = newroot; childone -> p = newroot; newroot -> c0 = childzero; newroot -> c1 = childone; } } else { currentchar = header.front(); header.pop(); if(newroot -> c0 != null) { newroot -> c0 -> symbol = currentchar; newroot = newroot -> c1; } else { newroot -> symbol = currentchar; while(newroot -> p != null && index != 2) { index++; newroot = newroot -> p; } index = 0; newroot = newroot -> c1; } } } }

i literally wrote code exercise, , you're using same header format did. trick found much easier implement recursively, in:

node read_tree(some_input input, string current_code = "") { node node; if (input.readchar() == '0') { node.left = read_tree(input, current_code + "0"); node.left.parent = node; node.right = read_tree(input, current_code + "1"); node.right.parent = node; } else { node.code = input.readchar(); } homecoming node; }

obviously you'll need similar using own more realistic types, basic thought should work.

c++ algorithm huffman-coding