Huffman Coding Trees - https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/Huffman.html

HuffTree.cs

using System;
using System.Collections.Generic;

public interface HuffBaseNode {
  bool isLeaf();
  int weight();
}

public class HuffLeafNode : HuffBaseNode {
  private char _element;
  private int _weight;

  // Constructor
  public HuffLeafNode(char el, int wt) {
    this._element = el; this._weight = wt;
  }

  public char value() { return this._element;}
  public int weight() { return this._weight;}
  public bool isLeaf() { return true; }
}

public class HuffInternalNode : HuffBaseNode {
  private int _weight;
  private HuffBaseNode _left;
  private HuffBaseNode _right;

  // Constructor
  public HuffInternalNode(HuffBaseNode l, HuffBaseNode r, int wt) {
    this._left = l;
    this._right = r;
    this._weight = wt;
  }

  public HuffBaseNode left() { return this._left;}
  public HuffBaseNode right() { return this._right;}
  public int weight() { return this._weight;}
  public bool isLeaf() { return false;}
}

class HuffTree : IComparable {
  private HuffBaseNode _root;

  // Constructors
  public HuffTree(char el, int wt) {
    this._root = new HuffLeafNode(el, wt);
  }
  public HuffTree(HuffBaseNode l, HuffBaseNode r, int wt) {
    this._root = new HuffInternalNode(l, r, wt);
  }

  public HuffBaseNode root() { return this._root;}
  public int weight() { return this._root.weight(); }
  public int CompareTo(Object t) {
    HuffTree that = (HuffTree) t;
    if(this._root.weight() < that.weight()) { return -1; }
    else if (this._root.weight() == that.weight()) { return 0; }
    else { return 1; }
  }  
  public static HuffTree BuildTree(PriorityQueue<HuffTree, int> Hheap) {
    HuffTree tmp1, tmp2, tmp3 = null;
    while(Hheap.Count > 1) {
      tmp1 = Hheap.Dequeue();
      tmp2 = Hheap.Dequeue();
      tmp3 = new HuffTree(tmp1.root(), tmp2.root(), tmp1.weight() + tmp2.weight());

      Hheap.Enqueue(tmp3, tmp3.weight());
    }
    return tmp3;
  }
}