构造哈夫曼树,并且生成哈夫曼编码。编写程序,完成树构造、生成编码,见图https://postimg.cc/WD6crYTn。给出程序代码,生成哈夫曼编码可以从叶子到根,也可以使用堆栈从树根开始遍历哈夫曼树。 (1) C#编写程序,生成哈夫曼Huffman树,同时得到哈夫曼编码,显示https://postimg.cc/WD6crYTn中内容——数组在生成前、后情况,哈夫曼编码。给出程序代码。 (2) 生成哈夫曼Huffman树的结点二叉树,文件夹“3-3结点二叉树”中,例子表示结点二叉树的生成及显示(遍历)。 A、 新建哈夫曼二叉树结点类HTNode,写出类的定义。 B、 建立结构HTElemType C、 编写算法,完成二叉树生成。补充图片https://postimg.cc/B81Cttf9
时间: 2024-02-06 19:13:09 浏览: 131
对于问题1,以下是C#程序代码,实现哈夫曼树的构建和编码的生成:
```csharp
using System;
using System.Collections.Generic;
namespace HuffmanCoding
{
class Program
{
static void Main(string[] args)
{
string str = "abacabadabacaba";
Dictionary<char, int> freq = new Dictionary<char, int>();
// 统计字符频率
foreach (char c in str)
{
if (freq.ContainsKey(c))
freq[c]++;
else
freq[c] = 1;
}
// 构造哈夫曼树
List<HTNode> nodes = new List<HTNode>();
foreach (KeyValuePair<char, int> p in freq)
{
nodes.Add(new HTNode(p.Key, p.Value));
}
HuffmanTree tree = new HuffmanTree(nodes);
// 生成哈夫曼编码
Dictionary<char, string> encoding = tree.GenerateEncoding();
// 显示结果
Console.WriteLine("字符频率:");
foreach (KeyValuePair<char, int> p in freq)
{
Console.WriteLine(p.Key + ": " + p.Value);
}
Console.WriteLine("\n哈夫曼编码:");
foreach (KeyValuePair<char, string> p in encoding)
{
Console.WriteLine(p.Key + ": " + p.Value);
}
Console.ReadLine();
}
}
class HuffmanTree
{
HTNode root; // 哈夫曼树的根节点
public HuffmanTree(List<HTNode> nodes)
{
BuildTree(nodes);
}
// 构造哈夫曼树
private void BuildTree(List<HTNode> nodes)
{
while (nodes.Count > 1)
{
// 找出权值最小的两个节点
nodes.Sort();
HTNode left = nodes[0];
HTNode right = nodes[1];
// 创建新节点作为两个节点的父节点
HTNode parent = new HTNode('\0', left.Weight + right.Weight);
parent.LeftChild = left;
parent.RightChild = right;
// 移除已处理的节点,添加新节点
nodes.Remove(left);
nodes.Remove(right);
nodes.Add(parent);
}
root = nodes[0];
}
// 生成哈夫曼编码
public Dictionary<char, string> GenerateEncoding()
{
Dictionary<char, string> encoding = new Dictionary<char, string>();
GenerateEncoding(root, "", encoding);
return encoding;
}
// 递归生成哈夫曼编码
private void GenerateEncoding(HTNode node, string code, Dictionary<char, string> encoding)
{
if (node.IsLeaf())
{
encoding[node.Symbol] = code;
}
else
{
GenerateEncoding(node.LeftChild, code + "0", encoding);
GenerateEncoding(node.RightChild, code + "1", encoding);
}
}
}
// 哈夫曼树节点类
class HTNode : IComparable<HTNode>
{
public char Symbol { get; set; } // 节点代表的符号
public int Weight { get; set; } // 权值
public HTNode LeftChild { get; set; } // 左子节点
public HTNode RightChild { get; set; } // 右子节点
public HTNode(char symbol, int weight)
{
this.Symbol = symbol;
this.Weight = weight;
}
public bool IsLeaf()
{
return LeftChild == null && RightChild == null;
}
public int CompareTo(HTNode other)
{
return this.Weight - other.Weight;
}
}
}
```
对于问题2,以下是类的定义和算法实现:
```csharp
// 哈夫曼树节点类
class HTNode
{
public HTElemType Data { get; set; } // 节点数据
public HTNode LeftChild { get; set; } // 左子节点
public HTNode RightChild { get; set; } // 右子节点
public HTNode(HTElemType data)
{
this.Data = data;
}
}
// 哈夫曼树元素类型
struct HTElemType
{
public char Symbol { get; set; } // 符号
public int Weight { get; set; } // 权值
}
// 哈夫曼树类
class HuffmanTree
{
HTNode root; // 哈夫曼树的根节点
public HuffmanTree(List<HTElemType> elems)
{
BuildTree(elems);
}
// 构造哈夫曼树
private void BuildTree(List<HTElemType> elems)
{
List<HTNode> nodes = new List<HTNode>();
foreach (HTElemType elem in elems)
{
nodes.Add(new HTNode(elem));
}
while (nodes.Count > 1)
{
// 找出权值最小的两个节点
nodes.Sort((a, b) => a.Data.Weight - b.Data.Weight);
HTNode left = nodes[0];
HTNode right = nodes[1];
// 创建新节点作为两个节点的父节点
HTNode parent = new HTNode(new HTElemType { Symbol = '\0', Weight = left.Data.Weight + right.Data.Weight });
parent.LeftChild = left;
parent.RightChild = right;
// 移除已处理的节点,添加新节点
nodes.Remove(left);
nodes.Remove(right);
nodes.Add(parent);
}
root = nodes[0];
}
// 前序遍历哈夫曼树
public void PreOrderTraversal()
{
PreOrderTraversal(root);
}
private void PreOrderTraversal(HTNode node)
{
if (node != null)
{
Console.WriteLine(node.Data.Symbol + " " + node.Data.Weight);
PreOrderTraversal(node.LeftChild);
PreOrderTraversal(node.RightChild);
}
}
}
```
阅读全文