Hufman.cs

using System;
using System.Collections.Generic;

namespace HuffmanTest
{

	class Node
	{
		public Node Left;
		public Node Right;
		public bool HasSymbol;
		public byte Symbol;
		public int Value;

		public override string ToString()
		{
			return string.Format("Node: {0} {1}", Value, HasSymbol ? Symbol : 0);
		}
	}

	class Huffman
	{
		LinkedList<Node> items;
		Dictionary<byte, int> table;

		public Huffman(Dictionary<byte, int> table)
		{
			this.table = table;
			items = new LinkedList<Node>();
			foreach (var kv in table)
			{
				Node newBaseNode = new Node() { HasSymbol = true, Symbol = kv.Key, Value = kv.Value };
				items.AddFirst(newBaseNode);
			}

			Node bestNode = null;

			while (items.Count > 1)
			{
				Node leftNode = GetWorstSymbol();
				if (leftNode == null)
					break;
				items.Remove(leftNode);
				Node rightNode = GetWorstSymbol();
				if (rightNode == null)
					break;
				items.Remove(rightNode);
              
				Node parentNode = new Node()
				{
					Value = leftNode.Value + rightNode.Value,
					Left = leftNode,
					Right = rightNode,
				};


				items.AddFirst(parentNode);

				bestNode = GetBestNode();

			}

			PrintNodes(bestNode);
		}

        private void PrintNodes(Node root)
		{
			if (root == null)
				return;
			Console.WriteLine("Left {0}, Right {1} [Parent {2}]", root.Left, root.Right, root);
			PrintNodes(root.Left);
			PrintNodes(root.Right);
		}

        private Node GetBestNode()
		{
			Node bestNode = null;
			int highestValue = int.MinValue;

            foreach (Node node in items)
            {
				if (node.Value > highestValue)
                {
					bestNode = node;
					highestValue = node.Value;
                }
            }

            return bestNode;
		}

		private Node GetWorstSymbol()
		{
			Node worstNode = null;
			int lowestValue = int.MaxValue;

			foreach (Node node in items)
			{
				if (node.Value < lowestValue)
				{
					worstNode = node;
					lowestValue = node.Value;
				}
			}

			return worstNode;
		}
	}

	class MainClass
	{
		public static void Main(string[] args)
		{
			

			Dictionary<byte, int> table = new Dictionary<byte, int>();
			table.Add(1, 50);
			table.Add(2, 40);
			table.Add(3, 10);
			table.Add(4, 80);
			table.Add(5, 110);

			Huffman huffman = new Huffman(table);

			Console.ReadLine();
		}
	}
}