网站信息员队伍建设方案,最新新闻十条,推荐好用的浏览器,百度推广员工工资怎么样1.树
前言
本文主要介绍的数据结构之树型结构的相关知识#xff0c;树型数据结构是面试官面试的时候非常喜欢考的一种数据结构#xff0c;树形结构的遍历也是大厂笔试非常喜欢设置的考点#xff0c;这些内容都会在本篇文章中进行详细的介绍#xff0c;并且还会介绍一些常…1.树
前言
本文主要介绍的数据结构之树型结构的相关知识树型数据结构是面试官面试的时候非常喜欢考的一种数据结构树形结构的遍历也是大厂笔试非常喜欢设置的考点这些内容都会在本篇文章中进行详细的介绍并且还会介绍一些常用的算法。
一、树的基本概念
层次结构的数据在现实世界中大量存在。例如一个国家有若干省一个省有若干市县一个市县有若干区乡。又如一本书包含若干章一章包含若干节一节包含若干段。例如下图是数组的层次关系这种描述树形数据的形式称为倒置的树形表示法。
线性数据结构一般不适合用来表示层次数据。为了组织层次数据需要对树形数据的结构进行研究。
1.1树的定义
在上图1中我们采用倒置树来描述树状结构。一棵倒置树的顶端是根根有几个分枝称为子树每棵子树再分成几个小分枝小分枝再分成更小的分枝每个分枝也都是树一个结点也是树。由此我们可以给树下一个递归定义。
树Tree是包括n个结点的有限非空集合T其中一个特定的结点r称为根Root其余结点T-{r}划分成m个互不相交的子集T1T2Tm其中每个子集都是树称为树根r的子树。
根据树的定义一个结点的树是仅有根结点的树这时m0这棵树没有子树。
1.2基本术语
图1可以抽象成图2它形象地反映了树的逻辑结构。下面参照图2给出树结构讨论中常用的术语。 树中元素称为结点Node如A、B等。
如果某结点到另一结点之间存在着连线则称此连线为一条边Edge如A,B、B,E等。
如果从某个结点沿着树中的边可到达另一个结点则称这两个结点间存在一条路径Path如结点A到结点J存在路径{A,CC,J}。
如果一个结点有子树则称该结点为子树的双亲Parent子树的根称为该结点的孩子Child如结点A是结点B、C、D的双亲而结点B、C、D是结点A的孩子。具有相同双亲的结点称为兄弟Sibling如结点B、C、D是兄弟。
结点拥有的子树数目称为结点的度Degree如结点A的度为3结点D的度为0结点J的度为0。
度为零的结点称为叶子(Leaf)。
规定根结点的层次为1树中结点的最大层次称为该树的高度(Hight)如图2所表示的树的高度为3。
如果树中结点的各子树是从左至右有次序的则称该树为有序树否则称为无序树。
二、二叉树
树结构和自然界的树一样具有各种各样的形态这样就使我们对树结构的研究比较困难。为此我们首先研究最为常见的二叉树以及二叉树的性质、存储结构和运算然后给出二叉树和一般树之间的转换。
2.1二叉树的定义 二叉树Binary Tree是由有限个结点组成的集合它或者为空集合或者仅含一个根结点或者由一个根结点和两棵互不相交的左、右子树组成。
上述定义表明二叉树有如图3所示的五种基本形态。
必须指出树定义与二叉树定义稍有区别。首先树不能是空树却可以有空二叉树。其次一般树的子树的不分次序而二叉树的子树却分左、右子树即使在仅有一棵子树的情况下也要指明是左子树还是右子树。最后一般树中结点的度(子树数目)可以大于2但二叉树中结点的度均不超过2。
2.2二叉树的性质 若二叉树高为h树的结点总数为2^h-1称此二叉树为满二叉树。
h3那么结点总数7(包含根节点) 【性质1】高度为h的二叉树的结点总数n2^h-1。
这个性质很容易理解
证明对于高度为h的满二叉树其结点总数为
它是高度为h的二叉树结点总数的最大值故。
对于高度为h的二叉树如果第1~h-1层构成满二叉树而第h层的叶子结点严格按从左至右依次排列称此二叉树为完全二叉树如图5(a)所示。 在图5(b)中双亲结点C仅有右孩子G无左孩子故它不是完全二叉树。
【性质2】对于含n(n1)个结点的完全二叉树(区分满二叉树)其高度 h ⌈ l o g 2 ( n 1 ) ⌉ h\lceil log2(n1) \rceil h⌈log2(n1)⌉ 。
eg上述图an6那么 h [ l o g 2 ( 6 1 ) ] l o g 2 ( 8 ) 3 h[log2(61)]log2(8)3 h[log2(61)]log2(8)3
【性质3】对于一棵非空二叉树如果度为0的结点数为度为2的结点数为则
1。 即零度结点数总比2度结点数大1
证 设二叉树的结点数为n度为1的结点数为n1边数为e则 e n − 1 en-1 en−1 e 2 × n 2 n 1 e2×n2n1 e2×n2n1 n n 0 n 1 n 2 nn0n1n2 nn0n1n2
边数等于结点数n-1 等于2倍的度为2的结点数度为1的结点数。
画个树的逻辑结构图就很容易看出来。
于是n0n21。
【性质4】对于含个结点的完全二叉树(区分满二叉树)按从上到下、从左到右的顺序从0到n-1编号如图6所示。对于树中编号为 i 0 i n − 1 i0in-1 i0in−1的结点有
1如果 i 0 i0 i0则该结点为二叉树的根
2如果 2 i 1 n 2_i1n 2i1n则其左孩子为 2 i 1 2_i1 2i1否则不存在左孩子
3结点的双亲为[(i-1)/2]向下取整。(求双亲注意双亲只有一个) 2.3二叉树的ADT ADT BinTree
数据
0个或有限个结点组成的集合。
运算
Create()
创建一棵空二叉树或二叉树。
IsEmpty()
若二叉树为空则返回1否则返回0。
PreOrder()
前序遍历二叉树。
InOrder()
中序遍历二叉树。
PostOrder()
后序遍历二叉树。
Display():
输出二叉树。
三、二叉树的存储表示
3.1二叉树的数组表示 用一维数组来存储二叉树首先将二叉树想象成一棵完全二叉树对于没有左孩子或右孩子的结点用特殊字符或数字替代再依从上至下、从左至右的次序依次将结点值存放到一维数组之中。
【例1】将图7(a)所示的二叉树用一维字符数组表示。
解
首先将图7(a)所示的二叉树想象成一棵完全二叉树如图7(b)所示再用表8-1所示的一维字符型数组存储。
这种表示法的实现程序如下示法的实现程序如下
#include bits/stdc.h
using namespace std;
const int MaxSize 64//为了树的显示效果,结点数不超过63,即二叉树高不超过6
//创建二叉树
void Create(char Node[], int n)
{cout 按完全二叉树输入结点字符,空字符用替代 endl;cin Node;//计算字符数组含字符个数n 0;while (Node[n] ! \0)//当Node[n]不等于结束符时n;
}
//输出二叉树
void Display(char Node[], int n)
{int hight, layer, num; //hight树高,layer树层,num结点编号hight ceil(log(n 1) / log(2));//确定完全二叉树高度//求下限接近整数ceil//自然对数 log//求上限接近整数 floorcout hight endl;num 0;//从结点Node[0]开始输出for (layer 1; layer hight; layer)//输出1层—hight层{ //每层前面空格的输出控制for (int i 1; i pow(2, hight - layer)-1; i)cout ;//每层结点的输出控制for (int j 1; j pow(2, layer - 1); j, num){if (Node[num] ! Node[num] ! \0)cout Node[num];//遇到结点,输出结点else if (Node[num] )cout ;//遇到号,输出空格elsebreak;//遇到结束符,跳出输出//每层结点间空格的输出控制for (int k 1; k pow(2, hight - layer 1) - 1; k)cout ;}cout endl;//输完一层,换行}
}
//主函数
int main()
{int n;//完全二叉树所含结点数char Node[MaxSize];//定义字符型的结点数组Create(Node, n);//创建二叉树结点的一维数组cout 二叉树为 endl;Display(Node, n);//输出二叉树return 0;
}程序运行的结果如图8所示
创建这棵5结点二叉树用了6颗星号替代缺失的左、右孩子这显然是这种表示法的一个缺点。
但当二叉树为完全二叉树时该表示法具有建树简便输出直观的优点。
3.2二叉树的链表表示 用一维数组表示的二叉树不便实现二叉树的一些规定运算。因此二叉树一般采用链表来创建。
链式二叉树结点的逻辑结构如图9所示其中data用来存储结点值*lChild、*rChild分别用来存储左、右孩子的地址。
图9 树节点的逻辑结构 【例2】创建图7(a)所示的链式二叉树。
用链表表示图7(a)其逻辑结构如图10所示其中Λ代表NULL。 具体的创建过程如下
1首先创建第4层结点并用结点指针Kp指向其根结点如图11所示。
图11 2再创建第3层结点并用结点指针Ep指向其根结点如图12所示。
图12 3再创建第2层结点并用结点指针Bp、Cp分别指向其根结点如图13所示。
图13 4最后创建第1层结点并用结点指针Ap指向其根结点如图14所示。
图14 如果用程序来描述上述过程其程序如下
#includeiostream
using namespace std;
//二叉树结点定义
struct Node
{ char data;//数据域Node *lChild,*rChild;//指针域
};
//二叉树定义
struct BinTree
{ Node *root;
};
//创建二叉树
void Create(BinTree T,char x,Node *left,Node *right)
{ Node *NewNode;//新结点NewNodenew Node;//为新结点申请内存NewNode-datax;//为新结点数据域赋值NewNode-lChildleft;//为新结点左指针域赋值NewNode-rChildright;//为新结点右指针域赋值T.rootNewNode;//让新结点成为该子树根结点
}
//主函数
int main()
{ BinTree K,E,B,C,A;Create(K,K,NULL,NULL);//创建结点K的子树Create(E,E,NULL,K.root);//创建结点E的子树Create(B,B,NULL,E.root);//创建结点B的子树Create(C,C,NULL,NULL);//创建结点C的子树Create(A,A,B.root,C.root);//创建结点A的子树return 0;
}上述链式二叉树的创建过程是先创建最底层的叶子结点然后向上逐层创建子树直至最顶层的根结点。该方法的优点是直观易懂缺点是无法给出通用程序。一般链式二叉树的创建方法与通用程序如下。
用广义表构建二叉树。
二叉树的广义表表示法
尽管构建二叉树的方法并不复杂但对于结点多、结构复杂的二叉树却不易用程序来实现。因此有必要寻找更具一般性的二叉树的构建方法。
图1所示的二叉树可以用以下方式重新表示它。
用A(B)表示A有左孩子B无右孩子
用B(C,D)表示B有左孩子C右孩子D
用C(,E)表示C无左孩子但有右孩子E
用D(F,G)表示D有左孩子F右孩子G。
将它们复合起来有A(B(C(,E),D(F,G)))。这是一个字符数组它是上述二叉树的另一种表示法称这种二叉树的表示法为广义表法。
用广义表来表示二叉树其具体规定如下
树的根结点放在最前面。
每个结点的左子树和右子树用逗号隔开。若仅有左子树没有右子树逗号可省略若仅有右子树没有左子树逗号不能省略。
约定广义表用字符型数组 GenList[] 来存储。
广义表构建二叉树的算法
设结点值均用字母来替代先建一棵空二叉树T借助一个简易结点顺序栈 stack 广义表A(B(C(,E),D(F,G)))创建二叉树的具体过程如下
1读A创建新结点AT为空让T.rootA结点。
2读让新结点A入栈置k1栈stack状态为
A
3读B创建新结点B因k1让栈顶结点A的左指针指向B即B←A。
4读让新结点B入栈置k1栈stack状态为
A
B
5读C创建新结点C因k1让栈顶结点B的左指针指向C即C←B。
6读让新结点C入栈置k1栈stack状态为A B C
7读号置k2。
8读E创建新结点E因k2让栈顶结点C的右指针指向E即C→E。
9读栈顶结点C出栈栈stack状态为A B
10读号置k2。
11读D创建新结点D因k2让栈顶结点B的右指针指向D即B→D。
12读让新结点D入栈置k1栈stack状态为A B D
13读F创建新结点F因k1让栈顶结点D的左指针指向F即F←D。
14读号置k2。
15读G创建新结点G因k2让栈顶结点D的右指针指向G即D→G。
16读栈顶结点D出栈栈stack状态为A B
17读栈顶结点B出栈栈stack状态为A
18读栈顶结点A出栈栈stack状态为
至此二叉树创建完毕。
由T.rootAB←AC←BC→E可构建如下图2所示的二叉树。
图2 二叉树的构建过程1 由B→DF←DD→G可构建如图3所示的二叉树。
图3 二叉树的构建过程2 3. 广义表构建二叉树算法的程序实现
#includeiostream
using namespace std;
const int MaxSize 100//顺序栈的最大容量
//结点定义
struct Node
{ char data;//数据域Node *lChild,*rChild;//指针域
};
//二叉树定义
struct BinTree
{ Node *root;
};
//创建空二叉树
void Create(BinTree T)
{ T.rootNULL;
}
//树判空
int IsEmpty(BinTree T)
{ if(T.rootNULL) return 1;else return 0;
}
//广义表创建二叉树
void Create(char GenList[],BinTree T)
{ Node *stack[MaxSize],*NewNode,*p;//简易结点顺序栈,新结点,探测指针int top-1;//置栈空int k,i0;//k1链接左子树,k2链接右子树,i广义表字符下标char ch;do{ chGenList[i];//读取广义表第i个字符switch(ch){ case (://读到左括号stack[top]NewNode;//新结点入栈k1;break;case )://读到右括号top--;break;//栈顶结点出栈case ,://读到逗号k2;break;default://读到字符NewNodenew Node;//新结点申请内存NewNode-datach;//新结点数据域赋值NewNode-lChildNULL;//新结点左指针域赋值NewNode-rChildNULL;//新结点右指针域赋值if(IsEmpty(T))//如果树为空T.rootNewNode;//新结点作为根结点if(k1){ pstack[top];//获取栈顶结点p-lChildNewNode;//让栈顶结点左孩子指向新结点}else if(k2){pstack[top];//获取栈顶结点p-rChildNewNode;//让栈顶结点左孩子指向新结点}}i;//i增1}while(GenList[i]!\0);//逐一读完整个广义表
}
//非递归前序遍历算法
void PreOrder(Node *p)
{ Node *stack[MaxSize];// 简易结点顺序栈int top-1;//置栈空while(p||top!-1)//当p结点所指非空或栈非空时{ if(p)//如果p所指结点非空{ coutp-data;//输出p的值stack[top]p;//p所指结点入栈pp-lChild;//p向左下移}else//如果p结点所指结点为空{ pstack[top--];//p指向栈顶结点,栈顶结点出栈pp-rChild;//p向右下移}}
}
//非递归中序遍历算法
void InOrder(Node *p)
{ Node *stack[MaxSize];//简易结点顺序栈int top-1;//置栈空while(p||top!-1)//当p结点所指非空或栈非空时{ if(p)//如果p所指结点非空{ stack[top]p;//p所指结点入栈pp-lChild;//p向左下移}else//如果p所指结点为空{ pstack[top--];//p指向栈顶结点,栈顶结点出栈coutp-data;//输出p的值pp-rChild;//p向右下移}}
}
//主函数
int main()
{ char GenList[]A(B(C(,E),D(F,G)));//定义广义表BinTree T;//定义二叉树Create(T);//创建空二叉树Create(GenList,T); //创建二叉树cout前序遍历为 ; PreOrder(T.root); coutendl;cout中序遍历为 ; InOrder(T.root); coutendl;return 0;
}程序运行的结果如图4所示。
图4 四、二叉树的遍历 欲在屏幕上形象地输出链式二叉树是一件困难的事一般采用输出它的三个线性序列VLR、LVR和LRV的方式来解决这一问题。
VLR称为前序PreOrder遍历序列它是按先树根再左子树后右子树的次序输出二叉树的结点值。
LVR称为中序InOrder遍历序列它是按先左子树再树根后右子树的次序输出二叉树的结点值。
LRV称为后序PostOrder遍历序列它是按先左子树再右子树后树根的次序输出二叉树的结点值。
所谓前序、中序和后序遍历是相对于根结点位置而言的。例如在中序遍历中根结点在中间而前序遍历是根结点在前面后序遍历是根结点在后面。三种遍历方式一定是先左子树后右子树。
4.1前序遍历 前序遍历的次序为树根—左子树—右子树即从根结点开始处理根结点处理完后往左子树走直到无法前进再处理右子树。
图10 链式二叉树的逻辑结构 【例2】的前序遍历为ABEKC前序遍历的递归算法如下
void PreOrder(Node *p)
{ if(p!NULL){ coutp-data;//访问树根PreOrder(p-lChild);//遍历左子树PreOrder(p-rChild); //遍历右子树}
}4.2中序遍历 中序遍历的次序为左子树—树根—右子树即沿树的左子树一直往下直到无法前进时后退到双亲结点而后再沿右子树一直往下。如果右子树也走完了就退回上层的左结点重复左、中、右的顺序遍历。
【例2】的中序遍历为BEKAC中序遍历的递归算法如下
void InOrder(Node *p)
{ if(p!NULL){ InOrder(p-lChild); //遍历左子树coutp-data; //访问树根InOrder(p-rChild);//遍历右子树}
}【例2】的后序遍历为KEBCA后序遍历的递归算法如下
void PostOrder(Node *p)
{ if(p!NULL){ PostOrder(p-lChild);//遍历左子树PostOrder(p-rChild); //遍历右子树coutp-data; //访问树根}
}#includeiostream
using namespace std;
//二叉树结点定义
struct Node
{char data;//数据域Node* lChild, * rChild;//指针域
};
//二叉树定义
struct BinTree
{Node* root;
};
//创建二叉树
void Create(BinTree T, char x, Node* left, Node* right)
{Node* NewNode;//新结点NewNode new Node;//新结点申请内存NewNode-data x;//新结点数据域赋值NewNode-lChild left;//新结点左指针域赋值NewNode-rChild right;//新结点右指针域赋值T.root NewNode;//让新结点成为该子树根结点
}
//前序遍历
void PreOrder(Node* p)
{if (p ! NULL){cout p-data;//访问树根PreOrder(p-lChild);//遍历左子树PreOrder(p-rChild); //遍历右子树}if (p NULL){cout *;//输出空的节点更清楚的理解PreOrder的调用过程}
}
//中序遍历
void InOrder(Node* p)
{if (p ! NULL){InOrder(p-lChild); //遍历左子树cout p-data; //访问树根InOrder(p-rChild);//遍历右子树}if (p NULL){cout *;//输出空的节点更清楚的理解PreOrder的调用过程}
}
//后序遍历
void PostOrder(Node* p)
{if (p ! NULL){PostOrder(p-lChild);//遍历左子树PostOrder(p-rChild); //遍历右子树cout p-data; //访问树根}if (p NULL){cout *;//输出空的节点更清楚的理解PreOrder的调用过程}
}
//主函数
int main()
{BinTree K, E, B, C, A;Create(K, K, NULL, NULL);//创建结点K的子树Create(E, E, NULL, K.root);//创建结点E的子树Create(B, B, NULL, E.root);//创建结点B的子树Create(C, C, NULL, NULL);//创建结点C的子树Create(A, A, B.root, C.root);//创建结点A的子树cout 前序遍历为 ; PreOrder(A.root); cout endl;cout 中序遍历为 ; InOrder(A.root); cout endl;cout 后序遍历为 ; PostOrder(A.root); cout endl;return 0;
}程序运行的结果如图16所示
【定理1】任意n(n0)个不同结点的二叉树都可由其前序遍历序列和中序遍历序列唯一确定。
【例4】画出前序遍历ABEKC中序遍历BEKAC所确定的二叉树。
1由前序遍历ABEKCA为根结点由中序遍历BEKACBEK为左子树C为右子树其对应的二叉树如图17所示。
2对于左子树由前序遍历BEKB为根结点由中序遍历BEKEK为右子树其对应的二叉树如图18所示。
3对于右子树由前序遍历EKE为根结点由中序遍历EKK为右子树其对应的二叉树如图19所示。
五、常用二叉树 5.1排序二叉树 先给出排序二叉树的定义。
设二叉树的所有结点值互异排序二叉树或者是一棵空树或者是满足以下条件的树
1若左子树不空则左子树上所有结点的值均小于根结点的值左小于根
2若右子树不空则右子树上所有结点的值均大于根结点的值右大于根
3左、右子树也分别是排序二叉树。(递归定义)
排序二叉树定义是由递归方式给出的据此定义可给出排序二叉树的创建方法
首次输入的数据作为此二叉树的根其后输入的数据与根进行比较小于树根的放置到左子树大于树根的放置到右子树。
【例5】依次输入数据3225163527创建一棵排序二叉树。
排序二叉树的创建过程如图20所示 创建排序二叉树的程序如下
#include bits/stdc.h
using namespace std;
//二叉树结点定义
struct Node
{ int data;//数据域Node *lChild,*rChild;//指针域
};
//二叉树定义
struct BinTree
{ Node *root;
};
//创建空二叉树
void Create(BinTree T)
{ T.rootNULL;
}//判空
int IsEmpty(BinTree T)
{ if(T.rootNULL) return 1;else return 0;
}
//创建排序二叉树
void Create(BinTree T,int x)
{ Node *NewNode,*p;NewNodenew Node; //新结点申请内存NewNode-datax;//新结点数据域赋值NewNode-lChildNULL;//新结点左指针域赋值NewNode-rChildNULL;//新结点右指针域赋值int flag0;//新结点入树标识,flag0表示未入树if(IsEmpty(T))//如果二叉树为空{T.rootNewNode;}else//如果二叉树非空{ pT.root;//探测指针指向根结点while(!flag)//当新结点未入树时//理解江老师说的兑奖劵问题{ if(xp-data)//如果新结点的值小于双亲结点的值{ //进入左子树if(p-lChildNULL)//如果左子树为空{ p-lChildNewNode;//新结点成为左子树flag1;//新结点入树}else//如果左子树非空{pp-lChild;//探测指针向左下移}}else//如果新结点的值大于双亲结点的值{ //进入右子树if(p-rChildNULL)//如果右子树为空{ p-rChildNewNode;//新结点成为右子树flag1;//新结点入树}else{pp-rChild;//探测指针向右下移}}}}
}
//前序遍历
void PreOrder(Node *p)
{ if(p!NULL){ coutp-data ;//访问树根PreOrder(p-lChild);//遍历左子树PreOrder(p-rChild);//遍历右子树}
}
//中序遍历
void InOrder(Node *p)
{ if(p!NULL){ InOrder(p-lChild);//遍历左子树coutp-data ;//访问树根InOrder(p-rChild);//遍历右子树}
}
//主函数
int main()
{ BinTree T;//定义二叉树Create(T);//创建空二叉树char c;int x;printf(输入二叉树结点值(用空格隔开,回车结束)\n);while(scanf(%d%c,x,c))//while键盘输入的第一种用法{Create (T,x);//创建排序二叉树if(c\n) break;}cout前序遍历为 ; PreOrder(T.root); coutendl;cout中序遍历为 ; InOrder(T.root); coutendl;return 0;
}程序运行的结果如图21所示 排序二叉树的优点是建树方便中序遍历为升序序列。
5.2哈夫曼树 先介绍几个概念 。
路径长度Path Length 路径上的分支(边)数目。
树的路径长度Tree Path Length 根结点到每个叶子结点的路径长度之和。
树的带权(叶子结点的权值)路径长度Weighted Path Length 其中wi是第i个叶子结点的权值li为从根结点到第i个叶子结点的路径长度n为叶子结点的总数。
最优二叉树 WPL最小的二叉树最优二叉树也称哈夫曼树Huffman Tree。
【例6】图27给出了三棵二叉树分别计算它们的带权路径长度即 W P L WPL WPL 。
图27 二叉树的带权路径长度 解
a W P L 9 × 1 15 × 2 3 × 3 4 × 3 60 WPL9×115×23×34×360 WPL9×115×23×34×360
b W P L 3 × 1 4 × 2 9 × 3 15 × 3 83 WPL3×14×29×315×383 WPL3×14×29×315×383
c W P L 4 × 1 15 × 2 9 × 3 3 × 3 70 WPL4×115×29×33×370 WPL4×115×29×33×370
哈夫曼给出了一个创建最优二叉树的方法。下面我们用一个实例来介绍这一方法。
【例7】设集合{1231052}为叶结点的权值试创建哈夫曼树。
创建哈夫曼树的过程可以由以下步骤和示意图来说明。
1将权值按升序排序构建单结点的二叉树集TT如图28所示。
图28 2从T中选取前两棵的二叉树分别作为左、右子树构造一棵新二叉树注意排序在前的作左子树对T中权值再按升序排序注意如果出现权值相等的情况则原树排前新树排后T如图29所示。
图29 3反复重复第2步的操作T如图30 — 图32所示。
图30 创建过程3 图31 创建过程4 图32 创建过程5
必须指出哈夫曼树的形状不唯一。但如果严格按上述规定来创建哈夫曼树还是唯一
的编程创建哈夫曼树将严格按上述规定进行。
性质1: 哈夫曼树不存在度为1的结点。
性质2: 设哈夫曼树的叶子结点数为 n 0 n_0 n0则哈夫曼树的结点数 n 2 × n 0 − 1 n2×n_0-1 n2×n0−1。
性质3: 哈夫曼树的带权路径长度等于所有度为2的结点值之和。
