锐客网

  1. 首页 > it技术 > >

数据结构|哈夫曼树的实现


BinaryTree.h

#pragma once #pragma once #include using namespace std; template struct BTNode { BTNode() { lchild = rchild = NULL; } BTNode(const T& x){ element = x; lchild = rchild = NULL; } BTNode(const T& x, BTNode* l, BTNode* r) { element = x; lchild = l; rchild = r; } T element; BTNode* lchild, *rchild; }; template class BinaryTree { public: BinaryTree() { root = NULL; } ~BinaryTree(); bool IsEmpty()const; void Clear(); //移去所有结点，使其成为空树 bool Root(T& x)const; //若二叉树非空，则x为根的值，并返回true，否则返回false void MakeTree(const T& x, BinaryTree& left, BinaryTree& right); //构造一棵二叉树，根的值为x，以left和right为左右子树 void BreakTree(T& x, BinaryTree& left, BinaryTree& right); //拆分二叉树为三部分，x为根的值，left和right分别为左右子树 //---------------------(华丽分割线)---------------------- void PreOrder(void (*Visit)(T& x)); //使用函数Visit访问结点，先序遍历二叉树 void InOrder(void (*Visit)(T& x)); //中序遍历二叉树 void PostOrder(void (*Visit)(T& x)); //后序遍历二叉树 //---------------------(华丽分割线)---------------------- //分割线内的函数面向用户，主要提供一个用户与类内递归循环的一个接口 protected: BTNode* root; //指向根结点的指针 private: void Clear(BTNode* &t); //---------------------(华丽分割线)---------------------- void PreOrder(void (*Visit)(T& x),BTNode*t); void InOrder(void (*Visit)(T& x), BTNode*t); void PostOrder(void (*Visit)(T& x), BTNode*t); //---------------------(华丽分割线)---------------------- //分割线内的函数才是主要实现递归遍历算法的函数 }; template BinaryTree::~BinaryTree() { Clear(); }; template bool BinaryTree::IsEmpty()const { return (root == NULL) ? true : false; }; template void BinaryTree::Clear() { Clear(root); }; template void BinaryTree::Clear(BTNode*&t=root) { if (p!= NULL) { Clear(p->lchild); Clear(p->rchild); delete p; } }; template bool BinaryTree::Root(T& x)const { if (root == NULL)return false; else { x = root.element; return true; } return false; }; template void BinaryTree::MakeTree(const T& x, BinaryTree& left, BinaryTree& right) { if (root || &left == &right)return; //若root非空，说明root已是某二叉树树根 root = new BTNode(x,left.root,right.root); left.root = right.root = NULL; //left和right已与新树结合，故将其指针设为空 }; template void BinaryTree::BreakTree(T& x, BinaryTree& left, BinaryTree& right) { if (!root || &left == &right || left.root || right.root)return; //如果实参left和right的root非空则说明用户传过来用于获取左右子树的的BTNode指针是某个树的结点 x == root->element; left.root = root->lchild; right.root = root->rchild; delete root; root = NULL; }; //先序遍历，面向用户 template void BinaryTree::PreOrder(void(*Visit)(T& x)) { PreOrder(Visit, root); }; //先序遍历，真正实现的函数 template void BinaryTree::PreOrder(void(*Visit)(T& x), BTNode* t) { if (t) { Visit(t->element); PreOrder(Visit, t->lchild); PreOrder(Visit, t->rchild); } }; template void Visit(T& x) { cout << x << " "; }; //中序遍历，面向用户 template void BinaryTree::InOrder(void(*Visit)(T& x)) { InOrder(Visit, root); }; //中序遍历，真正实现的函数 template void BinaryTree::InOrder(void(*Visit)(T& x),BTNode*t) { if (t) { InOrder(Visit, t->lchild); Visit(t->element); InOrder(Visit, t->rchild); } }; //后序遍历，面向用户 template void BinaryTree::PostOrder(void(*Visit)(T& x)) { InOrder(Visit, root); }; //后序遍历，真正实现的函数 template void BinaryTree::PostOrder(void(*Visit)(T& x),BTNode*t) { if (t) { PostOrder(Visit, t->lchild); PostOrder(Visit, t->rchild); Visit(t->element); } };

