问题二：哈夫曼树的构造 10分 第一步：排序 2 4 5 9
第二步：挑出2个最小的 2 4 为叶子构造出
6
2 4
第三步：判断 6 不大于 5或9（剩余叶子中最小的2个）=》 同方向生长，得出：
11
6 5
2 4
第四步：继续生长
20
11 9
6 5
2 4
权值为 23+43+52+91=37
也可以20+11+6=37
例题：6、13、18、30、7、16
排序 6 7 13 16 18 30
13
6 7
26 26大于16或18 =》分支生长
13 13
6 7
26 34
13 13 16 18
6 7
此时最小的2个数为 26 30 得出
56 34
26 30 16 18
13 13
6 7
最后得出 90
56 34
26 30 16 18
13 13
6 7 权值 219
90+56+26+13+34 or 64+74+133+302+162+182
问题三：怎样构造合适的哈夫曼树？ 5分 来自百度百科：哈夫曼树构造方法：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
简单的说，就是选择两个权值最小的节点，构造一棵树，树的根权值是两个权值最小的节点之和，将新的权值节点放回序列，继续按照上述方法构造，直到只有一棵树为止，这样的树其WPL最小。
问题四：哈夫曼树怎样构造编码？ 先编造哈夫曼树，哈夫曼树构造规则：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止
构造完成之后，从这个树根结点开始，默认左子树为0，右子树为1，直到叶子结点为止，叶子结点的编码就是需要的编码。
举例
知字符A B C D E F的权值为8 12 5 20 4 11
哈夫曼树就是：
60
/ \
23 37
/ \ / \
F(11) B(12) 17 D(20)
/ \
A(8) 9
/ \
E(4) C(5)
编码就是 A：100， B：01， C：1011， D： 11， E：1010 ，F：00
问题五：哈夫曼树的构建过程 30分 哈夫曼树:
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
哈夫曼树的构造：
假设给定的权值如下：3,5,7,8,10,15；
首先取 中最小的两个数：3+5=8，再删除 中3和5的值，把8放入原 ,
原 变成:7,8,8,10,15；
8
/ \
3 5
再从7,8,8,10,15中再取2个最小的数构成一个树
15
/ \
8 7
/ \
3 5
再从8,10,15,15中再取2个最小的数构成一个树:
18
/ \
8 10
再从15,15,18中取两个最小数:15,15,构成树:
30
/ \
15 15
/ \
8 7
/ \
3 5
最后把18,30构成树(此时 中已经没元素了，就形成了哈夫曼树):
48
/ \
30 18
/ \ / \
15 15 8 10
/ \
8 7
/ \
3 5
希望你能看懂！！
问题六：哈夫曼树的创建 哈夫曼树不一定是唯一的，选出最小和次小之后哪个放左边都行的，哈弗曼编码唯一只是说得到的码是唯一，但是可以有许多种码，只是它能够唯一地编码和解码。所以，上面两个图应该都是正确的。如果你习惯按照左小右大的规则来构造的话，那只能选择第二幅图了。
问题七：数据结构，图中哈夫曼树是如何构建的？ 怎么样才可以并列生长？如第三层的37和41 构造哈夫曼树，从节点中选择权最小的两个节点。两个节点求和后，它们的和被放入节点选择的节点数队中。下次从节点队中再选当前权值最小的两个节点。如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。就是37,51的情况。不知道对不对。
问题八：3 4 5 6 8 9怎么构造哈夫曼树，怎么我总是构造不对，是这样的么 对的，不过通常习惯性会从左到右，从下到上来构造// binary_treecpp : 定义控制台应用程序的入口点。
//last modified by Hujuly, may 13, 2008
#include "stdafxh"
#include
#define increasement 5
using namespace std;
//--------树结点类-------------
template
class TreeNode{//定义树结点
TreeNode left;//该结点的左孩子
Elem element;//该结点数据项
TreeNode right;//该结点的右孩子
public:
TreeNode(){
left=right=NULL;
}
TreeNode(Elem& item){
left=right=NULL;
element=item;
}
~TreeNode(){}
void setVal(const Elem item){element=item;}//给该结点数据项赋值
Elem getVal(){return element;}//获取该结点的数据
void setLeft(TreeNode leftNode){left=leftNode;}//设置左孩子
TreeNode getLeftChild(){return left;}//获取左孩子
void setRight(TreeNode rightNode){right=rightNode;}//设置右孩子
TreeNode getRightChild(){return right;}//获取右孩子
bool isLeaf(){return ( left==NULL && right==NULL );}//判断是否为叶子
};
//---------树类----------------
template
class binTree{
private:
TreeNode root;
Elem RefValue;//用途ok结束标记
void clearHlp(TreeNode current);//清空以current为根的树
void creatHlp(TreeNode current);//创建一棵以current为根的树
void InOrder(TreeNode current);//中序遍历
void PreOrder(TreeNode current);//前序遍历
void PostOrder(TreeNode current);//后序遍历
bool findHlp(TreeNode current,Elem data);//查找以current为根的树中是否有data
void changeRLHlp(TreeNode current);//交换以current为根的左右子树
void printHlp(TreeNode current,int pos);//打印树
public:
binTree(Elem e){ RefValue = e; root = new TreeNode; root->setVal(e);} //构造函数构造一棵空树
~binTree(){clearHlp(root);} //析构函数
void creatBinTree(); //创建一棵树
void clearTree();//清空树
void printTree();//打印树
bool find(Elem d);//查找d是否在树中
TreeNode parent(TreeNode current,TreeNode start);//寻找双亲结点
void InOrderRoot(){ InOrder(root);}//中序
void PreOrderRoot(){PreOrder(root);}//先序
void PostOrderRoot(){PostOrder(root);}//后序
void changeRL();//交换左右子树
};
要创建二叉树，可以简单的创建一个CSimpleBinaryTree 对象并初始化。
#define MAXELEMS 100
CSimpleBinaryTree btree;
btreeInitialise(MAXELEMS,sizeof(CSomeObject));或btreeInitialise(MAXELEMS,sizeof(CSomeObject), someCompareFunction);或btreeInitialise(MAXELEMS,sizeof(CSomeObject), someCompareFunction, nGrowTrigger, nGrowByValue, nShrinkTrigger, nShrinkByValue);"someCompareFunction"是一个有两个指针参数的函数的指针，这个函数根据第一个参数是否小于，等于，大于第二个参数而分别返回负数，0和正数。CSimpleBinaryTree 提供了一个通用的全局比较函数，它可以比较两个长整型的指针。
添加元素
要向这棵树添加一个子项,可以简单的调用AddItem()并传一个指针给它，用来存放添加后的对象。在内部，相关数据通过指针被拷贝到动态分贝的内存上。CSomeObject sObj;
CSomeObject psObj1=&sObj;
CSomeObject psObj2;
int nResult;
nResult=btreeAddItem(&sObj);或nResult=btreeAddItem(psObj1);或nResult=btreeAddItem(psObj1, psObj2);AddItem() 函数返回两个值。第一个是整型结果。如果子项被成功添加了，子项的索引值会被成功返回，如果没有成功添加，就会返回错误代码:
· DUPLICATE_FOUND
· OUT_OF_MEMORY
· TREE_IS_FULL
第二个返回值是可选择的第二个参数值。如果 *** 作成功,那末指向新创建对象的指针被返回了, 如果 *** 作不成功，该指针被赋值为空。
DUPLICATE_FOUND仅当公共变量m_bAllowDuplicates被设为FALSE时才返回，否则，这个树将允许复制数据（缺省情况）。
如果复制 *** 作不被允许，那末这棵树将会在每次被搜索时都会添加子元素以便判断子元素是否存在。这一点就降低了添加子项的速度，但是也潜在的节省了内存分配的数量。
删除元素
要删除一个子项，可以简单的调用RemoveItem() 函数，并设置上我们要删除的子项的索引值。
BOOL bResult;
bResult=RemoveItem(nIndex);如果该项被成功地从树中删除了,函数返回TRUE, 否则返回FALSE;
当一个子项从树中删除时，其上面所有的元素对应的子项左移一个位置并“子项总数”减一。
这一点，说明效率并不高,潜在的,函数有可能不得不遍历整棵树无论如何从二叉树添加和删除元素是天生的比其他的存储/修补算法要慢，这是因为二叉遍历网络树要求元素有序的事实。
遍历这棵树
要判断一个元素是否在这棵树中存在,可以简单的调用FindItem() 函数int nIndex;
nIndex = btreeFindItem(psObj);或CSomeObject pFoundObject;
nIndex = btreeFindItem(psObj,pFoundObject);FindItem() 返回两个值如果子项存在，第一个值就是子项的索引值，如果不存在，赋值为ITEM_NOT_PRESENT value第二个返回值是可选择的第二个参数值。如果子项被发现了，pFoundObject 将指向它在树中的对象,如果子项没有被发现，pFoundObject 赋为空;
在CSimpleBinaryTree 中有两个搜索算法线性搜索和对半搜索线性搜索只在树种子项数目小于指定值的时候才使用 (缺省为10),从这个点以后的各项，将使用对半搜索这样做的原因是线性查找不要求元素进行排序并且它的运算规则相对要简单的多因此对于小数目项来说，线性查找是理想的
如果在树中允许复制(m_bAllowDuplicates=TRUE) ，那末平衡(所有子项排序) *** 作只有当在“被要求”的时候进行，而不是像m_bAllowDuplicates=FALSE and并且所有子项在每次添加新的子项时都会进行排序相反地,排序可能会在调用FindItem() 函数时进行当用FindItem()查找一个子项时，使用的是对半查找算法,即使该项存在，查找也可能失败这样的原因是这个树并不是完全平衡的这这种情况下，算法查找子项时，就会失败,同时也说明该树并非完全平衡的,通过排序使得该树平衡，然后再递归的调用FindItem()函数一旦该树平衡了，一个内部标记将会被设置，并且这个标记在添加一个新元素时不会被设置,因而避免了任何一个递归的循环因此后来的FindItem()调用就会避免重复的调用对于程序员来说，没有必要作些特殊的 *** 作以上说的只是这个类中众多内部处理中一个而已
这样在允许复制 *** 作的时候，每添加一个子项就不必再调用SortItems() 了，从而效率得到很大的提高此处使用的是C 语言库中的qsort()函数来实现排序算法的
重设树的大小
通过ReSize()来设置二叉树的子项数目，以满足添加和删除的需要btreeReSize(300);通过调用ReSize()可以设置树中可以容纳的最大子项数 然而当树中已经存在200个元素并且其最大容纳子项数为250， 如果作如下调用btreeReSize(100),那末树中开始的100元素 将会传送到新的指针数组上面，而后面的120个元素将会从树中被移除，其占用的内存也会被释放掉
通过设置公共成员变量m_bAutoResize = TRUE (缺省),该树可以通过成员变量中用于控制增减和减少的参数自动的设置元素数目的大小
增加和消减
当公共成员变量m_bAutoResize被设为TRUE时，增加和消减参数控制树的元素数目每项 *** 作会有两个变量一个触发器，一个增加/消减值所有的值用占当前树中元素数目的百分比来表示
触发器的值可以确定增长或消减 *** 作的发生增加/消减 的百分比确定了该树增加或消减的程度
比如，如果在树中我有80 元素，被允许的最大子项数为100，m_bAutoResize 设为TRUE同样的增长触发器被设为90 (90%) ，消减触发器被设为10 (10%)，增长和消减的值都设为50 (50%)
如果我向树中添加11个元素,该树将会有91%的填充率，同时增长触发器也会被激活那末此时该树可容纳的元素数目就会增加50%,ie 在内部会调用ReSize(150)同样的，如果我删除了80 个元素中的71个，该树将只有9%的填充率，消减触发器会被激活，从而导致树中可容纳元素树消减50%,ie 在内部会调用ReSize(50)
重设大小的 *** 作代价昂贵，因此应该尽可能的避免上面的例子中给出了增长/消减触发器的缺省值和增长/消减的对应值。
公共方法概述
AddItem()为新元素分配一个空间,把指针添加到二叉树的元素数组中,从而添加向二叉树中添加一个新元素如果失败,返回负数RemoveItem()从二叉树中删除某项 该项被删除厚,此项上面的所有指针左移一个位置,子项的数目相应地更新,如果nItem在有效的索引范围内,返回TRUEFindItem()决定使用哪一种查找算法查找元素,如果数组大小小于对半查找的开始位置,线性查找将被执行,而不是对半查找ReSize()根据nNewSize对二叉树进行增长和消减如果nNewSize等于当前的数目或者没有更多的内存可供分配了的话返回FALSE,否则返回 TRUE Initialise()在一个对象被创建后,初始化函数必须被调用设置内部成员值并为二叉树数组分配空间GetSearchMethodThreshold()获取当前查找算法的临界值GetTotalItems()取得当前树中存放的子项的数目GetTreeSize()取得树中子项数目的最大值GetShrinkTriggerValue()在消减触发器激活时，返回当前的值SetShrinkTriggerValue()设置消减触发器的值当该树使用的空间与自身的空间百分比小于nPercentageUsed,当且仅当AutoResizing有效时，该树会自动的重新设置子项数目缺省的消减触发器值为10%GetShrinkByPercentage()返回当前消减百分比SetShrinkByPercentage()当AutoResize 有效时，设置消减百分比的值当AutoResize有效并且重设大小被触发时，该树将会释放nPercentDecrease相关项GetGrowTriggerValue()在增长触发器激活时，返回当前的值SetGrowTriggerValue()设置增长触发器的值当该树已经分配了使用的百分比时,当且仅当AutoResizing有效时，该树会自动的重新设置子项数目缺省的增长触发器值为90%GetGrowByPercentage()返回当前增长百分比SetGrowByPercentage()当AutoResize 有效时，设置增长百分比的值当AutoResize有效并且重设大小被触发时，该树将会给nPercentIncrease相关项分配空间FreeMemory()释放所有的堆空间，包括二叉树数组以及其中包括的子项用户不必调用这个函数，除非他想立刻释放内存并愿意删除二叉树 最好的办法是，使用缺省的析构函数自动的调用这个函数SetSearchMethodThreshold()设置对半查找的临界值，以区分何时使用对半查找和线性查找。查找方法会根据这个临界值进行切换缺省值为10GetItemPtr()返回一个空类型指针，用于指向在二叉树子项数组中nItem索引对应的子项的指针如果索引值超出了有效值，返回空GenericLongCompare()提供给用户的全局比较函数用来比较两个long型数据（a,b）如果相等，返回0,如果a<b,返回负数如果 a>b 返回正数DoTest()CSimpleBinarySearch类中提供了测试函数在使用这个函数前，必须先定义BINARY_TREE_EXAMPLE 这是我学习二叉树时用过的例子，运行没有问题，你自己按照上面弄下吧。由于图贴不了，实在抱歉。
学生会组织机构管理问题的设计方案
1． 问题描述
学生会组织机构管理问题中的数据元素具有如下形式：
firstchild data rightbrother
firstchild: 指向第一个孩子结点
rightbrother: 指向右兄弟结点
data: 学生会成员信息，其自然情况包括：职位，姓名，性别，年级，班级。
2． 功能需求
要求完成以下功能：
(1) 插入：将某学生插入到某部门；
(2) 删除：将某学生在某个部门删除；
(3) 修改：修改某个部门的组成情况；
(4) 查询：查询学生会的组织机构状况；
(5) 输出：按部门输出学生会全体成员。
3． 实现要点
(1) 为方便对学生会组织机构的各项 *** 作，学生会的组织机构用孩子兄弟表示法进行存储。为该存储结构设计一个模板类，设计成员函数完成上述功能。
(2) 为树的孩子兄弟表示法设计一个结点类，将结点的数据部分作为私有成员隐藏在类的内部，并提供查找右兄弟、查找第一个孩子等 *** 作。
(3) 简单起见，学生会成员的自然情况包括职位、姓名、性别、年级、班级，为其设计一个学生类，将各自然情况作为私有成员隐藏在类的内部，并提供相应成员函数实现对数据进行访问。
(4) 在主函数中提供 *** 作菜单，先对该组织机构进行初始化，即根据实验数据建立一棵树，再根据用户的输入完成相应功能并输出结果。
4． 类定义
为树的孩子兄弟表示法建立结点类(Node)，其类定义如下：
template <class T>
class Node
{
public:
Node(T data) { _data = data; _firstChild = NULL; _brother = NULL;}//有参构造函数
~Node() {} //无参析构函数
Node<T> getFirstChild() { return _firstChild; } //访问结点第一个孩子
Node<T> getBrother() { return _brother; } //访问结点的右兄弟
T getData() { return _data; } //取结点数据域的值
void setFirstChild(Node<T> node) { _firstChild = node; } //为结点的第一个孩子赋值
void setBrother(Node<T> node) { _brother = node; } //为结点的右兄弟赋值
void setData(T data) { _data = data; } //为结点的数据域赋值
private:
T _data; //结点的数据域
Node<T> _firstChild; //结点的头孩子指针
Node<T> _brother; //结点的右兄弟指针
};
在结点类中，提供了如下成员函数：
（1） 函数的声明：Node(T data)；
完成的功能：初始化一个新结点
（2） 函数的声明：Node<T> getFirstChild()；
完成的功能：返回指向结点的第一个孩子结点的指针
（3） 函数的声明：Node<T> getBrother()；
完成的功能：返回指向结点的右兄弟结点的指针；
（4） 函数的声明：T getData()；
完成的功能：返回结点数据域的值
（5） 函数的声明：void setFirstChild(Node<T> node)；
完成的功能：为结点的第一个孩子赋值
（6） 函数的声明：void setBrother(Node<T> node)；
完成的功能：为结点的右兄弟赋值
（7） 函数的声明：void setData(T data)；
完成的功能：为结点的数据域赋值
为数据域的学生会成员建立成员类（Member）,其类定义如下：
class Member
{
public:
Member(string position, string name, string sex, string grade, int classes); //有参构造函数
void print(void); //打印数据
string getPosition() const { return _position; }//获取学生职务
string getName() const { return _name; } //获取学生姓名
string getSex() const { return _sex; } //获取学生性别
string getGrade() const { return _grade; }//获取学生所在年级
int getClasses() const { return _classes; }//获取学生所在班级
// *** 作符重载用来判断结点中数据是否相等，若相等则返回1否则返回0
int operator==(Member& stu) const
{
return _name == stugetName()
&& _sex == stugetSex()
&& _grade == stugetGrade()
&& _classes == stugetClasses()
&& _position == stugetPosition();
}
private: //学生会成员属性
string _position; //职位
string _name; //姓名
string _sex; //性别
string _grade; //年级
int _classes; //班级
};
在成员类中，提供了如下成员函数：
（1） 函数的声明：Member(string position, string name, string sex, string grade, int classes);
完成的功能：初始化一个新的数据成员
（2） 函数的声明：void print(void);
完成的功能：打印出数据成员信息
（3） 函数的声明：string getPosition() const；
完成的功能：返回学生会成员的职务
（4） 函数的功能：string getName() const；
完成的功能：返回学生会成员的姓名
（5） 函数的声明：string getSex() const；
完成的功能：返回学生会成员的性别
（6） 函数的声明：string getGrade() const；
完成的功能：返回学生会成员的年级
（7） 函数的声明：int getClasses() const；
完成的功能：返回学生会成员的班级
（8） 函数的声明：int operator==(Member& stu) const；
完成的功能：比较数据域的值（即学生会成员的所有属性）是否相等，若相等返回1，否则返回0
为学生会组织机构的管理建立树类（Tree）,其类的定义如下：
template <class T>
class Tree
{
Node<T> _root; //指向根结点的头指针
T _tempDate; //结点数据域中的数据
public:
Tree(T data) {_root = new Node<T>(data);} //有参构造函数，初始化一棵树//的根结点
~Tree(void) {Release(_root);} //析构函数，释放树中各结点的存储空间
void Insert(T oldData, T newData); //插入函数
void DeleteNode(T date); //删除树中某结点及其孩子
void Update(T oldData, T newData); //修改函数
Node<T> FindNode(std::string position,Function function); //查询函数
void LeverOrder(Function function); //层序遍历树
private:
void Release(Node<T> node); //析构函数调用
Node<T> FindNode(T data); //插入函数调用
void InsertBrother(Node<T> node,T data); //插入兄弟结点
void InsertChild(Node<T> node, T data); //插入第一个孩子结点
};
在树类中，提供了如下成员函数：
（1） 函数的声明：Tree(T data)；
完成的功能：初始化一棵树
（2） 函数的声明：~Tree(void)；
完成的功能：释放树的存储空间
（3） 函数的声明：void Insert(T oldData, T newData);
完成的功能：将新结点插入到合适的位置
下面是演示结果：
例如将（文艺部员，刘琳，女，一，3 ）插入到（文艺部长，王一，女，一，5）的孩子结点中：
（5） 函数的声明：void DeleteNode(T date);
完成的功能：释放要删除结点及其孩子结点的存储空间
如下将演示删除的过程：
例如：删除（秘书长，李四，女，一，4）这个结点：
（6） 函数的声明：void Update(T oldData, T newData);
完成的功能：修改结点的数据信息
例如要将（学习部长，刘一，女，二，4）修改为
（学习部长，周瑜，男，二，5）
（7） 函数的声明：Node<T> FindNode(std::string position,Function function);
完成的功能：查询树中的结点信息，并输出符合条件的结点的数据信息
例如查询副主席的所有成员显示如下：
（8） 函数的声明：void LeverOrder(Function function);
完成的功能：层序遍历一棵树，输出树中所有结点的数据信息
未进行任何 *** 作前的学生会所有成员如下：
插入后显示树中的所有成员如下：
删除后显示树中的所有成员：
修改后显示如下：
1、我们先是定义这样一个Node结构。
2、可以用Typedef重命名，C++中可以不写。
3、然后我们定义一个数据元素，名为data。
4、此时，我们递归调用这个结构，形成链表。
5、此时，我们就能为这棵树定义一个节点和一棵树类型。
6、不过，这个ElemType是有提前定义的，否则会无效命名。
1、找到一片红杉林做基地。找到一棵树，制作一个井字。2、紧接着下方5格，再制作一个井字作为地基。接着用白杨楼梯。
3、接着用桃花木台阶铺满。接着为制作顶部做准备。
4、接着继续增加胡桃楼梯，使得房屋面积增大，也更加稳固。接着地基下方，用坚固的红杉木搭建。
5、接着屋顶用灰沙楼梯制作。搭建屋顶。接着中间树干去掉，备置一些家具。接着围绕树干制作台阶。树屋就完成了。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）