哈夫曼树(一) C语言详解 - 数据结构与算法 - 编程入门网
哈夫曼树(一) C语言详解
哈夫曼树的介绍
Huffman Tree，中文名是哈夫曼树或霍夫曼树，它是最优二叉树。
定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。这个定义里面涉及到了几个陌生的概念，下面就是一颗哈夫曼树，我们来看图解答。
(01) 路径和路径长度
定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
例子：100和80的路径长度是1，50和30的路径长度是2，20和10的路径长度是3。
(02) 结点的权及带权路径长度
定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
例子：节点20的路径长度是3，它的带权路径长度= 路径长度 * 权 = 3 * 20 = 60。
(03) 树的带权路径长度
定义：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
例子：示例中，树的WPL= 1*100 + 2*80 + 3*20 + 3*10 = 100 + 160 + 60 + 30 = 350。
比较下面两棵树
上面的两棵树都是以{10, 20, 50, 100}为叶子节点的树。
左边的树WPL=2*10 + 2*20 + 2*50 + 2*100 = 360
右边的树WPL=350
左边的树WPL & 右边的树的WPL。你也可以计算除上面两种示例之外的情况，但实际上右边的树就是{10,20,50,100}对应的哈夫曼树。至此，应该堆哈夫曼树的概念有了一定的了解了，下面看看如何去构造一棵哈夫曼树。
哈夫曼树的图文解析
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、&、wn，哈夫曼树的构造规则为：
1. 将w1、w2、&，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
2. 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3. 从森林中删除选取的两棵树，并将新树加入森林；
4. 重复(02)、(03)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
以{5,6,7,8,15}为例，来构造一棵哈夫曼树。哈夫曼树(三)之 Java详解 - 如果天空不死 - 博客园
随笔 - 278
评论 - 1023
前面分别通过和实现了哈夫曼树，本章给出哈夫曼树的java版本。
转载请注明出处：
更多内容：
哈夫曼树的介绍
Huffman Tree，中文名是哈夫曼树或霍夫曼树，它是最优二叉树。
定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。
这个定义里面涉及到了几个陌生的概念，下面就是一颗哈夫曼树，我们来看图解答。
(01) 路径和路径长度
定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
例子：100和80的路径长度是1，50和30的路径长度是2，20和10的路径长度是3。
(02) 结点的权及带权路径长度
定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
例子：节点20的路径长度是3，它的带权路径长度= 路径长度 * 权 = 3 * 20 = 60。
(03) 树的带权路径长度
定义：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
例子：示例中，树的WPL= 1*100 + 2*80 + 3*20 + 3*10 = 100 + 160 + 60 + 30 = 350。
比较下面两棵树
上面的两棵树都是以{10, 20, 50, 100}为叶子节点的树。
左边的树WPL=2*10 + 2*20 + 2*50 + 2*100 = 360
右边的树WPL=350
左边的树WPL & 右边的树的WPL。你也可以计算除上面两种示例之外的情况，但实际上右边的树就是{10,20,50,100}对应的哈夫曼树。至此，应该堆哈夫曼树的概念有了一定的了解了，下面看看如何去构造一棵哈夫曼树。
哈夫曼树的图文解析
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、&、wn，哈夫曼树的构造规则为：
1. 将w1、w2、&，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
2. 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3. 从森林中删除选取的两棵树，并将新树加入森林；
4. 重复(02)、(03)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
以{5,6,7,8,15}为例，来构造一棵哈夫曼树。
第1步：创建森林，森林包括5棵树，这5棵树的权值分别是5,6,7,8,15。
第2步：在森林中，选择根节点权值最小的两棵树(5和6)来进行合并，将它们作为一颗新树的左右孩子(谁左谁右无关紧要，这里，我们选择较小的作为左孩子)，并且新树的权值是左右孩子的权值之和。即，新树的权值是11。 然后，将"树5"和"树6"从森林中删除，并将新的树(树11)添加到森林中。
第3步：在森林中，选择根节点权值最小的两棵树(7和8)来进行合并。得到的新树的权值是15。
然后，将"树7"和"树8"从森林中删除，并将新的树(树15)添加到森林中。
第4步：在森林中，选择根节点权值最小的两棵树(11和15)来进行合并。得到的新树的权值是26。
然后，将"树11"和"树15"从森林中删除，并将新的树(树26)添加到森林中。
第5步：在森林中，选择根节点权值最小的两棵树(15和26)来进行合并。得到的新树的权值是41。 然后，将"树15"和"树26"从森林中删除，并将新的树(树41)添加到森林中。
此时，森林中只有一棵树(树41)。这棵树就是我们需要的哈夫曼树！
哈夫曼树的基本操作
哈夫曼树的重点是如何构造哈夫曼树。本文构造哈夫曼时，用到了以前介绍过的"(二叉堆)最小堆"。下面对哈夫曼树进行讲解。
1. 基本定义
public class HuffmanNode implements Comparable, Cloneable {
protected HuffmanN
protected HuffmanN
protected HuffmanN
protected HuffmanNode(int key, HuffmanNode left, HuffmanNode right, HuffmanNode parent) {
this.key =
this.left =
this.right =
this.parent =
public Object clone() {
Object obj=
obj = (HuffmanNode)super.clone();//Object 中的clone()识别出你要复制的是哪一个对象。
} catch(CloneNotSupportedException e) {
System.out.println(e.toString());
public int compareTo(Object obj) {
return this.key - ((HuffmanNode)obj).
HuffmanNode是哈夫曼树的节点类。
public class Huffman {
private HuffmanNode mR
Huffman是哈夫曼树对应的类，它包含了哈夫曼树的根节点和哈夫曼树的相关操作。
2. 构造哈夫曼树
* 创建Huffman树
* @param 权值数组
public Huffman(int a[]) {
HuffmanNode parent =
// 建立数组a对应的最小堆
heap = new MinHeap(a);
for(int i=0; i&a.length-1; i++) {
HuffmanNode left = heap.dumpFromMinimum();
// 最小节点是左孩子
HuffmanNode right = heap.dumpFromMinimum(); // 其次才是右孩子
// 新建parent节点，左右孩子分别是left/right；
// parent的大小是左右孩子之和
parent = new HuffmanNode(left.key+right.key, left, right, null);
left.parent =
right.parent =
// 将parent节点数据拷贝到"最小堆"中
heap.insert(parent);
// 销毁最小堆
heap.destroy();
首先创建最小堆，然后进入for循环。
每次循环时：
(01) 首先，将最小堆中的最小节点拷贝一份并赋值给left，然后重塑最小堆(将最小节点和后面的节点交换位置，接着将"交换位置后的最小节点"之前的全部元素重新构造成最小堆)；
(02) 接着，再将最小堆中的最小节点拷贝一份并将其赋值right，然后再次重塑最小堆；
(03) 然后，新建节点parent，并将它作为left和right的父节点；
(04) 接着，将parent的数据复制给最小堆中的指定节点。
在中已经介绍过堆，这里就不再对堆的代码进行说明了。若有疑问，直接参考后文的源码。其它的相关代码，也Please RTFSC(Read The Fucking Source Code)！
哈夫曼树的完整源码
哈夫曼树的源码共包括4个文件。
阅读(...) 评论()&&&&&&&&&&&&&&&&&&
posts - 34,comments - 2,trackbacks - 0
积分与排名
阅读排行榜
评论排行榜
哈夫曼树定义为：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。1、那么什么是权值？什么是路径长度？什么是带权路径长度呢？权值：哈夫曼树的权值是自己定义的，他的物理意义表示数据出现的次数、频率。可以用树的每个结点数据域data存放一个特定的数表示它的值。
路径长度：在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。& 树中所有叶子节点的带权路径长度之和，WPL=sigma(w*l)2、哈夫曼树的构造过程。（结合图例）假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
　　(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
　　(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
　　(3)从森林中删除选取的两棵树，并将新树加入森林；
　　(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树3、哈夫曼树的应用：哈夫曼编码（前缀编码）哈夫曼编码
在数据通信中，通常需要把要传送的文字转换为由二进制字符0和1组成的二进制串，这个过程被称之为编码(Encoding)。例如，假设要传送的电文为DCBBADD，电文中只有A、B、C、D四种字符，若这四个字符采用表(a)所示的编码方案，则电文的代码为11，代码总长度为14。若采用表(b) 所示的编码方案，则电文的代码为0，代码总长度为13。
字符集的不同编码方案
哈夫曼树可用于构造总长度最短的编码方案。具体构造方法如下：设需要编码的字符集为{d1,d2,…,dn}，各个字符在电文中出现的次数或频率集合为{w1,w2,…,wn}。以d1,d2,…,dn作为叶子结点，以w1,w2,…,wn作为相应叶子结点的权值来构造一棵哈夫曼树。规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码就是哈夫曼编码(Huffman Encoding)。
在建立不等长编码中，必须使任何一个字符的编码都不是另一个编码的前缀，这样才能保证译码的唯一性。例如，若字符A的编码是00，字符B的编码是001，那么字符A的编码就成了字符B的编码的后缀。这样，对于代码串001001，在译码时就无法判定是将前两位码00译成字符A还是将前三位码001译成B。这样的编码被称之为具有二义性的编码，二义性编码是不唯一的。而在哈夫曼树中，每个字符结点都是叶子结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。
下图就是电文DCBBADD的哈夫曼树：
4、哈夫曼树的实现
由哈夫曼树的构造算法可知，用一个数组存放原来的n个叶子结点和构造过程中临时生成的结点，数组的大小为2n-1。所以，哈夫曼树类HuffmanTree中有两个成员字段：data数组用于存放结点，leafNum表示哈夫曼树叶子结点的数目。结点有四个域，一个域weight，用于存放该结点的权值；一个域lChild，用于存放该结点的左孩子结点在数组中的序号；一个域rChild，用于存放该结点的右孩子结点在数组中的序号；一个域parent，用于判定该结点是否已加入哈夫曼树中。
哈夫曼树结点的结构为：| 数据 | weight | lChild | rChild | parent |
&&&& public class Node&&& {&&&&&&& //存储的数据，为一个字符&&&&&&& p //结点权值&&&&&&& private int lC //左孩子结点&&&&&&& private int rC //右孩子结点&&&&&&& //父结点&&&&&&& //结点权值属性&&&&&&& public double Weight&&&&&&& {&&&&&&&&&&& get&&&&&&&&&&& {&&&&&&&&&&&&&&&&&&&&&&&&&& }&&&&&&&&&&& set&&&&&&&&&&& {&&&&&&&&&&&&&&& weight =&&&&&&&&&&& }&&&&&&& }&&&&&&& //左孩子结点属性&&&&&&& public int LChild&&&&&&& {&&&&&&&&&&& get&&&&&&&&&&& {&&&&&&&&&&&&&&& return lC&&&&&&&&&&& }&&&&&&&&&&& set&&&&&&&&&&& {&&&&&&&&&&&&&&& lChild =&&&&&&&&&&& }&&&&&&& }&&&&&&& //右孩子结点属性&&&&&&& public int RChild&&&&&&& {&&&&&&&&&&& get&&&&&&&&&&& {&&&&&&&&&&&&&&& return rC&&&&&&&&&&& }&&&&&&&&&&& set&&&&&&&&&&& {&&&&&&&&&&&&&&& rChild =&&&&&&&&&&& }&&&&&&& }&&&&&&& //父结点属性&&&&&&& public int Parent&&&&&&& {&&&&&&&&&&& get&&&&&&&&&&& {&&&&&&&&&&&&&&&&&&&&&&&&&& }&&&&&&&&&&& set&&&&&&&&&&& {&&&&&&&&&&&&&&& parent =&&&&&&&&&&& }&&&&&&& }&&&&&&& //构造器&&&&&&& public Node()&&&&&&& {&&&&&&&&&&& weight = 0;&&&&&&&&&&& lChild = -1;&&&&&&&&&&& rChild = -1;&&&&&&&&&&& parent = -1;&&&&&&& }&&&&&&& //构造器&&&&&&& public Node(double weitht)&&&&&&& {&&&&&&&&&&& this.weight =&&&&&&&&&&& lChild = -1;&&&&&&&&&&& rChild = -1;&&&&&&&&&&& parent = -1;&&&&&&& }
&&&&&&& //构造器&&&&&&& public Node(int w, int lc, int rc, int p)&&&&&&& {&&&&&&&&&&& weight =&&&&&&&&&&& lChild =&&&&&&&&&&& rChild =&&&&&&&&&&& parent =&&&&&&& }&&& }
&&& public class HuffmanTree&&& {&&&&&&& private Node[] //结点数组&&&&&&& private int leafN //叶子结点数目&&&&&&& //索引器&&&&&&& public Node this[int index]&&&&&&& {&&&&&&&&&&& get&&&&&&&&&&& {&&&&&&&&&&&&&&& return data[index];&&&&&&&&&&& }&&&&&&&&&&& set&&&&&&&&&&& {&&&&&&&&&&&&&&& data[index] =&&&&&&&&&&& }&&&&&&& }&&&&&&& //叶子结点数目属性&&&&&&& public int LeafNum&&&&&&& {&&&&&&&&&&& get&&&&&&&&&&& {&&&&&&&&&&&&&&& return leafN&&&&&&&&&&& }&&&&&&&&&&& set&&&&&&&&&&& {&&&&&&&&&&&&&&& leafNum =&&&&&&&&&&& }&&&&&&& }&&&&&&& //构造器&&&&&&& public HuffmanTree(int n)&&&&&&& {&&&&&&&&&&& data = new Node[2 * n - 1];&&&&&&&&&&& leafNum =&&&&&&& }&&&&&&& //创建哈夫曼树&&&&&&& public void Create(Node[] datain)&&&&&&& {&&&&&&&&&&& double minL, minR;&&&&&&&&&&& minL = minR = double.MaxV&&&&&&&&&&& int lchild,&&&&&&&&&&& lchild = rchild = -1;
&&&&&&&&&&& int length = data.L&&&&&&&&&&& //初始化哈夫曼树&&&&&&&&&&& for (int i = 0; i & i++)&&&&&&&&&&&&&&& data[i] = new Node();&&&&&&&&&&& for (int i = 0; i & datain.L i++)&&&&&&&&&&&&&&& data[i] = datain[i];
&&&&&&&&&&& //处理n个叶子结点，建立哈夫曼树&&&&&&&&&&& for (int i = leafN i & i++)&&&&&&&&&&& {&&&&&&&&&&&&&&& //在全部结点中找权值最小的两个结点&&&&&&&&&&&&&&& for (int j = 0; j & j++)&&&&&&&&&&&&&&& {&&&&&&&&&&&&&&&&&&& if (data[j].Parent == -1)&&&&&&&&&&&&&&&&&&& {&&&&&&&&&&&&&&&&&&&&&&& if (data[j].Weight & minL)&&&&&&&&&&&&&&&&&&&&&&& {&&&&&&&&&&&&&&&&&&&&&&&&&&& minR = minL;&&&&&&&&&&&&&&&&&&&&&&&&&&& minL = data[j].W&&&&&&&&&&&&&&&&&&&&&&&&&&& rchild =&&&&&&&&&&&&&&&&&&&&&&&&&&& lchild =&&&&&&&&&&&&&&&&&&&&&&& }&&&&&&&&&&&&&&&&&&&&&&& else if (data[j].Weight & minR)&&&&&&&&&&&&&&&&&&&&&&& {&&&&&&&&&&&&&&&&&&&&&&&&&&& minR = data[j].W&&&&&&&&&&&&&&&&&&&&&&&&&&& rchild =&&&&&&&&&&&&&&&&&&&&&&& }&&&&&&&&&&&&&&&&&&& }&&&&&&&&&&&&&&& }&&&&&&&&&&&&&&& data[lchild].Parent = data[rchild].Parent =&&&&&&&&&&&&&&& data[i].Weight = minL + minR;&&&&&&&&&&&&&&& data[i].LChild =&&&&&&&&&&&&&&& data[i].RChild =&&&&&&&&&&& }&&&&&&& }&&& }
&&& class Program&&& {&&&&&&& static void Main(string[] args)&&&&&&& {&&&&&&&&&&& HuffmanTree tree = new HuffmanTree(5);&&&&&&&&&&& Node[] nodes = new Node[] { new Node(1), new Node(2), new Node(2.5d), new Node(3), new Node(2.6d) };&&&&&&&&&&& tree.Create(nodes);
&&&&&&&&&&& Console.ReadLine();&&&&&&& }&&& }
/////////////////////////////节选自网络上的资料、
阅读(2132)
&re: 哈夫曼树
到底什么是权值？都看不懂&&&&&&> 问题详情
由权值为9，2，5，7的四个叶子构造一棵哈夫曼树，该树的带权路径长度为（13)。A．23B．37C．44D．46
悬赏：0&答案豆
提问人：匿名网友
发布时间：
由权值为9，2，5，7的四个叶子构造一棵哈夫曼树，该树的带权路径长度为(13)。A．23B．37C．44D．46请帮忙给出正确答案和分析，谢谢！
权威推荐： & &
为您推荐的考试题库
您可能感兴趣的试题
1在一棵完全二叉树中，其根的序号为1，(14)可判定序号为p和q的两个节点是否在同一层。A．[logp]=[log2q)B．log2p=log2qC．[log2p]+1=[log2q)D．[log2p]=[log2q)+12若一棵哈夫曼(Huffman)树共有9个顶点，则其叶子节点的个数为()。A．4B．5C．6D．73在一棵度为3的树中，若有2个度为3的节点，有1个度为2的节点，则有(16)个度为0的节点。A．4B．5C．6D．74设节点x和y是二叉树中任意的两个节点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是(17)。A．x是y的左兄弟B．x是y的右兄弟C．x是y的祖先D．x是y的后裔
我有更好的答案
请先输入下方的验证码查看最佳答案
图形验证：
验证码提交中……
找答案会员
享三项特权
找答案会员
享三项特权
找答案会员
享三项特权
选择支付方式：
支付宝付款
郑重提醒：支付后，系统自动为您完成注册
请使用微信扫码支付(元)
支付后，系统自动为您完成注册
遇到问题请联系在线客服QQ：
恭喜你被选中为
扫一扫-免费查看答案！
请您不要关闭此页面,支付完成后点击支付完成按钮
遇到问题请联系在线客服QQ：
恭喜您！升级VIP会员成功
提示：请截图保存您的账号信息，以方便日后登录使用。
常用邮箱：
用于找回密码
确认密码：树结构_百度百科
清除历史记录关闭
声明：百科词条人人可编辑，词条创建和修改均免费，绝不存在官方及代理商付费代编，请勿上当受骗。
本词条缺少名片图，补充相关内容使词条更完整，还能快速升级，赶紧来吧！
树是一种重要的非线性数据结构，直观地看，它是（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。
树是一种重要的非线性数据结构，直观地看，它是（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译如下时，可用树表示源源程序如下的语法结构。又如在中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。
树结构定义
一棵树（tree）是由n（n&0）个元素组成的，其中：
（1）每个元素称为（node）；
（2）有一个特定的结点，称为或根（root）；
（3）除根结点外，其余结点被分成m（m&=0）个互不相交的有限集合，而每个又都是一棵树（称为原树的子树）
树结构概念介绍
树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。
树结构深度
树的深度——组成该树各结点的最大层次，如上图，其深度为4；
树结构层次
的层次为1，其他结点的层次等于它的的层次数加1.
树结构路径
对于一棵子树中的任意两个不同的结点，如果从一个结点出发，按层次自上而下沿着一个个树枝能到达另一结点，称它们之间存在着一条路径。可用路径所经过的结点序列表示路径，路径的长度等于路径上的结点个数减1.
树结构森林
指若干棵互不相交的树的集合
树结构树的表示
树结构父亲数组
设T是一棵树，表示T的一种最简单的方法是用一个存储每个结点，数组的下标就是结点的位置指针，每个结点中有一个指向各自的父亲结点的数组下标的域，这样可使Parent操作非常方便。类型定义如下：
TPosition= {结点的位置类型为整型}
NodeType=Record
Label:LabelT {该结点的标号}
Parent:TP {该结点的父亲的数组下标，对于根结点该域为0}
TreeType=Record
NodeCount: {树的结点的总数目}
Node:Array [1..MaxNodeCount] of NodeT{存储树的结点}
由于树中每个结点的父亲是唯一的，所以上述的父亲数组表示法可以唯一地表示任何一棵树。在这种表示法下，寻找一个结点的父结点只需要O(1)时间。在树中可以从一个结点出发找出一条向上延伸到达其祖先的道路，即从一个结点到其父亲，再到其祖父等等。求这样的道路所需的时间正比于道路上结点的个数。在树的父亲数组表示法中，对于涉及查询儿子和兄弟信息的树操作，可能要遍历整个数组。为了节省查询时间，可以规定指示儿子的数组下标值大于父亲的数组下标值，而指示兄弟结点的数组下标值随着兄弟的从左到右是递增的。
树结构儿子链表
树的另一种常用的表示方法就是儿子表示法。这种表示法用一个来存储树的所有结点信息，称为结点表。对每个结点建立一个儿子表。儿子表中只存储儿子结点的地址信息，可以是指针，数组下标甚至内存地址。由于每个结点的儿子数目不定，因此儿子表常用来实现，因此这种表示法称为儿子链表表示法。这种实现法与图的表示法类似。下图是一个儿子链表表示法的示意图。
图3 树的儿子链表实现
图3中儿子链表结构表示的树如图4所示，树中各结点存放于一个数组实现的表中，数组下标作为各结点的指针。每一个（即每一个结点）含有一个儿子表，在图3中儿子表是用单链表来实现的，当然也可以用其他表的实现方式来实现儿子表，比如说游标方式(静态链表)。但由于每个结点的儿子数目不确定，所以一般不用数组来实现儿子表，但可以用数组来实现结点表，就如图3所示。在图3中可以看到，位于结点表第一个位置的结点(未必是)有两个儿子结点，从左到右的两个儿子结点分别位于结点表的第2和第3个位置。因为图3中的结点表用数组实现，所以结点的标号就是结点在结点表中的数组下标。如图4所示。
图4 图3中儿子所表示的树
为了指明树的根结点的位置，我们可以用一个变量Root记录根结点在结点表中的位置。有了根结点的位置，就可以利用儿子表依次找到树中所有的结点。
儿子链表表示的树的类型定义如下：
{======================
NodeListType是一个元素为NodeType类型的线性表，其位置类型为TPosition，
NodeListType定义了结点表的类型；
ChildrenListType是一个元素为TPosition类型的线性表， ChildrenListType定义了儿子表的类型
=======================}
TPosition=....
ChildrenListType=...
NodeType=Record {结点的类型}
:LabelT {结点的标号}
Children:ChildrenListT{结点的儿子表}
NodeListType=...
TreeType=record
root:TP {记录树根在结点表中的位置}
Node:NodeListT {结点表}
其中NodeListType是一个元素为NodeType类型的线性表，其位置类型为TPosition，NodeListType定义了结点表的类型；ChildrenListType是一个元素为TPosition类型的， ChildrenListType定义了儿子表的类型。以上类型定义并不考虑表的具体实现方式，如果假设结点表和儿子表都用实现，则类型定义可以具体实现如下：
{儿子实现树的类型定义的一个具体实例，结点表和儿子表都用单链表实现}
TPosition=^NodeT {结点表的位置类型}
ChildrenNodeType=record {儿子表的结点项的类型}
child:TP {指向儿子结点的位置指针}
next:^ChildrenNodeT {指向下一个儿子表项的指针}
NodeType=Record {结点的类型定义为}
:LabelT {结点的标号}
Children:^ChildrenNodeT{指向儿子表的指针}
TreeType=^NodeT {树的类型定义为结点指针类型}
注意以上的定义只是一种具体情况，实际应用中结点表和儿子表可能用数组、等任何一种表的实现方式实现。
树结构左儿子右兄弟
树的左儿子右兄弟表示法又称为二叉树表示法或表示法。每个结点除了data域外，还含有两个域，分别指向该结点的最左儿子和右邻兄弟。这种表示法常用二叉链表实现，因此又称为二叉链表表示法。但是实际应用中常用()来代替，请参见表的游标实现。
若用指针实现，其类型定义为：
TPosition=^NodeT
NodeType=record
Label:LabelT
Leftmost_Child,Right_Sibling:TP
TreeType=TP
若用实现，其类型定义为:
TPosition=
NodeType=record
Label:LabelT
Leftmost_Child,Right_Sibling:TP
CellspaceType=array [1..MaxNodeCount] of NodeT
TreeType=TP
Cellspace:CellspaceT
Tree:TreeT
此时树类型TreeType是整数类型，它指示树根在cellspace中的。例如图5(a)中树的左儿子右兄弟表示法的指针和游标实现分别如图5(b)和(c)所示。
图5 树的左儿子右兄弟表示法
用树的左儿子右兄弟表示法可以直接实现树的大部分操作，只有在对树结点作Parent操作时需树。如果要反复执行Parent操作，可在结点记录中再开辟一个指向父结点的指针域，也可以利用最右儿子单元中的Right_Sibling作为指向父结点的指针(否则这里总是空指针)。当执行Parent(v)时，可以先通过Right_Sibling逐步找出结点v的最右兄弟，再通过最右兄弟的Right_Sibling(父亲指针)找到父结点。这个结点就是结点v的父亲。在这样的表示法下，求一个结点的父亲所需要的时间正比于该结点右边的兄弟个数。不过，这时每个记录中需要多用一位(bit)空间，用以标明该记录中的right_sibling是指向右邻兄弟还是指向父亲。
考虑到对于现在的计算机，内存已经不是很重要的限制因素了。我们下面就采取增加一个parent域的方案，以改进左儿子右兄弟表示法中Parent操作的效率。因此重新定义树的类型如下：
若用指针实现，其类型定义为：
TPosition=^NodeT
NodeType=record
Label:LabelT
Parent,Leftmost_Child,Right_Sibling:TP {增加一个Parent域}
TreeType=TP
Tree:TreeT
若用游标实现，其类型定义为:
TPosition=
NodeType=record
Label:LabelT
Parent,Leftmost_Child,Right_Sibling:TP {增加一个Parent域}
CellspaceType=array [1..MaxNodeCount] of NodeT
TreeType=TP
Cellspace:CellspaceT
Tree:TreeT
树结构树的遍历
树的是树的一种重要的运算。所谓遍历是指对树中所有结点的系统的访问，即依次对树中每个结点访问一次且仅访问一次。树的3种最重要的遍历方式分别称为、和。以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的前序列表，中序列表和后序列表。相应的结点次序分别称为结点的前序、中序和后序。
树的这3种遍历方式可地定义如下：
§ 如果T是一棵空树，那么对T进行前序遍历、中序遍历和后序遍历都是空操作，得到的列表为空表。
§ 如果T是一棵单结点树，那么对T进行前序遍历、和都只访问这个结点。这个结点本身就是要得到的相应列表。
§ 否则，设T如图6所示，它以n为树根，树根的子树从左到右依次为T1,T2,..,Tk，那么有：
§ 对T进行是先访问树根n,然后依次前序遍历T1,T2,..,Tk。
§ 对T进行中序是先中序遍历T1，然后访问树根n，接着依次对T2,T2,..,Tk进行中序遍历。
§ 对T进行后序遍历是先依次对T1,T2,..,Tk进行后序遍历，最后访问树根n。
树结构树的应用
树结构二叉排序树
排序是一种十分重要的运算。所谓排序就是把一堆杂乱无章的元素按照某种次序排列起来，形成一个有序的序列。是利用二叉树的结构特点来实现对元素排序的。
一、二叉排序树的定义
二叉排序树或者是空树，或者是具有如下性质的二叉树：
1、左子树上所有结点的数据值均小于的数据值；
2、右子树上所有结点的数据值均大于或等于根结点的数据值；
3、左子树、右子树本身又各是一棵二叉排序树。
由此可见，二叉排序树是一种特殊结构的二叉树。（18（10（3，15（12，15）），21（20，21（，37））））就是一棵。
二、二叉排序树的构造
二叉排序树的构造过程实质上就是排序的过程，它是二叉排序树作媒介，将一个任意的数据序列变成一个有序序列。二叉排序树的构造一般是采用陆续插入结点的办法逐步构成的。具体构造的思路是：
1、以待排序的数据的第一个数据构成；
2、对以后的各个数据，逐个插入结点，而且规定：在插入过程的每一步，原有树结点位置不再变动，只是将新数据的结点作为一个插入到合适的位置，使树中任何结点的数据与其左、右子树结点数据之间的关系仍然符合对二叉排序树的要求。
树结构Huffman树
一、的含义：哈夫曼树是一种带权路径长度最短的树。
所谓路径长度就是某个端结点到树的的距离，等于该端结点的祖先数，或该结点所在层数减1，用lk表示。二叉树中每个端结点对应的一个称为该结点的权，用Wk表示。我们定义各端结点的权Wk与相应的路径程度lk乘积的代数和为该二叉树的带权路径长度，用表示，即：
可以证明，哈夫曼树是最优二叉树。如给定{5，4，7，2，3}，可以生成很多棵二叉树，其中的（A（B（7，5），C（4，D（3，2））））是哈夫曼树。
二、哈夫曼树的构造
（1）根据给定的n个权值{W1，W2，…，Wn}构成n棵二叉树的森林：F{T1，T2，…，Tn}。其中每棵二叉树Ti只有一个带权为Wi的，其左右子树为空。
（2）在F中选取两棵结点的权值最小的树作为左右子树构成一棵新的二叉树，且置新的二叉树的根结点的为其左右子树上根结点的权值之和。
（3）在F中删除这两棵树，同时，将新得到的二叉树加入F中。
（4）重复（2）、（3），直到F只含一棵树为止。最后的这棵树便是。
2、算法描述
为了上述算法，选用数组型的作为存储结构，其类型设计如下：
Type tnode=RECORD
weight：real；
Lc，Rc：integer；
tree=ARRAY[1..2*n-1]
node=RECORD
weight：real；
adr：integer；
A=ARRAY[1..n]
下面是在这个存储结构上实现的构造的算法：
Procedure Huffmantree（VAR W：[1..n]OFVAR TR:tree）；
FOR i:=1 TO n DO{实现第(1)步}
TR[i].weight:=W[i];{将放在树叶中}
TR[i].Lc：=0；
TR[i].Rc：=0；
AT[i].weight:=TR[i].{用AT存放当前森林的根}
AT[i].adr:=i;
num:=n;{森林中结点个数}
K:=num+1;{形成的新结点在TR数组中的位置}
WHILE (num&=2) DO {重复实现第(2)、(3)步}
SORTING(AT,num);{按根值大小对森林中的树进行升序排列}
TR[k].weight:=AT[1].weight+AT[2].
{选择两棵结点最小的树构造新二叉树}
TR[k].Lc:=AT[1]. {左子树：权值最小的树}
TR[k].Rc:=AT[2]. {右子树：权值次小的树}
AT[1].weight:=TR[k]. {新树赋予第一}
AT[1].adr:=k; {新树结点标号}
AT[2].weight:=AT[num].{原最后树赋予第二}
AT[2].adr:=AT[num]. {跟进结点标号}
num:=num-1; {删除原最后树}
k:=k+1; {增加结点标号}
三、应用：
利用构造的用于通信的，称为哈夫曼编码。
例如，有一段电文‘CAST TAT A SA’，统计电文中字母的频度，f('C')=1,f('S')=2,f('T')=3,f(' ')=3,f('A')=4，可用其频度{1，2，3，3，4}为生成Huffman树，并在每个叶子上注明对应的字符。树中从根到每个叶子都有一条路径，若对路径上的各分支进行约定，指向树根的分支用“0”码表示，指向右子树根的分支用“1”码表示，再取每条路径上的“0”或“1”的序列作为与各个叶子对应的字符的编码，这就是。
树结构二叉树
是一类非常重要的，它可以地定义如下：
二叉树T是有限个结点的集合，它或者是，或者由一个u以及分别称为左子树和右子树的两棵互不相交的二叉树u(1)和u(2)组成。若用n,n1和n2分别表示T，u(1)和u(2)的结点数，则有n=1+n1+n2 。u(1)和u(2)有时分别称为T的第一和第二子树。
因此，二叉树的根可以有空的左子树或空的右子树，或者左、右子树均为空。
二叉树具有以下的重要性质：
高度为h≥0的二叉树至少有h+1个结点； 高度不超过h(≥0)的二叉树至多有2h+1-1个结点； 含有n≥1个结点的二叉树的高度至多为n-1； 含有n≥1个结点的二叉树的高度至少为 logn ，因此其高度为Ω(logn)。 详见词条。
清除历史记录关闭