I see two questions here:
How to have a recursive function continue in order to process the remaining string after the first output is generated?
Although you have provided code that does this in a certain way, that is not the way to approach it. You'd better unwind from recursion before decoding for the next output.
How to build a tree without having to code as many new Node() assignments as there are nodes in the tree?
But first:
The Node class
This is about Huffman encoding/decoding. As your tree would be a full binary tree, where its leaves have character data, I would:
- include a constructor that takes
left and right as arguments, with the goal to set the instance members directly during construction, and not later.
- make members immutable, to bring the first point home.
- enforce that the tree is a full binary tree, i.e. no node should have just one child.
- set the type of the
data member to char and not string: you'd only store single characters there.
The Node class could then be like this:
class Node {
private:
const char data = '.';
const Node *left = nullptr;
const Node *right = nullptr;
public:
Node() {}
Node(char data) : data(data) {}
Node(Node* left, Node* right) : left(left), right(right) {
if (!left || !right) { // Apply full binary tree constraint
std::cout << "Node constructor arguments should be non-null\n";
exit(1);
}
}
bool is_leaf() const {
return !left && !right;
}
}
The first question: unwinding from recursion
I can't wrap my head around the "conditional" recursion. I am especially stuck on having the function to continue to process the string after the first "1".
A recursive approach can be fine, even though it is a case of tail recursion and would be suitable for a plain loop. But to continue deepening the recursion at each input character, as done by the code you shared, is a stretch. A logical state where you would exit the recursion tree is where you retrieve a decoded character from a leaf of the binary tree. At that point completely unwind from recursion. That way the recursion depth will never be more than the height of your binary tree: it will invariably match the depth of the current node in the binary tree.
So you would restart the recursion from scratch when starting the decoding for a new output. To achieve this, make the recursive function such that it only deals with generating one output character. Leave it for the caller to initiate the next call from the top.
Also, I would build a string and not use cout in your function. Leave that to the caller of the function, or whatever else they want to do with the decoded string that the function can return.
Here is a method you could have on the Node class, which uses recursion to decode characters for just one output, by traversing the binary tree from the root to one of its leaves. It takes a character pointer which it updates so that after a call of this function, a next call will continue from where it stopped:
std::string decode_one(char* &chr_ptr) const {
return is_leaf() ? data
: !*chr_ptr ? "" // message is not a valid encoding
: (*chr_ptr == '0' ? left : right)->decode_one(++chr_ptr); // Recur
}
Use this method in another method that decodes a whole string:
std::string decode(std::string unambiguous_message) const {
char* chr_ptr = unambiguous_message.data();
std::string decoded = "";
while (*chr_ptr) decoded += decode_one(chr_ptr);
return decoded;
}
Now you can call it as a method:
std::cout << root->decode("01111");
The second question: building the tree
is [there] a better way to translate the bt from the image to code.
I take this as a question for a more generic approach that does not need one line of new Node() code for each node of your tree. One idea is to create a function that takes as input some encoding for the desired tree, like a pre-order sequence for it.
static Node *from_pre_order(char* &chr_ptr) {
char ch = *chr_ptr;
if (!ch) {
std::cout << "Unexpected end of pre-order input\n";
exit(1);
}
if (ch != '.') return new Node(ch);
Node* save_left = from_pre_order(++chr_ptr);
return new Node(save_left, from_pre_order(++chr_ptr));
}
To facilitate calling this function with a string argument, add this wrapper:
static Node *from_pre_order(std::string pre_order) {
char* chr_ptr = pre_order.data();
return from_pre_order(chr_ptr);
}
The example tree you used could now be created as follows:
Node *root = Node::from_pre_order(".B..CDA");
NB: In practice you would build a tree based on some message that needs encoding, using the Huffman encoding algorithm.
Result
Here is all of the above put together with an example call:
#include <iostream>
#include <vector>
class Node {
private:
const char data = '.';
const Node *left = nullptr;
const Node *right = nullptr;
public:
Node() {}
Node(char data) : data(data) {}
Node(Node* left, Node* right) : left(left), right(right) {
if (!left || !right) { // Apply full binary tree constraint
std::cout << "Node constructor arguments should be non-null\n";
exit(1);
}
}
bool is_leaf() const {
return !left && !right;
}
char decode_one(char* &chr_ptr) const {
return is_leaf() ? data
: !*chr_ptr ? '\0' // message is not a valid encoding
: (*chr_ptr == '0' ? left : right)->decode_one(++chr_ptr); // Recur
}
std::string decode(std::string unambiguous_message) const {
char* chr_ptr = unambiguous_message.data();
std::string decoded = "";
while (*chr_ptr) decoded += decode_one(chr_ptr);
return decoded;
}
static Node *from_pre_order(char* &chr_ptr) {
char ch = *chr_ptr;
if (!ch) {
std::cout << "Unexpected end of pre-order input\n";
exit(1);
}
if (ch != '.') return new Node(ch);
Node* save_left = from_pre_order(++chr_ptr);
return new Node(save_left, from_pre_order(++chr_ptr));
}
static Node *from_pre_order(std::string pre_order) {
char* chr_ptr = pre_order.data();
return from_pre_order(chr_ptr);
}
};
int main() {
Node *root = Node::from_pre_order(".B..CDA");
std::cout << root->decode("01111") << "\n";
return 0;
}
