C++实现哈夫曼树简单创建与遍历的方法

本文以实例形式讲述了C++实现哈夫曼树简单创建与遍历的方法,比较经典的C++算法。

本例实现的功能为:给定n个带权的节点,如何构造一棵n个带有给定权值的叶节点的二叉树,使其带全路径长度WPL最小。

据此构造出最优树算法如下:

哈夫曼算法:

1. 将n个权值分别为w1,w2,w3,....wn-1,wn的节点按权值递增排序,将每个权值作为一棵二叉树。构成n棵二叉树森林F={T1,T2,T3,T4,...Tn},其中每个二叉树都只有一个权值,其左右字数为空

2. 在森林F中选取根节点权值最小二叉树,作为左右字数构成一棵新的二叉树,并使得新的二叉树的根节点为
其左右字数权值之和,其中叶子都是最初的树

3. 在森林F中删除这两棵树,同时将新得到的二叉树代替这两个树加入到森林F中,因此森林中二叉树的个数比以前少一颗

4. 对新的森林重复2和3,知道森林中只有一棵树位置,这棵树就是哈夫曼树.

#include <iostream>
using namespace std;
#define LEAFNUM 10        //叶子节点数,也就是权值树
#define HUFNUM 2*LEAFNUM
#define MAXWEIGHT 999.9
//*********存储结构***********
class HufTree;
//***** Node**********
class NODE
{
private:
 char Data;          //节点的数据域
 double Weight;   //节点的权值域
 int Lchild,Rchild,Parent;   //节点的左孩子右孩子及双亲域
public:
 NODE()            //构造函数
 {
 Data = '\0';
 Weight = 0;
 Lchild = -1;
 Rchild = -1;
 Parent = -1;        //给节点的数据初始化
 }
 int Re_L(){return Lchild;}
 int Re_R(){return Rchild;}
 char Re_Data(){return Data;}
 double Re_Weight(){return Weight;}
 friend class HufTree;     //声明友元
};//Node

//********HufTree类**********
class HufTree
{
private:
 int NodeNum;
 NODE HufArry[HUFNUM];
public:
 HufTree(){NodeNum = 0;}
 void SetHuf(int,double,char);   //设置权值与数据域
 void CreatHuf();          //创建哈夫曼树
 void SelectMin(int,int&,int&);   //查找哈夫曼树种两个权值最小的树
 void Find_Root_and_Print();       //查找树根节点位置
 void PrintHuf(int);          //遍历哈夫曼树
};//huftree

void HufTree::SetHuf(int i,double wei,char ch)
{
 HufArry[i].Data = ch;
 HufArry[i].Weight = wei;
}
void HufTree::CreatHuf()
{
 cout<<"每次查询两个最小树的位置:"<<endl;
 for(int i = LEAFNUM; i < HUFNUM - 1; i++)
 {
 int p1 = 0;
 int p2 = 0;
 SelectMin(i,p1,p2);           //找出当前树种权值最小的两颗树
 cout<<p1<<"   < - >    "<<p2<<endl;
 HufArry[p1].Parent = i;   //设置两颗最小树的双亲
 HufArry[p2].Parent = i;
 HufArry[i].Lchild = p1;   //设置这棵3节点的树的根的权值以及孩子
 HufArry[i].Rchild = p2;
 HufArry[i].Weight = HufArry[p1].Weight + HufArry[p2].Weight;
 }
 cout<<"************************"<<endl;
}
void HufTree::SelectMin(int i,int &p1,int &p2)
{
 int least1 = MAXWEIGHT;
 int least2 = MAXWEIGHT;
 for(int j = 0; j < i; j++)
 {
 if(HufArry[j].Parent == -1)
 {

  if(HufArry[j].Weight < least1)
  {
  least2 = least1;
  least1 = HufArry[j].Weight;
  p2 = p1;
  p1 = j;
  }
  else
  {
  if(HufArry[j].Weight < least2)
  {
   least2 = HufArry[j].Weight;
   p2 = j;
  }
  }
 }
 }
}
void HufTree::Find_Root_and_Print()
{
 int root;
 for(int i = 0; i < HUFNUM - 1; i++)
 {
 if(HufArry[i].Parent == -1)
 {
  root = i;
  break;
 }
 }
 PrintHuf(root);
}
void HufTree::PrintHuf(int position)
{
 if(NodeNum == LEAFNUM)
 {

 return;
 }
 else
 {
 if(HufArry[position].Data != '\0') //如果是叶子节点
 {
  cout<<"权值:"<<HufArry[position].Weight<<"<-> 数据:"<<HufArry[position].Data<<" 此节点为叶子"<<endl;
  NodeNum = NodeNum + 1;
 }
 else
 {
  cout<<"权值:"<<HufArry[position].Weight<<" 此节点无数据域,不是叶子"<<endl;
  PrintHuf(HufArry[position].Lchild);
  PrintHuf(HufArry[position].Rchild);
 }
 }

}
int main()
{
 HufTree Tree;
 cout<<"请输入"<<LEAFNUM<<"对(权值,数据):"<<endl;
 double wei;
 char ch;
 for(int i = 0; i < LEAFNUM; i++)
 {
 cin>>wei;
 cin>>ch;
 Tree.SetHuf(i,wei,ch);
 }
 Tree.CreatHuf();     //创建哈夫曼树
 Tree.Find_Root_and_Print();           //遍历哈夫曼树
 return 0;
}

测试结果:

1 a
2 b
5 c
7 d
4 e
13 f
3 g
6 h
11 i
8 l
(0)

