12,406,098 members (39,138 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
 OriginalGriff 366 Karthik Bangalore 179 BillWoodruff 165 ppolymorphe 144 Richard Deeming 125
 OriginalGriff 7,747 ppolymorphe 3,380 Karthik Bangalore 3,321 Richard MacCutchan 2,472 F-ES Sitecore 2,300