12,999,157 members (46,165 online)
Rate this:
See more:
it is the half man algorithm could you tell me that how does the encode function work!!!

```
public class Node
{
public char Symbol { get; set; }
public int Frequency { get; set; }
public Node Right { get; set; }
public Node Left { get; set; }
public List<bool> Traverse(char symbol, List<bool> data)
{
// Leaf
if (Right == null && Left == null)
{
if (symbol.Equals(this.Symbol))
{
return data;
}
else
{
return null;
}
}
else
{
List<bool> left = null;
List<bool> right = null;
if (Left != null)
{
List<bool> leftPath = new List<bool>();
left = Left.Traverse(symbol, leftPath);
}
if (Right != null)
{
List<bool> rightPath = new List<bool>();
right = Right.Traverse(symbol, rightPath);
}
if (left != null)
{
return left;
}
else
{
return right;
}
}
}
}
```

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace HuffmanTest
{
public class HuffmanTree
{
private List<Node> nodes = new List<Node>();
public Node Root { get; set; }
public Dictionary<char, int> Frequencies = new Dictionary<char, int>();
public void Build(string source)
{
for (int i = 0; i < source.Length; i++)
{
if (!Frequencies.ContainsKey(source[i]))
{
}
Frequencies[source[i]]++;
}
foreach (KeyValuePair<char, int> symbol in Frequencies)
{
nodes.Add(new Node() { Symbol = symbol.Key, Frequency = symbol.Value });
}
while (nodes.Count > 1)
{
List<Node> orderedNodes = nodes.OrderBy(node => node.Frequency).ToList<Node>();
if (orderedNodes.Count >= 2)
{
// Take first two items
List<Node> taken = orderedNodes.Take(2).ToList<Node>();
// Create a parent node by combining the frequencies
Node parent = new Node()
{
Symbol = '*',
Frequency = taken[0].Frequency + taken[1].Frequency,
Left = taken[0],
Right = taken[1]
};
nodes.Remove(taken[0]);
nodes.Remove(taken[1]);
}
this.Root = nodes.FirstOrDefault();
}
}
public BitArray Encode(string source)
{
List<bool> encodedSource = new List<bool>();
for (int i = 0; i < source.Length; i++)
{
List<bool> encodedSymbol = this.Root.Traverse(source[i], new List<bool>());
}
BitArray bits = new BitArray(encodedSource.ToArray());
return bits;
}
public string Decode(BitArray bits)
{
Node current = this.Root;
string decoded = "";
foreach (bool bit in bits)
{
if (bit)
{
if (current.Right != null)
{
current = current.Right;
}
}
else
{
if (current.Left != null)
{
current = current.Left;
}
}
if (IsLeaf(current))
{
decoded += current.Symbol;
current = this.Root;
}
}
return decoded;
}
public bool IsLeaf(Node node)
{
return (node.Left == null && node.Right == null);
}
}
```
Posted 1-Jun-12 22:21pm
Updated 2-Jun-12 21:52pm
v3
OriginalGriff 3-Jun-12 4:30am

Don't bump your question - add information if there is extra, but otherwise it is just rude.

Rate this:

## Solution 1

See here[^] for details on this algorithm.

Top Experts
Last 24hrsThis month
 Jochen Arndt 100 RickZeeland 96 Dave Kreskowiak 60 Peter Leow 50 Raghu112 50
 OriginalGriff 4,527 ppolymorphe 2,252 Kornfeld Eliyahu Peter 1,973 RickZeeland 1,967 Richard Deeming 1,593