如何定义哈夫曼树结点的数据结构?与普通二叉树有什么不同?
时间: 2024-05-17 18:19:40 浏览: 156
哈夫曼树结点的数据结构与普通二叉树的结点类似,都包括父节点指针、左右子节点指针和数据域。但是,哈夫曼树结点的数据域不是一个普通的数据项,而是一个权值。这个权值通常表示某个字符在文本中出现的频率。
在哈夫曼树中,每个结点都有一个权值,通过不断合并权值较小的结点,最终得到根节点,形成一棵完整的哈夫曼树。因此,哈夫曼树的结点不一定都有左右子节点,只有叶子结点才有数据项和没有子节点。
另外,哈夫曼树还有一个独特的特点:所有叶子结点的深度是相等的,这是为了保证哈夫曼编码的唯一性和最优性。因此,构建哈夫曼树时需要采用贪心算法,每次选择权值最小的两个结点进行合并。
相关问题
构造哈夫曼树,并且生成哈夫曼编码。编写程序,完成树构造、生成编码,见图https://postimg.cc/WD6crYTn。给出程序代码,生成哈夫曼编码可以从叶子到根,也可以使用堆栈从树根开始遍历哈夫曼树。 (1) C#编写程序,生成哈夫曼Huffman树,同时得到哈夫曼编码,显示https://postimg.cc/WD6crYTn中内容——数组在生成前、后情况,哈夫曼编码。给出程序代码。 (2) 生成哈夫曼Huffman树的结点二叉树,文件夹“3-3结点二叉树”中,例子表示结点二叉树的生成及显示(遍历)。 A、 新建哈夫曼二叉树结点类HTNode,写出类的定义。 B、 建立结构HTElemType C、 编写算法,完成二叉树生成。补充图片https://postimg.cc/B81Cttf9
对于问题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);
}
}
}
```
阅读全文