第六章 树和二叉树
树的概念和基本术语
二叉树
二叉树遍历
二叉树的计数
树与森林
霍夫曼树树的概念和基本术语树的定义树是由 n (n? 0) 个结点的有限集合。如果 n = 0，称为空树；如果 n > 0，则
有且仅有一个特定的称之为根 (Root)的结点，它只有直接后继，但没有直接前驱；
当 n > 1，除根以外的其它结点划分为 m
(m >0) 个互不相交的有限集 T1,T2,…,T m，
其中每个集合本身又是一棵树，并且称为根的子树 (SubTree)。
A
C
G
B D
E F
K L
H
M
I J
例如
A
只有根结点的树有 13个结点的树其中,A是根；其余结点分成三个互不相交的子集，
T1={B,E,F,K,L}； T2={C,G}； T3={D,H,I,J,M},
T1,T2,T3都是根 A的子树，且本身也是一棵树树的基本术语
1层
2层
4层
3层
height
= 4
A
C
G
B D
E F
K L
H
M
I J
结点
结点的度
叶结点
分支结点
子女
双亲
兄弟
祖先
子孙
结点层次
树的深 度
树的度
森林二叉树 (Binary Tree)
定义五种形态一棵二叉树是结点的一个有限集合，
该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
L LR R
特点 每个结点至多只有两棵子树（二叉树中不存在度大于 2的结点）
性质 1 在二叉树的第 i 层上至多有 2i － 1
个结点。 (i? 1) [证明用归纳法 ]
证明：当 i=1时，只有根结点,2 i-1=2 0=1。
假设对所有 j,i>j?1，命题成立，即第 j层上至多有 2 j-1 个结点。
由归纳假设第 i-1层上至多有 2i － 2个结点。
由于二叉树的每个结点的度至多为 2，故在第 i层上的最大结点数为第 i-1层上的最大结点数的 2倍，即 2* 2i － 2= 2 i-1。
性质性质 2 深度为 k 的二叉树至多有 2 k-1
个结点 (k? 1)。
证明：由性质 1可见，深度为 k的二叉树的最大结点数为
k
i
i
1
12
＝ 20 + 21 + … + 2 k-1 = 2 k-1
k
i
i
1
( 层上的最大结点数）第
＝
性质 3 对任何一棵二叉树 T,如果其叶结点数为 n0,度为 2的结点数为 n2,则 n0＝
n2＋ 1.
证明：若度为 1的结点有 n1 个，总结点个数为 n，总边数为 e，则根据二叉树的定义，
n = n0 + n1 + n2 e = 2n2 + n1 = n - 1
因此，有 2n2 + n1 = n0 + n1 + n2 - 1
n2 = n0 - 1 n0 = n2 + 1
定义 1 满二叉树 (Full Binary Tree)
一棵深度为 k且有 2 k-1个结点的二叉树称为满二叉树。
两种特殊形态的二叉树
6
2
1
754
3
8 9 10 11 13 14 1512
满二叉树
2
1
54
3
6 7
2
1
654
3
非完全二叉树定义 2 完全二叉树 (Complete Binary Tree)
若设二叉树的高度为 h，则共有 h层。除第
h 层外，其它各层 (0? h-1) 的结点数都达到最大个数，第 h 层 从右向左 连续缺若干结点，
这就是完全二叉树。
6
2
1
754
3
8 9 10 11 12
完全二叉树性质 4 具有 n (n? 0) 个结点的完全二叉树的深度为?log2(n)?＋ 1
证明：
设完全二叉树的深度为 h，则根据性质 2和完全二叉树的定义有
2h－ 1 - 1 < n? 2h- 1或 2h－ 1? n < 2h
取对数 h－ 1 < log2n? h，又 h是整数，
因此有 h =?log2(n)? ＋ 1
性质 5 如将一棵有 n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号 0,1,2,…,
n-1，则有以下关系：
若 i = 0,则 i 无双亲若 i > 0,则 i 的双亲为?(i -1)/2?
若 2*i+1 < n,则 i 的左子女为 2*i+1，若 2*i+2 < n,则 i 的右子女为 2*i+2
若结点编号 i为偶数，且 i!=0,则左兄弟结点 i-1.
若结点编号 i为奇数，且 i!=n-1,则右兄弟结点为 i+1.
结点 i 所在层次为?log2(i+1)? 0
7
1 2
3 4 5 6
8 9
完全二叉树 一般二叉树的顺序表示 的顺序表示二叉树的存储结构
1
1 2 3 4 5 6 7 8 910
9
1 2 3 4 0 5 6 7 8 0 0 910
2
4
8 9 10
5 6 7
3
1
2 3
654
7 8
顺序表示
910
链表表示
lChild data rChild
data
lChild rChild
二叉链表含两个指针域的结点结构
lChild data parent rChild
含三个指针域的结点结构
parent
data
lChild rChild
三叉链表二叉树链表表示的示例
A A A
B B B
CCC D D D
FFFE E E
root root root
二叉树 二叉链表 三叉链表三叉链表的静态结构
A
B
C D
FE
root data parent leftChild rightChild
0
1
2
3
4
5
A -1 1 -1
B 0 2 3
C 1 -1 -1
D 1 4 5
E 3 -1 -1
F 3 -1 -1
typedef char TreeData; //结点数据类型
typedef struct node { //结点定义
TreeData data;
struct node * leftChild,* rightchild;
} BinTreeNode;
typedef BinTreeNode * BinTree;
//根指针二叉链表的定义
Void destroy ( BinTreeNode *current )
{//删除根为 current的子树
if ( current != NULL ) {
destroy ( current -> leftChild );
destroy ( current -> rightChild );
delete current;
}
}
基本算法
BinTreeNode *Parent ( BinTreeNode * start,
BinTreeNode * cuurent )
{//找当前结点的双亲结点，并返回
if ( start == NULL ) return NULL;
if ( start->leftChild == current ||
start->rightChild == current )
return start; //找到
BinTreeNode *p; //否则
if (( p = Parent ( start->leftChild,
current ))!= NULL ) return p; //在左子树中找
else return Parent(start->rightChild,
current); //在右子树中找
}
void BinaryTree Traverse ( BinTreeNode
*current,ostream &out )
{//搜索并输出根为 current的二叉树
if ( current != NULL ) {
out << current->data <<;
Traverse ( current->leftChild,out );
Traverse ( current->rightChild,out );
}
}
INTree ( istream&in,BinaryTree & Tree )
{//输入并建立一棵二叉树 Tree
Type item;
in >> item;
While(item!=RefValue)
{
CreateBinTree ( istream& in,
root );
cout <<,,
in >> item;
}
return in
}
OUTree ( ostream& out,BinaryTree&Tree )
{//输出一棵二叉树 Tree
out <<,二叉树的前序遍历,\n";
Traverse (root,out );
out << endl;
return out;
}
二叉树遍历树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。
设访问根结点记作 V
遍历根的左子树记作 L
遍历根的右子树记作 R
则可能的遍历次序有前序 VLR
中序 LVR
后序 LRV
V
L R
中序遍历二叉树算法的定义：
若二叉树为空，则空操作；
否则中序遍历左子树 (L)；
访问根结点 (V)；
中序遍历右子树 (R)。
遍历结果
a + b * c - d - e / f
中序遍历 (Inorder Traversal)
-
-
/+
*a
b
c d
e f
void InOrder ( BinTreeNode *T )
{
if ( T != NULL ) {
InOrder ( T->leftChild );
cout << T->data;
InOrder ( T->rightChild );
}
}
中序遍历二叉树的递归算法
前序遍历二叉树算法的定义：
若二叉树为空，则空操作；
否则访问根结点 (V)；
前序遍历左子树 (L)；
前序遍历右子树 (R)。
遍历结果
- + a * b - c d / e f
前序遍历 (Preorder Traversal)
-
-
/+
*a
b
c d
e f
前序遍历二叉树的递归算法
void PreOrder ( BinTreeNode *T )
{
if ( T != NULL ) {
cout << T->data;
PreOrder ( T->leftChild );
PreOrder ( T->rightChild );
}
}
后序遍历二叉树算法的定义：
若二叉树为空，则空操作；
否则后序遍历左子树 (L)；
后序遍历右子树 (R)；
访问根结点 (V)。
遍历结果
a b c d - * + e f / -
后序遍历 (Postorder Traversal)
-
-
/+
*a
b
c d
e f
后序遍历二叉树的递归算法：
void PostOrder ( BinTreeNode * T ) {
if ( T != NULL ) {
PostOrder ( T->leftChild );
PostOrder ( T->rightChild );
cout << T->data;
}
}
二叉树遍历应用
以递归方式建立二叉树。
输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归,
此值在 RefValue中。例如用,@”或用,-
1”表示字符序列或正整数序列空结点。
1,按前序建立二叉树 (递归算法 )
如图所示的二叉树的前序遍历顺序为
A B C @ @ D E @ G @ @ F @ @ @
A
B
C D
E
G
F@ @
@
@ @
@ @
@
void Crt_BinTree ( ifstream& in,BinTreeNode *& T ) {
TreeData x;
if ( !in.eof ( ) ) {
in >> x; //读入根结点的值
if ( x != RefValue ) {
T = new BinTreeNode; //建立根结点
if ( T == NULL ) {
cerr <<,存储分配错 !” << endl;
exit (1);
}
T->data = x;
Crt_BinTree ( in,T->leftChild );
Crt_BinTree ( in,T->rightChild );
}
else T = NULL;
}
}
建立二叉树的主程序
void createBinTree ( filename,
BinTreeNode *& Tree )
{//建立一棵二叉树 Tree.
TreeData item;
ifstream fin(filename);//打开文件
if ( !fin )
{ cerr <<,文件未发现 !” << endl;
exit (1);
}
Crt_BinTree ( ifstream& fin,Tree );
fin.close ( );//关闭文件
}
int Count ( BinTreeNode *T ) {
if ( T == NULL ) return 0;
else return 1 + Count ( T->leftChild )
+ Count ( T->rightChild );
}
2,计算二叉树结点个数 (递归算法 )
int Leaf_Count(Bitree T)
{//求二叉树中叶子结点的数目
if(!T) return 0; //空树没有叶子
else if(!T->lchild&&!T->rchild) return 1;
//叶子结点
else return Leaf_Count(T-lchild)+Leaf_Count(T-
rchild); //左子树的叶子数加上右子树的叶子数
}
3,求二叉树中叶子结点的个数
int Height ( BinTreeNode * T )
{
if ( T == NULL ) return -1;
else{
int m = Height ( T->leftChild );
int n = Height ( T->rightChild ) );
return (m > n)? m+1,n+1;
}
}
4,求二叉树高度 (递归算法 )
5,复制二叉树 (递归算法 )
int Copy( BinTreeNode * T )
{
if ( T == NULL ) return -1;
BinTreeNode * temp=new BinTreeNode;
Temp->data=T->data;
Temp-> leftChild = Copy( T->leftChild );
Temp-> rightChild = Copy(T->rightChild );
return temp;
}
6,判断二叉树等价 (递归算法 )
int Equal( BinTreeNode *a,BinTreeNode *b) {
if ( a == NULL && b == NULL ) return 1;
if ( a !== NULL && b !== NULL
&& a->data==b->data
&& equal( a->leftChild,b->leftChild)
&& equal( a->rightChild,b->rightChild) )
return 1;
return 0;//如果 a和 b的子树不等同，则函数返回 0
}
中序遍历二叉树 (非递归算法 )用栈实现
b
a
a
b c
d e
a
d
a a
a b入栈 b退栈访问 d入栈 d退栈访问
e 退栈访问
e
c c
栈空a退栈访问 c e 入栈 c 退栈访问
void InOrder ( BinTree T ) {
stack S; InitStack( &S ); //递归工作栈
BinTreeNode *p = T; //初始化
while ( p != NULL || !StackEmpty(&S) ) {
if( p != NULL )
{ Push(&S,p); p = p->leftChild; }
if ( !StackEmpty(&S) ) { //栈非空
Pop(&S,p); //退栈
cout << p->data << endl; //访问根
p = p->rightChild;
}//if
}//while
return ok;
}
a
b c
d e
前序遍历二叉树 (非递归算法 )用栈实现
a
cb c
d e
d
c c
访问
a
进栈
c
左进
b
访问
b
进栈
d
左进空退栈
d
访问
d
左进空退栈
c
访问
c
左进
e
访问
e
左进空退栈
结束
void PreOrder( BinTree T ) {
stack S; InitStack(&S); //递归工作栈
BinTreeNode * p = T; Push (&S,NULL);
while ( p != NULL ) {
cout << p->data << endl;
if ( p->rightChild != NULL )
Push ( &S,p->rightChild );
if ( p->leftChild != NULL )
p = p->leftChild;//进左子树
else Pop( &S,p );
}
}
a
b c
d e
后序遍历二叉树 (非递归算法 )用栈实现后序遍历时使用的栈的结点定义
typedef struct {
BinTreeNode *ptr; //结点指针
enum tag{ L,R }; //该结点退栈标记
} StackNode;
根结点的
tag = L，表示从左子树退出,访问右子树。
tag = R,表示 从右子树退出,访问根。
ptr tag{L,R}
void PostOrder ( BinTree T ) {
stack S; InitStack(&S); StackNode w;
BinTreeNode * p = T;
do {
while ( p != NULL ) { //向左子树走
w.ptr = p; w.tag = L; Push (&S,w);
p = p->leftChild;
}
int continue = 1; //继续循环标记
while ( continue && !StackEmpty(&S) ) {
Pop (&S,w); p = w.ptr;
switch ( w.tag ) { //判断栈顶 tag标记
case L,w.tag = R; Push (&S,w);
continue = 0;
p = p->rightChild; break;
case R,cout << p->data << endl;
}
}
} while ( p != NULL || !StackEmpty(&S) );
cout << endl;
}
练习,交换二叉树各结点的左、右子树
(递归算法 )
void unknown ( BinTreeNode * T ) {
BinTreeNode *p = T,*temp;
if ( p != NULL ) {
temp = p->leftChild;
p->leftChild = p->rightChild;
p->rightChild = temp;
unknown ( p->leftChild );
unknown ( p->rightChild );
}
}
void unknown ( BinTreeNode * T ) {
BinTreeNode *p = T,*temp;
while ( p != NULL ) {
temp = p->leftChild;
p->leftChild = p->rightChild;
p->rightChild = temp;
unknown ( p->leftChild );
p = p->rightChild;
}
}
不用栈消去递归算法中的第二个递归语句使用栈消去递归算法中的两个递归语句
void unknown ( BinTreeNode * T ) {
BinTreeNode *p,*temp;
stack S; InitEmpty (&S);
if ( T != NULL ) {
push(&S,T);
while ( ! StackEmpty(&S) ) {
Pop(&S,p); //栈中退出一个结点
temp = p->leftChild; //交换子女
p->leftChild = p->rightChild;
p->rightChild = temp;
if ( p->rightChild != NULL )
push (&S,p->rightChild );
if ( p->leftChild != NULL )
push (&S,p->leftChild );
}
}
}
LeftThread=0,LeftChild为 左子女指针
LeftThread=1,LeftChild为 前驱线索
RightThread=0,RightChild为 右子女指针
RightThread=1,RightChild为 后继指针
LeftChild RightChilddata
LeftThread RightThread
线索二叉树 (Threaded Binary Tree)
结点结构
template <class Type> class ThreadNode {
friend class ThreadTree<Type>;
private:
int leftThread,rightThread;
ThreadNode<Type> *leftChild,*rightChild;
Type data;
public:
ThreadNode ( const Type item )
,data (item),leftChild (NULL),
rightChild (NULL),leftThread (0),
rightThread (0) { }
};
中序线索二叉树的类定义
template <class Type> class ThreadTree;
template <class Type> class ThreadTree {
private:
ThreadNode<Type> * root; //根
InThread ( ThreadNode <Type> * current,
ThreadNode <Type> * pre ); //建树
public:
ThreadTree ( ),root (NULL) { }; //构造函数
ThreadNode<Type> *
First ( ThreadNode <Type> * current );
ThreadNode<Type> *
Last ( ThreadNode <Type> * current );
ThreadNode<Type> *
Next ( ThreadNode <Type> * current );
ThreadNode<Type> *
Prior ( ThreadNode <Type> * current );
…………
}
通过中序遍历建立中序线索化二叉树
template <class Type>
void ThreadTree<Type>,:
InThread ( ThreadNode<Type> * current,
ThreadNode<Type> *& pre ) {
if ( current != NULL ) {
InThread ( current->leftChild,pre );
//递归,左子树线索化
if ( current->leftChild == NULL ) {
current->leftChild = pre;
current->leftThread = 1;
} //建立当前结点的前驱线索
if ( pre != NULL &&
pre->rightChild == NULL ) {
pre->rightChild = current;
pre->rightThread = 1;
} //建立前驱结点的后继线索
pre = current; //前驱跟上当前指针
InThread ( current->rightChild,pre );
//递归,右子树线索化
}
}
树的存储结构
双亲表示：以一组连续空间存储树的结点，
同时在 结点中附设一个指针，存放双亲结点在链表中的位置。
树与森林
A
B C D
E F G
data
parent
A B C D E F G
-1 0 0 0 1 1 3
0 1 2 3 4 5 6
用双亲表示实现的树定义
#define MaxSize //最大结点个数
typedef char TreeData; //结点数据
typedef struct { //树结点定义
TreeData data;
int parent;
} TreeNode;
typedef TreeNode Tree[MaxSize]; //树
A
B C D
E F G
左子女 -右兄弟表示法第一种解决方案 等数量的链域
data child1 child2 child3 childd
A
B C D
E F G
空链域 n(k-1)+1个结点结构 data firstChild nextSibling
A
B C D
E F G
空链域 n+1个第二种解决方案 树的左子女 -右兄弟表示
（二叉链表表示）
B
C
D
G
F
E
A?
typedef char TreeData;
typedef struct node {
TreeData data;
struct node *firstChild,*nextSibling;
} TreeNode;
typedef TreeNode * Tree;
用左子女 -右兄弟表示实现的树定义
T1 T2 T3
T1 T2 T3
A F H
B C D G I J
E K
A F
B
C
D
E
G
H
I
K J
A
B
C
E
D
H
I
K J
F
G3 棵树的森林各棵树的二叉树表示森林的二叉树表示
森林与二叉树的转换树的二叉树表示,
树的遍历
深度优先遍历
先根次序遍历
后根次序遍历
A
B C D
E F G
A
B
CE
D
G
F
深度优先遍历
当树非空时
访问根结点
依次先根遍历根的各棵子树
树先根遍历 ABEFCDG
对应二叉树前序遍历 ABEFCDG
树的先根遍历结果与其对应二叉树表示的前序遍历结果相同
树的先根遍历可以借助对应二叉树的前序遍历算法实现
A
B
CE
D
G
F
树的 先根次序 遍历
树的 后根次序 遍历,
当树非空时
依次后根遍历根的各棵子树
访问根结点
树后根遍历 EFBCGDA
对应二叉树中序遍历 EFBCGDA
树的后根遍历结果与其对应二叉树表示的中序遍历结果相同
树的后根遍历可以借助对应二叉树的中序遍历算法实现
A
B
CE
D
G
F
二叉树的计数
由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。
例,前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG },构造二叉树过程如下：
HBDF EKCG
A
EKCG
A
B
H DF
KCG
EKCG
A
B
H DF
EKCG
A
B
H F
D
E
A
B
H F
D
E
A
B
H F
D
C
K G
如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。
6
1
2
3 4
5
7
8 9
6
1
2
3 7
5
8
4 9
固定前序排列,选择所有可能的中序排列,
可以构造多少种不同的二叉树？
例如,有 3 个数据 { 1,2,3 }，可得 5 种不同的二叉树。它们的前序排列均为 123，中序序列可能是 321,231,213,132,123.
1
2
3
1
2
3
1
2 3
1
2
3
1
2
3
具有 n个结点不同形态的树的数目和具有
n-1个结点互不相似的二叉树的数目相同。
有 0个,1个,2个,3个结点的不同二叉树如下
b0 =1 b1 =1 b2 =2
b3 =5
b4 =14
!!
)!(2
1
1
1
1
2 nn
n
nn
b C n nn
计算具有 n 个结点的不同二叉树的棵数最终结果：
bi bn-i-1
1
1
0
1
n
i
inin bbb
霍夫曼树 (Huffman Tree)
路径长度 (Path Length)
两个结点之间的路径长度 PL 是连接两结点的路径上的分支数。
树的外部路径长度是各叶结点 (外结点 )到根结点的路径长度之和 EPL。
树的内部路径长度是各非叶结点 (内结点 )
到根结点的路径长度之和 IPL。
树的路径长度 PL = EPL + IPL
1
2 3
4 5 6 7
8
2 3
4 5
6 7
8树的外部路径长度
EPL = 3*1+2*3 = 9
树的外部路径长度
EPL = 1*1+2*1+3*1+4*1 = 10
1
带权路径长度 (Weighted Path Length,WPL)
二叉树的带权 (外部 ) 路径长度是树的各叶结点所带的权值 wi 与该结点到根的路径长度 li 的乘积的和。
1
0
n
i
ii lwW P L
WPL = 2*2+ WPL = 2*1+ WPL = 7*1+
4*2+5*2+ 4*2+5*3+ 5*2+2*3+
7*2 = 36 7*3 = 46 4*3 = 35
2
2
24
4
45 5
5
7
7
7
带权 (外部 )路径长度达到最小霍夫曼树
带权路径长度达到最小的二叉树即为霍夫曼树。
在霍夫曼树中，权值大的结点离根最近。
(1) 由给定的 n 个权值 {w0,w1,w2,…,w n-1}，
构造具有 n 棵扩充二叉树的森林 F = { T0,T1,
T2,…,T n-1 }，其中每棵扩充二叉树 Ti 只有一个带权值 wi 的根结点,其左、右子树均为空。
霍夫曼 算法
(2) 重复以下步骤,直到 F 中仅剩下一棵树为止：
① 在 F 中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
② 在 F 中删去这两棵二叉树。
③ 把新的二叉树加入 F。
F,{7} {5} {2} {4} F,{7} {5} {6}
F,{7} {11}
7 5 2 4
初始 合并 {2} {4}
7 5
2 4
6
F,{18} 11
7 5
2 4
6
合并 {5} {6}
5
合并 {7} {11} 2
7
4
6
11
18
举例霍夫曼树的构造过程
5 27 4
Weight parent leftChild rightChild
7 -1 -1 -1
5 -1 -1 -1
2 -1 -1 -1
4 -1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
0
1
2
3
4
5
6
上例存储结构初 态
5
2
7
4
6
Weight parent leftChild rightChild
7 -1 -1 -1
5 -1 -1 -1
2 -1 -1 -1
4 -1 -1 -1
6 -1 -1 -1
-1 -1 -1
-1 -1 -1
0
1
2
3
4
5
6
p1
p2
4
4
2 3i
过 程
5
2
7
4
6
11
Weight parent leftChild rightChild
7 -1 -1 -1
5 -1 -1 -1
2 4 -1 -1
4 4 -1 -1
6 -1 2 3
11 -1 -1 -1
-1 -1 -1
0
1
2
3
4
5
6
p1
p2
5
5
1 4i
5
2
7
4
6
11
Weight parent leftChild rightChild
7 -1 -1 -1
5 5 -1 -1
2 4 -1 -1
4 4 -1 -1
6 5 2 3
11 -1 1 4
18 -1 -1 -1
0
1
2
3
4
5
6
p1
p2
6
6
0 5i
18
终 态
const int n = 20;//叶结点数
const int m = 2*n -1;//结点数
typedef struct {
float weight;
int parent,leftChild,rightChild;
} HTNode;
typedef HTNode HuffmanTree[m];
霍夫曼树的定义建立霍夫曼树的算法
void CreateHuffmanTree ( HuffmanTree T,
float fr[ ] ) {
for ( int i = 0; i < n; i++ )
T[i].weight = fr[i];
for ( i = 0; i < m; i++ ) {
T[i].parent = -1;
T[i].leftChild = -1;
T[i].rightChild = -1;
}
for ( i = n; i < m; i++ ) {
int min1 = min2 = MaxNum;
int pos1,pos2;
for ( int j = 0; j < i; j++ )
if ( T[j].parent == -1 )
if ( T[j].weight < min1 )
{ pos2 = pos1; min2 = min1;
pos1 = j; min1 = T[j].weight;
}
else if ( T[j].weight < min2 )
{ pos2 = j; min2 = T[j].weight; }
T[i].leftChild = pos1;
T[i].rightChild = pos2;
T[i].weight =
T[pos1].weight + T[pos2].weight;
T[pos1].parent = T[pos2].parent = i;
}
}
最佳判定树考试成绩分布表
[ 0,6 0 ) [ 6 0,7 0 ) [ 7 0,8 0 ) [ 8 0,9 0 ) [ 9 0,1 0 0 )
不及格 及格 中 良 优
0,1 0 0,15 0,2 5 0,3 5 0,1 5
判定树不及格及格中良 优
<60?
<70?
<80?
<90?
0.10
0.15
0.25
0.35 0.15
≥
≥
≥
≥<
<
<
<
WPL = 0.10*1+0.15*2+0.25*3+0.35*4+0.15*4
= 3.15
最佳判定树不及格 及格中 良 优<60?
<70?
<80?
<90?
0.10 0.15
0.25 0.35 0.15
≥
≥
≥
≥<
<
<
<
WPL = 0.10*3+0.15*3+0.25*2+0.35*2+0.15*2
= 0.3+0.45+0.5+0.7+0.3 = 2.25
霍夫曼编码主要用途是实现数据压缩。
设给出一段报文：
CAST CAST SAT AT A TASA
字符集合是 { C,A,S,T }，各个字符出现的频度 (次数 )是 W＝ { 2,7,4,5 }。
若给每个字符以等长编码
A,00 T,10 C,01 S,11
则总编码长度为 ( 2+7+4+5 ) * 2 = 36,
若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。
各字符出现概率为 { 2/18,7/18,4/18,5/18 },
化整为 { 2,7,4,5 }。以它们为各叶结点上的权值,建立霍夫曼树。 左分支赋 0，右分支赋
1，得霍夫曼编码 (变长编码 )。
7 2 5 4
0 1
00 11
A C T S
A,0 T,10 C,110 S,111
它的总 编码长度,7*1+5*2+( 2+4 )*3 = 35。
比等长编码的情形要短。
总编码长度正好等于霍夫曼树的带权路径长度 WPL。
霍夫曼编码是一种 无前缀编码 。解码时不会混淆。
霍夫曼编码树
0
0
0
1
1
1
2 4
5
7
树的概念和基本术语
二叉树
二叉树遍历
二叉树的计数
树与森林
霍夫曼树树的概念和基本术语树的定义树是由 n (n? 0) 个结点的有限集合。如果 n = 0，称为空树；如果 n > 0，则
有且仅有一个特定的称之为根 (Root)的结点，它只有直接后继，但没有直接前驱；
当 n > 1，除根以外的其它结点划分为 m
(m >0) 个互不相交的有限集 T1,T2,…,T m，
其中每个集合本身又是一棵树，并且称为根的子树 (SubTree)。
A
C
G
B D
E F
K L
H
M
I J
例如
A
只有根结点的树有 13个结点的树其中,A是根；其余结点分成三个互不相交的子集，
T1={B,E,F,K,L}； T2={C,G}； T3={D,H,I,J,M},
T1,T2,T3都是根 A的子树，且本身也是一棵树树的基本术语
1层
2层
4层
3层
height
= 4
A
C
G
B D
E F
K L
H
M
I J
结点
结点的度
叶结点
分支结点
子女
双亲
兄弟
祖先
子孙
结点层次
树的深 度
树的度
森林二叉树 (Binary Tree)
定义五种形态一棵二叉树是结点的一个有限集合，
该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
L LR R
特点 每个结点至多只有两棵子树（二叉树中不存在度大于 2的结点）
性质 1 在二叉树的第 i 层上至多有 2i － 1
个结点。 (i? 1) [证明用归纳法 ]
证明：当 i=1时，只有根结点,2 i-1=2 0=1。
假设对所有 j,i>j?1，命题成立，即第 j层上至多有 2 j-1 个结点。
由归纳假设第 i-1层上至多有 2i － 2个结点。
由于二叉树的每个结点的度至多为 2，故在第 i层上的最大结点数为第 i-1层上的最大结点数的 2倍，即 2* 2i － 2= 2 i-1。
性质性质 2 深度为 k 的二叉树至多有 2 k-1
个结点 (k? 1)。
证明：由性质 1可见，深度为 k的二叉树的最大结点数为
k
i
i
1
12
＝ 20 + 21 + … + 2 k-1 = 2 k-1
k
i
i
1
( 层上的最大结点数）第
＝
性质 3 对任何一棵二叉树 T,如果其叶结点数为 n0,度为 2的结点数为 n2,则 n0＝
n2＋ 1.
证明：若度为 1的结点有 n1 个，总结点个数为 n，总边数为 e，则根据二叉树的定义，
n = n0 + n1 + n2 e = 2n2 + n1 = n - 1
因此，有 2n2 + n1 = n0 + n1 + n2 - 1
n2 = n0 - 1 n0 = n2 + 1
定义 1 满二叉树 (Full Binary Tree)
一棵深度为 k且有 2 k-1个结点的二叉树称为满二叉树。
两种特殊形态的二叉树
6
2
1
754
3
8 9 10 11 13 14 1512
满二叉树
2
1
54
3
6 7
2
1
654
3
非完全二叉树定义 2 完全二叉树 (Complete Binary Tree)
若设二叉树的高度为 h，则共有 h层。除第
h 层外，其它各层 (0? h-1) 的结点数都达到最大个数，第 h 层 从右向左 连续缺若干结点，
这就是完全二叉树。
6
2
1
754
3
8 9 10 11 12
完全二叉树性质 4 具有 n (n? 0) 个结点的完全二叉树的深度为?log2(n)?＋ 1
证明：
设完全二叉树的深度为 h，则根据性质 2和完全二叉树的定义有
2h－ 1 - 1 < n? 2h- 1或 2h－ 1? n < 2h
取对数 h－ 1 < log2n? h，又 h是整数，
因此有 h =?log2(n)? ＋ 1
性质 5 如将一棵有 n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号 0,1,2,…,
n-1，则有以下关系：
若 i = 0,则 i 无双亲若 i > 0,则 i 的双亲为?(i -1)/2?
若 2*i+1 < n,则 i 的左子女为 2*i+1，若 2*i+2 < n,则 i 的右子女为 2*i+2
若结点编号 i为偶数，且 i!=0,则左兄弟结点 i-1.
若结点编号 i为奇数，且 i!=n-1,则右兄弟结点为 i+1.
结点 i 所在层次为?log2(i+1)? 0
7
1 2
3 4 5 6
8 9
完全二叉树 一般二叉树的顺序表示 的顺序表示二叉树的存储结构
1
1 2 3 4 5 6 7 8 910
9
1 2 3 4 0 5 6 7 8 0 0 910
2
4
8 9 10
5 6 7
3
1
2 3
654
7 8
顺序表示
910
链表表示
lChild data rChild
data
lChild rChild
二叉链表含两个指针域的结点结构
lChild data parent rChild
含三个指针域的结点结构
parent
data
lChild rChild
三叉链表二叉树链表表示的示例
A A A
B B B
CCC D D D
FFFE E E
root root root
二叉树 二叉链表 三叉链表三叉链表的静态结构
A
B
C D
FE
root data parent leftChild rightChild
0
1
2
3
4
5
A -1 1 -1
B 0 2 3
C 1 -1 -1
D 1 4 5
E 3 -1 -1
F 3 -1 -1
typedef char TreeData; //结点数据类型
typedef struct node { //结点定义
TreeData data;
struct node * leftChild,* rightchild;
} BinTreeNode;
typedef BinTreeNode * BinTree;
//根指针二叉链表的定义
Void destroy ( BinTreeNode *current )
{//删除根为 current的子树
if ( current != NULL ) {
destroy ( current -> leftChild );
destroy ( current -> rightChild );
delete current;
}
}
基本算法
BinTreeNode *Parent ( BinTreeNode * start,
BinTreeNode * cuurent )
{//找当前结点的双亲结点，并返回
if ( start == NULL ) return NULL;
if ( start->leftChild == current ||
start->rightChild == current )
return start; //找到
BinTreeNode *p; //否则
if (( p = Parent ( start->leftChild,
current ))!= NULL ) return p; //在左子树中找
else return Parent(start->rightChild,
current); //在右子树中找
}
void BinaryTree Traverse ( BinTreeNode
*current,ostream &out )
{//搜索并输出根为 current的二叉树
if ( current != NULL ) {
out << current->data <<;
Traverse ( current->leftChild,out );
Traverse ( current->rightChild,out );
}
}
INTree ( istream&in,BinaryTree & Tree )
{//输入并建立一棵二叉树 Tree
Type item;
in >> item;
While(item!=RefValue)
{
CreateBinTree ( istream& in,
root );
cout <<,,
in >> item;
}
return in
}
OUTree ( ostream& out,BinaryTree&Tree )
{//输出一棵二叉树 Tree
out <<,二叉树的前序遍历,\n";
Traverse (root,out );
out << endl;
return out;
}
二叉树遍历树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。
设访问根结点记作 V
遍历根的左子树记作 L
遍历根的右子树记作 R
则可能的遍历次序有前序 VLR
中序 LVR
后序 LRV
V
L R
中序遍历二叉树算法的定义：
若二叉树为空，则空操作；
否则中序遍历左子树 (L)；
访问根结点 (V)；
中序遍历右子树 (R)。
遍历结果
a + b * c - d - e / f
中序遍历 (Inorder Traversal)
-
-
/+
*a
b
c d
e f
void InOrder ( BinTreeNode *T )
{
if ( T != NULL ) {
InOrder ( T->leftChild );
cout << T->data;
InOrder ( T->rightChild );
}
}
中序遍历二叉树的递归算法
前序遍历二叉树算法的定义：
若二叉树为空，则空操作；
否则访问根结点 (V)；
前序遍历左子树 (L)；
前序遍历右子树 (R)。
遍历结果
- + a * b - c d / e f
前序遍历 (Preorder Traversal)
-
-
/+
*a
b
c d
e f
前序遍历二叉树的递归算法
void PreOrder ( BinTreeNode *T )
{
if ( T != NULL ) {
cout << T->data;
PreOrder ( T->leftChild );
PreOrder ( T->rightChild );
}
}
后序遍历二叉树算法的定义：
若二叉树为空，则空操作；
否则后序遍历左子树 (L)；
后序遍历右子树 (R)；
访问根结点 (V)。
遍历结果
a b c d - * + e f / -
后序遍历 (Postorder Traversal)
-
-
/+
*a
b
c d
e f
后序遍历二叉树的递归算法：
void PostOrder ( BinTreeNode * T ) {
if ( T != NULL ) {
PostOrder ( T->leftChild );
PostOrder ( T->rightChild );
cout << T->data;
}
}
二叉树遍历应用
以递归方式建立二叉树。
输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归,
此值在 RefValue中。例如用,@”或用,-
1”表示字符序列或正整数序列空结点。
1,按前序建立二叉树 (递归算法 )
如图所示的二叉树的前序遍历顺序为
A B C @ @ D E @ G @ @ F @ @ @
A
B
C D
E
G
F@ @
@
@ @
@ @
@
void Crt_BinTree ( ifstream& in,BinTreeNode *& T ) {
TreeData x;
if ( !in.eof ( ) ) {
in >> x; //读入根结点的值
if ( x != RefValue ) {
T = new BinTreeNode; //建立根结点
if ( T == NULL ) {
cerr <<,存储分配错 !” << endl;
exit (1);
}
T->data = x;
Crt_BinTree ( in,T->leftChild );
Crt_BinTree ( in,T->rightChild );
}
else T = NULL;
}
}
建立二叉树的主程序
void createBinTree ( filename,
BinTreeNode *& Tree )
{//建立一棵二叉树 Tree.
TreeData item;
ifstream fin(filename);//打开文件
if ( !fin )
{ cerr <<,文件未发现 !” << endl;
exit (1);
}
Crt_BinTree ( ifstream& fin,Tree );
fin.close ( );//关闭文件
}
int Count ( BinTreeNode *T ) {
if ( T == NULL ) return 0;
else return 1 + Count ( T->leftChild )
+ Count ( T->rightChild );
}
2,计算二叉树结点个数 (递归算法 )
int Leaf_Count(Bitree T)
{//求二叉树中叶子结点的数目
if(!T) return 0; //空树没有叶子
else if(!T->lchild&&!T->rchild) return 1;
//叶子结点
else return Leaf_Count(T-lchild)+Leaf_Count(T-
rchild); //左子树的叶子数加上右子树的叶子数
}
3,求二叉树中叶子结点的个数
int Height ( BinTreeNode * T )
{
if ( T == NULL ) return -1;
else{
int m = Height ( T->leftChild );
int n = Height ( T->rightChild ) );
return (m > n)? m+1,n+1;
}
}
4,求二叉树高度 (递归算法 )
5,复制二叉树 (递归算法 )
int Copy( BinTreeNode * T )
{
if ( T == NULL ) return -1;
BinTreeNode * temp=new BinTreeNode;
Temp->data=T->data;
Temp-> leftChild = Copy( T->leftChild );
Temp-> rightChild = Copy(T->rightChild );
return temp;
}
6,判断二叉树等价 (递归算法 )
int Equal( BinTreeNode *a,BinTreeNode *b) {
if ( a == NULL && b == NULL ) return 1;
if ( a !== NULL && b !== NULL
&& a->data==b->data
&& equal( a->leftChild,b->leftChild)
&& equal( a->rightChild,b->rightChild) )
return 1;
return 0;//如果 a和 b的子树不等同，则函数返回 0
}
中序遍历二叉树 (非递归算法 )用栈实现
b
a
a
b c
d e
a
d
a a
a b入栈 b退栈访问 d入栈 d退栈访问
e 退栈访问
e
c c
栈空a退栈访问 c e 入栈 c 退栈访问
void InOrder ( BinTree T ) {
stack S; InitStack( &S ); //递归工作栈
BinTreeNode *p = T; //初始化
while ( p != NULL || !StackEmpty(&S) ) {
if( p != NULL )
{ Push(&S,p); p = p->leftChild; }
if ( !StackEmpty(&S) ) { //栈非空
Pop(&S,p); //退栈
cout << p->data << endl; //访问根
p = p->rightChild;
}//if
}//while
return ok;
}
a
b c
d e
前序遍历二叉树 (非递归算法 )用栈实现
a
cb c
d e
d
c c
访问
a
进栈
c
左进
b
访问
b
进栈
d
左进空退栈
d
访问
d
左进空退栈
c
访问
c
左进
e
访问
e
左进空退栈
结束
void PreOrder( BinTree T ) {
stack S; InitStack(&S); //递归工作栈
BinTreeNode * p = T; Push (&S,NULL);
while ( p != NULL ) {
cout << p->data << endl;
if ( p->rightChild != NULL )
Push ( &S,p->rightChild );
if ( p->leftChild != NULL )
p = p->leftChild;//进左子树
else Pop( &S,p );
}
}
a
b c
d e
后序遍历二叉树 (非递归算法 )用栈实现后序遍历时使用的栈的结点定义
typedef struct {
BinTreeNode *ptr; //结点指针
enum tag{ L,R }; //该结点退栈标记
} StackNode;
根结点的
tag = L，表示从左子树退出,访问右子树。
tag = R,表示 从右子树退出,访问根。
ptr tag{L,R}
void PostOrder ( BinTree T ) {
stack S; InitStack(&S); StackNode w;
BinTreeNode * p = T;
do {
while ( p != NULL ) { //向左子树走
w.ptr = p; w.tag = L; Push (&S,w);
p = p->leftChild;
}
int continue = 1; //继续循环标记
while ( continue && !StackEmpty(&S) ) {
Pop (&S,w); p = w.ptr;
switch ( w.tag ) { //判断栈顶 tag标记
case L,w.tag = R; Push (&S,w);
continue = 0;
p = p->rightChild; break;
case R,cout << p->data << endl;
}
}
} while ( p != NULL || !StackEmpty(&S) );
cout << endl;
}
练习,交换二叉树各结点的左、右子树
(递归算法 )
void unknown ( BinTreeNode * T ) {
BinTreeNode *p = T,*temp;
if ( p != NULL ) {
temp = p->leftChild;
p->leftChild = p->rightChild;
p->rightChild = temp;
unknown ( p->leftChild );
unknown ( p->rightChild );
}
}
void unknown ( BinTreeNode * T ) {
BinTreeNode *p = T,*temp;
while ( p != NULL ) {
temp = p->leftChild;
p->leftChild = p->rightChild;
p->rightChild = temp;
unknown ( p->leftChild );
p = p->rightChild;
}
}
不用栈消去递归算法中的第二个递归语句使用栈消去递归算法中的两个递归语句
void unknown ( BinTreeNode * T ) {
BinTreeNode *p,*temp;
stack S; InitEmpty (&S);
if ( T != NULL ) {
push(&S,T);
while ( ! StackEmpty(&S) ) {
Pop(&S,p); //栈中退出一个结点
temp = p->leftChild; //交换子女
p->leftChild = p->rightChild;
p->rightChild = temp;
if ( p->rightChild != NULL )
push (&S,p->rightChild );
if ( p->leftChild != NULL )
push (&S,p->leftChild );
}
}
}
LeftThread=0,LeftChild为 左子女指针
LeftThread=1,LeftChild为 前驱线索
RightThread=0,RightChild为 右子女指针
RightThread=1,RightChild为 后继指针
LeftChild RightChilddata
LeftThread RightThread
线索二叉树 (Threaded Binary Tree)
结点结构
template <class Type> class ThreadNode {
friend class ThreadTree<Type>;
private:
int leftThread,rightThread;
ThreadNode<Type> *leftChild,*rightChild;
Type data;
public:
ThreadNode ( const Type item )
,data (item),leftChild (NULL),
rightChild (NULL),leftThread (0),
rightThread (0) { }
};
中序线索二叉树的类定义
template <class Type> class ThreadTree;
template <class Type> class ThreadTree {
private:
ThreadNode<Type> * root; //根
InThread ( ThreadNode <Type> * current,
ThreadNode <Type> * pre ); //建树
public:
ThreadTree ( ),root (NULL) { }; //构造函数
ThreadNode<Type> *
First ( ThreadNode <Type> * current );
ThreadNode<Type> *
Last ( ThreadNode <Type> * current );
ThreadNode<Type> *
Next ( ThreadNode <Type> * current );
ThreadNode<Type> *
Prior ( ThreadNode <Type> * current );
…………
}
通过中序遍历建立中序线索化二叉树
template <class Type>
void ThreadTree<Type>,:
InThread ( ThreadNode<Type> * current,
ThreadNode<Type> *& pre ) {
if ( current != NULL ) {
InThread ( current->leftChild,pre );
//递归,左子树线索化
if ( current->leftChild == NULL ) {
current->leftChild = pre;
current->leftThread = 1;
} //建立当前结点的前驱线索
if ( pre != NULL &&
pre->rightChild == NULL ) {
pre->rightChild = current;
pre->rightThread = 1;
} //建立前驱结点的后继线索
pre = current; //前驱跟上当前指针
InThread ( current->rightChild,pre );
//递归,右子树线索化
}
}
树的存储结构
双亲表示：以一组连续空间存储树的结点，
同时在 结点中附设一个指针，存放双亲结点在链表中的位置。
树与森林
A
B C D
E F G
data
parent
A B C D E F G
-1 0 0 0 1 1 3
0 1 2 3 4 5 6
用双亲表示实现的树定义
#define MaxSize //最大结点个数
typedef char TreeData; //结点数据
typedef struct { //树结点定义
TreeData data;
int parent;
} TreeNode;
typedef TreeNode Tree[MaxSize]; //树
A
B C D
E F G
左子女 -右兄弟表示法第一种解决方案 等数量的链域
data child1 child2 child3 childd
A
B C D
E F G
空链域 n(k-1)+1个结点结构 data firstChild nextSibling
A
B C D
E F G
空链域 n+1个第二种解决方案 树的左子女 -右兄弟表示
（二叉链表表示）
B
C
D
G
F
E
A?
typedef char TreeData;
typedef struct node {
TreeData data;
struct node *firstChild,*nextSibling;
} TreeNode;
typedef TreeNode * Tree;
用左子女 -右兄弟表示实现的树定义
T1 T2 T3
T1 T2 T3
A F H
B C D G I J
E K
A F
B
C
D
E
G
H
I
K J
A
B
C
E
D
H
I
K J
F
G3 棵树的森林各棵树的二叉树表示森林的二叉树表示
森林与二叉树的转换树的二叉树表示,
树的遍历
深度优先遍历
先根次序遍历
后根次序遍历
A
B C D
E F G
A
B
CE
D
G
F
深度优先遍历
当树非空时
访问根结点
依次先根遍历根的各棵子树
树先根遍历 ABEFCDG
对应二叉树前序遍历 ABEFCDG
树的先根遍历结果与其对应二叉树表示的前序遍历结果相同
树的先根遍历可以借助对应二叉树的前序遍历算法实现
A
B
CE
D
G
F
树的 先根次序 遍历
树的 后根次序 遍历,
当树非空时
依次后根遍历根的各棵子树
访问根结点
树后根遍历 EFBCGDA
对应二叉树中序遍历 EFBCGDA
树的后根遍历结果与其对应二叉树表示的中序遍历结果相同
树的后根遍历可以借助对应二叉树的中序遍历算法实现
A
B
CE
D
G
F
二叉树的计数
由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。
例,前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG },构造二叉树过程如下：
HBDF EKCG
A
EKCG
A
B
H DF
KCG
EKCG
A
B
H DF
EKCG
A
B
H F
D
E
A
B
H F
D
E
A
B
H F
D
C
K G
如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。
6
1
2
3 4
5
7
8 9
6
1
2
3 7
5
8
4 9
固定前序排列,选择所有可能的中序排列,
可以构造多少种不同的二叉树？
例如,有 3 个数据 { 1,2,3 }，可得 5 种不同的二叉树。它们的前序排列均为 123，中序序列可能是 321,231,213,132,123.
1
2
3
1
2
3
1
2 3
1
2
3
1
2
3
具有 n个结点不同形态的树的数目和具有
n-1个结点互不相似的二叉树的数目相同。
有 0个,1个,2个,3个结点的不同二叉树如下
b0 =1 b1 =1 b2 =2
b3 =5
b4 =14
!!
)!(2
1
1
1
1
2 nn
n
nn
b C n nn
计算具有 n 个结点的不同二叉树的棵数最终结果：
bi bn-i-1
1
1
0
1
n
i
inin bbb
霍夫曼树 (Huffman Tree)
路径长度 (Path Length)
两个结点之间的路径长度 PL 是连接两结点的路径上的分支数。
树的外部路径长度是各叶结点 (外结点 )到根结点的路径长度之和 EPL。
树的内部路径长度是各非叶结点 (内结点 )
到根结点的路径长度之和 IPL。
树的路径长度 PL = EPL + IPL
1
2 3
4 5 6 7
8
2 3
4 5
6 7
8树的外部路径长度
EPL = 3*1+2*3 = 9
树的外部路径长度
EPL = 1*1+2*1+3*1+4*1 = 10
1
带权路径长度 (Weighted Path Length,WPL)
二叉树的带权 (外部 ) 路径长度是树的各叶结点所带的权值 wi 与该结点到根的路径长度 li 的乘积的和。
1
0
n
i
ii lwW P L
WPL = 2*2+ WPL = 2*1+ WPL = 7*1+
4*2+5*2+ 4*2+5*3+ 5*2+2*3+
7*2 = 36 7*3 = 46 4*3 = 35
2
2
24
4
45 5
5
7
7
7
带权 (外部 )路径长度达到最小霍夫曼树
带权路径长度达到最小的二叉树即为霍夫曼树。
在霍夫曼树中，权值大的结点离根最近。
(1) 由给定的 n 个权值 {w0,w1,w2,…,w n-1}，
构造具有 n 棵扩充二叉树的森林 F = { T0,T1,
T2,…,T n-1 }，其中每棵扩充二叉树 Ti 只有一个带权值 wi 的根结点,其左、右子树均为空。
霍夫曼 算法
(2) 重复以下步骤,直到 F 中仅剩下一棵树为止：
① 在 F 中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
② 在 F 中删去这两棵二叉树。
③ 把新的二叉树加入 F。
F,{7} {5} {2} {4} F,{7} {5} {6}
F,{7} {11}
7 5 2 4
初始 合并 {2} {4}
7 5
2 4
6
F,{18} 11
7 5
2 4
6
合并 {5} {6}
5
合并 {7} {11} 2
7
4
6
11
18
举例霍夫曼树的构造过程
5 27 4
Weight parent leftChild rightChild
7 -1 -1 -1
5 -1 -1 -1
2 -1 -1 -1
4 -1 -1 -1
-1 -1 -1
-1 -1 -1
-1 -1 -1
0
1
2
3
4
5
6
上例存储结构初 态
5
2
7
4
6
Weight parent leftChild rightChild
7 -1 -1 -1
5 -1 -1 -1
2 -1 -1 -1
4 -1 -1 -1
6 -1 -1 -1
-1 -1 -1
-1 -1 -1
0
1
2
3
4
5
6
p1
p2
4
4
2 3i
过 程
5
2
7
4
6
11
Weight parent leftChild rightChild
7 -1 -1 -1
5 -1 -1 -1
2 4 -1 -1
4 4 -1 -1
6 -1 2 3
11 -1 -1 -1
-1 -1 -1
0
1
2
3
4
5
6
p1
p2
5
5
1 4i
5
2
7
4
6
11
Weight parent leftChild rightChild
7 -1 -1 -1
5 5 -1 -1
2 4 -1 -1
4 4 -1 -1
6 5 2 3
11 -1 1 4
18 -1 -1 -1
0
1
2
3
4
5
6
p1
p2
6
6
0 5i
18
终 态
const int n = 20;//叶结点数
const int m = 2*n -1;//结点数
typedef struct {
float weight;
int parent,leftChild,rightChild;
} HTNode;
typedef HTNode HuffmanTree[m];
霍夫曼树的定义建立霍夫曼树的算法
void CreateHuffmanTree ( HuffmanTree T,
float fr[ ] ) {
for ( int i = 0; i < n; i++ )
T[i].weight = fr[i];
for ( i = 0; i < m; i++ ) {
T[i].parent = -1;
T[i].leftChild = -1;
T[i].rightChild = -1;
}
for ( i = n; i < m; i++ ) {
int min1 = min2 = MaxNum;
int pos1,pos2;
for ( int j = 0; j < i; j++ )
if ( T[j].parent == -1 )
if ( T[j].weight < min1 )
{ pos2 = pos1; min2 = min1;
pos1 = j; min1 = T[j].weight;
}
else if ( T[j].weight < min2 )
{ pos2 = j; min2 = T[j].weight; }
T[i].leftChild = pos1;
T[i].rightChild = pos2;
T[i].weight =
T[pos1].weight + T[pos2].weight;
T[pos1].parent = T[pos2].parent = i;
}
}
最佳判定树考试成绩分布表
[ 0,6 0 ) [ 6 0,7 0 ) [ 7 0,8 0 ) [ 8 0,9 0 ) [ 9 0,1 0 0 )
不及格 及格 中 良 优
0,1 0 0,15 0,2 5 0,3 5 0,1 5
判定树不及格及格中良 优
<60?
<70?
<80?
<90?
0.10
0.15
0.25
0.35 0.15
≥
≥
≥
≥<
<
<
<
WPL = 0.10*1+0.15*2+0.25*3+0.35*4+0.15*4
= 3.15
最佳判定树不及格 及格中 良 优<60?
<70?
<80?
<90?
0.10 0.15
0.25 0.35 0.15
≥
≥
≥
≥<
<
<
<
WPL = 0.10*3+0.15*3+0.25*2+0.35*2+0.15*2
= 0.3+0.45+0.5+0.7+0.3 = 2.25
霍夫曼编码主要用途是实现数据压缩。
设给出一段报文：
CAST CAST SAT AT A TASA
字符集合是 { C,A,S,T }，各个字符出现的频度 (次数 )是 W＝ { 2,7,4,5 }。
若给每个字符以等长编码
A,00 T,10 C,01 S,11
则总编码长度为 ( 2+7+4+5 ) * 2 = 36,
若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。
各字符出现概率为 { 2/18,7/18,4/18,5/18 },
化整为 { 2,7,4,5 }。以它们为各叶结点上的权值,建立霍夫曼树。 左分支赋 0，右分支赋
1，得霍夫曼编码 (变长编码 )。
7 2 5 4
0 1
00 11
A C T S
A,0 T,10 C,110 S,111
它的总 编码长度,7*1+5*2+( 2+4 )*3 = 35。
比等长编码的情形要短。
总编码长度正好等于霍夫曼树的带权路径长度 WPL。
霍夫曼编码是一种 无前缀编码 。解码时不会混淆。
霍夫曼编码树
0
0
0
1
1
1
2 4
5
7
