using System;
002 using System.Collections.Generic;
003 using System.Linq;
004 using System.Text;
005 using System.Collections;
006
007 namespace Huffman
008 {
009     class Node
010     {
011         public int frequency;
012         public string data;
013         public Node leftChild, rightChild;
014
015         public Node(string data, int frequency)
016         {
017             this.data = data;
018             this.frequency = frequency;
019         }
020
021         public Node(Node leftChild, Node rightChild)
022         {
023             this.leftChild = leftChild;
024             this.rightChild = rightChild;
025
026             this.data = leftChild.data + ":" + rightChild.data;
027             this.frequency = leftChild.frequency + rightChild.frequency;
028         }
029     }
030
031     class Program
032     {
033         static void Main(string[] args)
034         {
035             IList<Node> list = new List<Node>();
036
037             //int[] array = new int[]{45, 13, 12, 16, 9, 5};
038             int[] array = new int[] { 18, 25, 21, 17, 5, 14 };
039
040             for (int i = 0; i < array.Length; i++)
041             {
042                 list.Add(new Node("S" + (i + 1), array[i]));
043             }
044
045             Stack<Node> stack = GetSortedStack(list);
046
047             while (stack.Count > 1)
048             {
049                 Node leftChild = stack.Pop();
050                 Node rightChild = stack.Pop();
051
052                 Node parentNode = new Node(leftChild, rightChild);
053
054                 stack.Push(parentNode);
055
056                 stack = GetSortedStack(stack.ToList<Node>());
057             }
058
059             Node parentNode1 = stack.Pop();
060
061             GenerateCode(parentNode1, "");
062
063             DecodeData(parentNode1, parentNode1, 0, "0010011101001111");
064             //DecodeData(parentNode1, parentNode1, 0, "100");
065
066             Console.ReadKey();
067         }
068
069         public static Stack<Node> GetSortedStack(IList<Node> list)
070         {
071             for (int i = 0; i < list.Count; i++)
072             {
073                 for (int j = 0; j < list.Count; j++)
074                 {
075                     if (list[i].frequency > list[j].frequency)
076                     {
077                         Node tempNode = list[j];
078                         list[j] = list[i];
079                         list[i] = tempNode;
080                     }
081                 }
082             }
083
084             Stack<Node> stack = new Stack<Node>();
085
086             for (int j = 0; j < list.Count; j++)
087                 stack.Push(list[j]);
088
089             return stack;
090         }
091
092         public static void GenerateCode(Node parentNode, string code)
093         {
094             if (parentNode != null)
095             {
096                 GenerateCode(parentNode.leftChild, code + "0");
097
098                 if (parentNode.leftChild == null && parentNode.rightChild == null)
099                     Console.WriteLine(parentNode.data + "{" + code + "}");
100
101                 GenerateCode(parentNode.rightChild, code + "1");
102             }
103         }
104
105         public static void DecodeData(Node parentNode, Node currentNode, int pointer, string input)
106         {
107             if (input.Length == pointer)
108             {
109                 if (currentNode.leftChild == null && currentNode.rightChild == null)
110                 {
111                     Console.WriteLine(currentNode.data);
112                 }
113
114                 return;
115             }
116             else
117             {
118                 if (currentNode.leftChild == null && currentNode.rightChild == null)
119                 {
120                     Console.WriteLine(currentNode.data);
121                     DecodeData(parentNode, parentNode, pointer, input);
122                 }
123                 else
124                 {
125                     if (input.Substring(pointer, 1) == "0")
126                     {
127                         DecodeData(parentNode, currentNode.leftChild, ++pointer, input);
128                     }
129                     else
130                     {
131                         DecodeData(parentNode, currentNode.rightChild, ++pointer, input);
132                     }
133                 }
134             }
135         }
136     }
137 }