相关推荐

  • C++实现二叉树遍历序列的求解方法

    本文详细讲述了C++实现二叉树遍历序列的求解方法,对于数据结构与算法的学习有着很好的参考借鉴价值.具体分析如下: 一.由遍历序列构造二叉树 如上图所示为一个二叉树,可知它的遍历序列分别为: 先序遍历:ABDECFG 中序遍历:DBEAFCG 后序遍历:DEBFGCA 我们需要知道的是,由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树:由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树:但是如果只知道先序序列和后序序列,则无法唯一确定一棵二叉树. 二.已知二叉树的先序序列和中序序列,求后序

  • C++非递归队列实现二叉树的广度优先遍历

    本文实例讲述了C++非递归队列实现二叉树的广度优先遍历.分享给大家供大家参考.具体如下: 广度优先非递归二叉树遍历(或者说层次遍历): void widthFirstTraverse(TNode* root) { queue<TNode*> q; // 队列 q.enqueue(root); TNode* p; while(q.hasElement()) { p = q.dequeue(); // 队首元素出队列 visit(p); // 访问p结点 if(p->left) q.enqu

  • c++二叉树的几种遍历算法

    1. 前序/中序/后序遍历(递归实现) 复制代码 代码如下: // 前序遍历void BT_PreOrder(BiTreePtr pNode){ if (!pNode)  return;    visit(pNode);   BT_PreOrder(pNode->left); BT_PreOrder(pNode->right);   }// 中序遍历void BT_PreOrder(BiTreePtr pNode){  if (!pNode)  return;     BT_PreOrder(

  • C++递归算法实例代码

    递归算法,总结起来具有以下几个特点: 特点1  它有一个基本部分,即直接满足条件,输出     特点2  它有一个递归部分,即 通过改变基数(即n),来逐步使得n满足基本部分的条件,从而输出     特点3  在实现的过程中,它采用了分治法的思想:        即将整体分割成部分,并总是从最小的部分(基本部分)开始入手(输出),其背后的原理在于 当整体递归到部分时,会保留整体的信息,部分满足条件输出的结果会被回溯给整体使用,从而使得整体输出结果.     特点4  每一步操作,整体都会将部分当

  • VC++实现模拟汉诺塔效果

    先上效果图 再附上源代码: 汉诺塔: 复制代码 代码如下: #include "stdio.h" #include "math.h" int arrA[15], arrB[15], arrC[15];   // 分别为A.B.C int length; int lenA, lenB, lenC; char plate[32]; // Make void makeplate(int n) {     int i;     if (n == length + 1)   

  • C++实现二叉树非递归遍历方法实例总结

    一般来说,二叉树的遍历是C++程序员在面试中经常考察的,其实前中后三种顺序的遍历都大同小异,自己模拟两个栈用笔画画是不难写出代码的.现举一个非递归遍历的方法如下,供大家参考. 具体代码如下: class Solution { public: vector<int> preorderTraversal(TreeNode *root) { vector<int> out; stack<TreeNode*> s; s.push(root); while(!s.empty()

  • C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

    本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法.分享给大家供大家参考,具体如下: /*求二叉树叶子节点个数 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <stack> using std::cout; using std::cin; using std::endl; using std::stack; /*二叉树结点定义*/

  • C++基于先序、中序遍历结果重建二叉树的方法

    本文实例讲述了C++基于先序.中序遍历结果重建二叉树的方法.分享给大家供大家参考,具体如下: 题目: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字.例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回. 实现代码: #include <iostream> #include <vector> #include <stack> using

  • C++实现汉诺塔算法经典实例

    本文所述为汉诺塔算法的C++代码的经典实现方法. 汉诺塔问题描述:3个柱为a.b.c,圆盘最初在a柱,借助b柱移到c柱.需要你指定圆盘数. 具体实现代码如下: #include <iostream> using namespace std; int times = 0; //全局变量,搬动次数 //第n个圆盘从x柱搬到z柱 void move(int n, char x, char z) { cout << "第" << ++times <&l

  • 二叉树遍历 非递归 C++实现代码

    二叉树的非递归遍历 二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的.对于二叉树,有前序.中序以及后序三种遍历方法.因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁.而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现.在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点. 一.前序遍历 前序遍历按照"根结点-左孩子-右孩子"的顺序进行访问. 1.递归实现 复制代码 代码

  • C++基于递归算法解决汉诺塔问题与树的遍历功能示例

    本文实例讲述了C++基于递归算法解决汉诺塔问题与树的遍历功能.分享给大家供大家参考,具体如下: 递归是把问题转化为规模缩小的同类问题,然后迭代调用函数(或过程)求得问题的解.递归函数就是直接或间接调用自身的函数. 递归两要素:递归关系和递归边界(终止条件),递归关系确定了迭代的层次结构,需要深入了解并分解问题:终止条件保证了程序的有穷性. 递归的应用有很多,常见的包括:阶乘运算.斐波那契数列.汉诺塔.数的遍历,还有大名鼎鼎的快排等等.理论上,递归问题都可以由多层循环来实现.递归的每次调用都会消耗

  • C++ 实现汉诺塔的实例详解

    C++ 实现汉诺塔的实例详解 前言: 有A,B,C三塔,N个盘(从小到大编号为1-N)起初都在A塔,现要将N个盘全部移动到C塔(按照河内塔规则),求最少移动次数以及每次的移动详细情况. 要求: 需要采用递归方法和消除尾递归两种方法编写. 盘数N由用户从标准输入读入,以一个整数表示,然后请调用两个方法按照下面例子所述分别在屏幕中输出结果(正常情况下一个输入数据会显示同样的输出结果2次). 实现代码: #include<iostream> using namespace std; void mov

随机推荐