数据结构-Huffman树构造

这是一篇关于数据结构-Huffman树构造的思维导图，包括codetrans、datatrans、HuffmanCode、MinHeap等主要内容。

HuffmanNode

• E data用来存储权值
• HuffmanNode<T, E>* leftChild, * rightChild, *parent每一个结点包括左右孩子结点和父亲节点，初始均为NULL
• HuffmanNode(E elem, HuffmanNode<T, E>* pr, HuffmanNode<T, E>* left, HuffmanNode<T, E>* right){}构造函数
  • data=elem
  • parent=pr
  • leftchild=left
  • rightchild=right
• codetrans
  • 将编码文件转换为原文本文件
  • ifstream path1编码文件路径
  • ifstream path2编码信息文件路径
  • ofstream path3 转换的原文件路径
  • string s(1, ch)采用读取字符构造字符串并进行匹配方法
• datatrans
  • 将原文件转换为0、1编码的编码文件
  • ifstream path1源文件路径
  • ifstream path2编码信息文件路径
  • ofstream path3 编码文件路径
  • string s(1, ch)采用读取字符构造字符串并进行匹配方法
• HuffmanCode
  • HuffmanNode<int, int>* t 当前头结点
  • int w[]权值数组
  • string code编码信息
  • codemessage << char(i) << " " << code << " "将字符及其编码写入编码信息文件
  • 递归调用
    • 左孩子存在
      • newcode=code+‘0’
      • HuffmanCode(L, w, newcode)
    • 右孩子存在
      • newcode=code+‘1’
      • HuffmanCode(R, w, newcode);
• MinHeap
  • bool Insert(const Item& x)向堆中加入元素
  • bool RemoveMin(Item& x)每次取出堆顶元素
  • void siftUp(int start)从start到0上滑调整成为最小堆
• HuffmanTree(E w[], int n)
  • MinHeap<T, HuffmanNode<T, E> > hp 使用最小堆存放森林的结点
  • HuffmanNode<T, E>* parent, * first, * second, * NodeList，temp 用来生成森林
  • w数组都中每一个字符对应Node都看成一颗树
  • 掉用最小堆函数，每次从森林中取出权值最小的
  • 调用mergeTree进行树的合并
• bool Incode_File_Heap()
  • 读取文本文件并创建权值数组W[]
  • 构造HuffmanTree
  • 调用HuffmanCode生成Huffman编码
• HuffmanTree
  • HuffmanTree(E w[], int n)构造函数
    • E w[]结点权值数组
    • int n结点的个数
  • HuffmanNode<T, E>* getRoot()获取根节点
  • void output(HuffmanNode<T, E>* t, string str, ostream& out)在控制台上输出这棵树
  • void mergeTree(HuffmanNode<T, E>* ht1, HuffmanNode<T, E>* ht2,HuffmanNode<T, E>*& parent)两颗子树合并
  • HuffmanNode<T, E>* root根节点