PrioQueue.h
#pragma once /* 优先权队列是多个元素的集合，每个元素都有一个优先权。 优先权队列的特点是：每次从队列中取出具有最高优先权的元素 ADT PrioQueue{ Data: n个元素的最小堆 Operation: Create(); //建立一个空队列 Destroy(); //撤销一个队列 IsEmpty(); //空则返回true，非空则false IsFull(); //满则true，非满则false Append(x); //元素值为x的新元素入队 Serve(x); //将该队列中具有最小优先权的元素值返回给x，并从优先权队列中删除该元素 } */ template class PrioQueue { public: PrioQueue(int mSize = 20) { maxSize = mSize; q = new T[maxSize]; } ~PrioQueue() { delete[]q; } bool IsEmpty() const{ return n == 0; } bool IsFull() { return n == maxSize; } void Append(const T&x); void Serve(T& x); private: void AdjustDown(int r, int j); void AdjustUp(int j); T*q; int n, maxSize; }; template void PrioQueue::AdjustDown(int r, int j){ int child = 2*r + 1; //child定位到r的左子位置 T temp = q[r]; while (child <= j) { if ((child < j) && (q[child] > q[child + 1]))child++; //找到左右子中最小的那一个 if (temp <= q[child])break; //如果temp比左右子最小的都小，说明符合向下调整的规则 q[(child - 1) / 2] == q[child]; //将该子值赋给其父结点 child = 2 * child + 1; //继续向下（跳到该节点的子节点） } q[(child - 1) / 2] = temp; //temp的位置 }template void PrioQueue::AdjustUp(int j){//j为新插入元素的位置+1 int i = j; T temp = q[i]; while (i > 0 && temp < q[(i - 1) / 2]) { q[i] = q[(i - 1) / 2]; //父子交换 i = (i - 1) / 2; //跳到该节点的父位置 } q[i] = temp; //i即为temp最后合理的位置 } //因为插入新元素之前堆中元素都已经满足最小堆的条件 //故只需调整新元素影响到的节点即可 template void PrioQueue::Append(const T&x) { if (IsFull())throw Overflow; q[n++] = x; //将新元素插入完全二叉树的最后位置 AdjustUp(n - 1); //新元素插入位置即为n-1，故用AdjustUp调整0~n-1; } template void PrioQueue::Serve(T& x) { if (IsEmpty())throw Underflow; x = q[0]; //返回具有最低优先权的元素（即堆顶元素） q[0] = q[--n]; //然后将堆底元素放到堆顶 AdjustDown(0, n - 1); //向下调整 }


HfmTree.h 【数据结构|哈夫曼树的实现】
#pragma once #include"BinaryTree.h" #include"PrioQueue.h" template class HfmTree :public BinaryTree { public : HfmTreeCreateHfmTree(T w[], int n); operator T()const { return weight; } T getW() { return weight; } void putW(const T& x) { weight = x; }//设置权重 setNull() { root = NULL; } private: T weight; }; template HfmTree HfmTree::CreateHfmTree(T w[], int n) { PrioQueue>pq(n); //pq是一个优先权队列，他的元素是哈夫曼树对象 HfmTreex, y, z, zero; //----------------------第一个for循环-------------- for (int i = 0; i < n; i++) { z.MakeTree(w[i], x, y); z.putW(w[i]); //构造一个数中只有一个结点的哈夫曼树对象 pq.Append(z); //将哈夫曼树对象放进优先权队列 z.setNull(); //将z置为空数 } //将w数组中的每一个元素当作一个哈夫曼树的权值构造一 //个只有一个结点的哈夫曼树，pq //压进优先权队列pq //----------------------第一个for循环-------------- //----------------------第二个for循环-------------- for (int i = 1; i < n; i++) { pq.Serve(x); //取出最小值 pq.Serve(y); //取出次最小值 z.MakeTree(x.getW() + y.getW(), x, y); //分别将该次取出的最小值和次最小值当作左、右子 //构造一个新的哈夫曼树对象 z.putW(x.getW() + y.getW()); pq.Append(z); z.setNull(); } //对优先权队列pq中的元素（即哈夫曼树对象）进行合并n-1次 //则最后剩一个完整的即构造完成的哈夫曼树 //----------------------第二个for循环-------------- pq.Serve(z); return z; }



    推荐阅读


    上一篇：2017年12月3日天气有点阴

    下一篇：Wiki|线段覆盖2（动态规划）