How to create a right bounded tree from a normal tree in C (Huffman)?-CodePudding

How to build a right bounded Huffman tree (so that the depth of any left child on any node is not larger than the depth on the right child on this node).

I already have a Huffman tree from here. The LeafNode's are the one with the symbols on it and no children and the InternalNode's are the one that have children.
My Idea would be to make a normal Huffman tree first and then sort it. To do this (every symbol should have the same amount of bits afterwards) I would go through the created Huffman tree and sort every Node in one row by their (largest) depth.

Does anyone have a good Idea how to program this in C or an easier solution to build a right bounded Huffman tree?

CodePudding user response：

One way to build a right-bounded Huffman tree is to modify the standard Huffman tree building algorithm. Here's one way to do it in C :

void buildRightBoundedTree(Node* root) {
if (root == nullptr) return;

// Compare the depth of the left and right children
if (root->left->depth > root->right->depth) {
    // Swap the children
    Node* temp = root->left;
    root->left = root->right;
    root->right = temp;
}

// Recursively apply the procedure to the children
buildRightBoundedTree(root->left);
buildRightBoundedTree(root->right);
}