? 树和森林的概念
? 二叉树
? 二叉树遍历
? 二叉树的计数
? 堆
? 树与森林
? 霍夫曼树
树和森林的概念
树的定义
树是由 n (n ? 0) 个结点组成的有限集合。
如果 n = 0，称为空树；如果 n > 0，则
?有一个特定的称之为 根 (root)的结点，
它只有直接后继，但没有直接前驱；
?除根以外的其它结点划分为 m (m ? 0)
个 互不相交的有限集合 T0,T1,…,Tm-1，每
个集合又是一棵树, 并且称之为根的 子树 。
树的特点
? 每棵子树的根结点有且仅有一个直接前
驱，但可以有 0个或多个直接后继。
0层
1层
3层
2层
height
= 3
A
C
G
B D
E F
K L
H
M
I J
0层
1层
3层
2层
height
= 3
A
C
G
B D
E F
K L
H
M
I J
?结点
?结点的度
?分支结点
?叶结点
?子女
?双亲
?兄弟
?祖先
?子孙
?结点层次
?树的度
?树 高度
?森林
二叉树 (Binary Tree)
二叉树的定义
二叉树的五种不同形态
一棵二叉树是结点的一个有限集合，
该集合或者为空，或者是由一个根结点加
上两棵分别称为左子树和右子树的、互不
相交的二叉树组成。
L LR R
性质 1 若二叉树的层次从 0开始,则在二叉
树的第 i 层最多有 2i 个结点。 (i? 0)
[证明用数学归纳法 ]
性质 2 高度为 h 的二叉树最多有 2h+1-1个
结点。 (h? -1)
[证明用求等比级数前 k项和的公式 ]
20 + 21 + 22 + … + 2 h = 2h+1-1
二叉树的性质
性质 3 对任何一棵二叉树,如果其 叶结点
有 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)
定义 2 完全二叉树 (Complete Binary Tree)
若设二叉树的高度为 h，则共有 h+1层。除
第 h 层外，其它各层 (0 ? h-1) 的结点数都
达到最大个数，第 h 层从右向左连续缺若干
结点，这就是完全二叉树。
性质 4 具有 n (n ? 0) 个结点的完全二叉树
的高度为 ?log2(n+1)?-1
证明,设完全二叉树的高度为 h，则有
2h - 1 < n ? 2h+1 - 1
变形 2h < n+1 ? 2h+1
取对数 h < log2(n+1) ? h+1
因此有 ?log2(n+1)?= h+1
h = ?log2(n+1)?-1
上面 h层 结点数 包括 第 h层 的最大结点数
性质 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
0
1 2
3
7
4 5 6
8 9
完全二叉树 一般二叉树
的 顺序表示 的 顺序表示
二叉树的顺序表示
0
0 1 2 3 4 5 6 7 8 9
9
0 1 2 3 4 5 6 7 8 9
1
3
7 8 9
4 5 6
2
0
1 2
543
6 7 8
二叉树的链表表示
leftChild data rightChild
data
leftChild rightChild
二叉链表
二叉树的链表表示
leftChild data parent rightChild
parent
data
leftChild rightChild
三叉链表
二叉树链表表示的示例
?
? ?
? ? ? ? ? ? ? ?
??
??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;
//树定义，代表树的根指针
二叉树的定义
二叉树遍历
树的遍历就是按某种次序访问树中的结
点，要求每个结点访问一次且仅访问一次。
设 访问根结点 记作 V
遍历根的左子树 记作 L
遍历根的右子树 记作 R
则可能的遍历次序有
前序 VLR 镜像 VRL
中序 LVR 镜像 RVL
后序 LRV 镜像 RLV
中序遍历二叉树算法的框架是：
? 若二叉树为空，则空操作；
? 否则
? 中序遍历左子树 (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”表示字符序列或正整数序列空结点。
二叉树建立的递归算法
如图所示的二叉树的前序遍历顺序为
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。 fin是输入流对象
TreeData item;
ifstream fin (filename,ios::in | ios::nocreate );
//打开文件
if ( !fin ) {
cerr <<,文件未发现 !” << endl; exit (1);
}
Crt_BinTree ( ifstream& fin,Tree );
fin.close ( ); //关闭文件
}
删除二叉树的递归算法
void destroy ( BinTreeNode *T ) {
if ( T != NULL ) {
destroy ( T->leftChild );
destroy ( T->rightChild );
delete T;
}
}
int Count ( BinTreeNode *T ) {
if ( T == NULL ) return 0;
else return 1 + Count ( T->leftChild )
+ Count ( T->rightChild );
}
计算二叉树结点个数的递归算法
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;
}
求二叉树高度的递归算法
计算二叉树含 x 结点所在层次 k
void level ( BinTree T,TreeData x,int h,int &k )
{
if ( T == NULL ) k = -1;
else if ( T->data == x ) k = h;
else { level ( T->leftChild,x,h+1,k);
if ( k == -1 )
level ( T->rightChild,x,h+1,k);
}
}
主程序调用 level ( T,x,0,k );
将一棵以二叉链表存储的二叉树按
顺序方式存储到一维数组中
void Link2Array ( BinTreeNode * T,
TreeData C[ ],int k ) {
if ( T != NULL ) {
C[k] = T->data;
Link2Array ( T->leftChild,C,2*k+1 );
Link2Array ( T->rightChild,C,2*k+2 );
}
}
主程序调用方式 create ( T,C,0 );
从完全二叉树的顺序表示
转换为二叉链表表示
void Array2Link ( TreeData T[ ],int n,int i,
BinTreeNode *& ptr ) {
//将用 T[n]顺序存储的完全二叉树,以 i 为根
//的子树转换成用二叉链表表示的以 ptr 为
//根的完全二叉树。利用引用型参数 ptr 将
//形参的值带回实参。
if ( i >= n ) ptr = NULL;
else {
ptr = new BinTreeNode; //建立根结点
ptr->data = T[i];
Array2Link (T,n,2*i+1,ptr->leftChild);
Array2Link (T,n,2*i+2,ptr->rightChild);
}
}
利用栈的前序遍历的非递归算法
a
b c
d e
c
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
b
a a
d
a a
左空 退栈
访问
左空 退栈
访问
退栈
访问
左空
e
c
退栈访问
c c
右空 退栈访问 栈空结束
void InOrder ( BinTree T ) {
stack S; InitStack( &S ); //递归工作栈
BinTreeNode *p = T; //初始化
do {
while ( p != NULL )
{ Push(&S,p); p = p->leftChild; }
if ( !StackEmpty(&S) ) { //栈非空
Pop(&S,p); //退栈
cout << p->data << endl; //访问根
p = p->rightChild; //向右链走
}
} while ( p != NULL || !StackEmpty(&S) );
}
利用栈的后序遍历的非递归算法
后序遍历时使用的栈的结点定义
typedef struct {
BinTreeNode *ptr; //结点指针
enum tag{ L,R }; //该结点退栈标记
} StackNode;
根结点的
tag = L，表示从左子树退出,访问右子树。
tag = R,表示 从右子树退出,访问根。
ptr tag{L,R}
a
b c
d e
aL
bL
aL
bR
aL
dL
bR
aL
dR
bR
aL
bR
aL aL aR
eL
cL
aR
eR
cL
aR
cL
aR
cR
aR aR
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 );
}
}
}
二叉树的计数
由二叉树的前序序列和中序序列可唯一
地确定一棵二叉树。
例,前序序列 { ABHFDECKG } 和中序序
列 { HBDFAEKCG },构造二叉树过程如下：
HBDF EKCG
A
EKCG
A
B
H DF
KCG
前序序列 { ABHFDECKG }
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,中
序序列可能是 123,132,213,231,321。
1
2
3
1
2
3
1
2 3
1
2
3
1
2
3
有 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 个结点的不同二叉树的棵数
Catalan函数
bi bn-i-1
1
?
?
?
????
1
0
1
n
i
inin bbb
堆 ( Heap )
设有一个关键字集合，按完全二叉树的
顺序存储方式存放在一个一维数组中。对
它们从根开始，自顶向下，同一层自左向
右 从 0开始 连续编号。若满足
Ki ? K2i+1 && Ki? K2i+2
或 Ki ? K2i+1 && Ki? K2i+2,
则称该关键字集合构成一个堆。
前者成为最小堆，后者称为最大堆。
完全二叉树
顺序表示
Ki ? K2i+1 &&
Ki? K2i+2
完全二叉树
顺序表示
Ki ? K2i+1 &&
Ki? K2i+2
堆的定义
09
09
87
87
78
7845 45
65
65 31
3153 23
23
53
17
17
#define MaxHeapSize 100;
typedef int HeapData;
typedef struct {
HeapData data[MaxHeapSize];
//存放最小堆元素的数组
int CSize; //最小堆当前元素个数
} MinHeap;
最小堆的定义
void InitHeap ( MinHeap *H )
{ H->CSize = 0; }
//堆初始化，置空堆
int HeapEmpty ( MinHeap *H )
{ return H->CSize == 0; }
//判堆空否
int HeapFull ( MinHeap *H )
{ return H->CSize == MaxHeapSize; }
//判堆满否
自下向上逐步调整为最小堆
将一组用数组存放的任意数据调整成堆
53 53
17 1778 78
09
23 45 65 87
i
09
23
45 65 87
CPos = i = 3 CPos = i = 2
i
53 53
17
1778 7809
23
45
65
87
i
09
23
45
65
87
CPos = i = 1
i
53
53
17 1778 78
09
23
45
65
87
i
09
23
45
65
87
CPos = i = 0
i
09
53
53
17 17
78 78
09
23
45
65
87
i
09
23 45
65
87i17
void Crt_MinHeap ( MinHeap *H,
HeapData arr[ ],int n ) {
//根据给定数组中的数据和大小,建立堆
for ( int i = 0; i < n; i++ ) H->data[i] = arr[i];
H->CSize = n; //数组传送及当前堆大小
int CPos = (H->CSize-2)/2; //最后分支结点
while ( CPos >= 0 ) { //从下到上逐步扩大堆
FilterDown ( &H,CPos,H->CSize-1 );
CPos--;
}
}
堆的建立
void FilterDown ( MinHeap *H,int start,
int EndOfHeap ) {
int i = start,j = 2*i+1; // j 是 i 的左子女
HeapData temp = H->data[i];
while ( j <= EndOfHeap ) {
if ( j < EndOfHeap && //两子女中选小者
H->data[j] > H->data[j+1] ) j++;
if ( temp <= H->data[j] ) break;
else { H->data[i] = H->data[j];
i = j; j = 2*j+1; } //向下滑动
}
最小堆的向下调整算法
H->data[i] = temp;
}
53
17 17
78 78
09
23 45
65
87
i
09
23 45
65
87
j
11
在堆中插入新元素 11
53
j
11
23
i
最小堆的插入和向上调整
53
17 11
78 78
09
45
65
87
09
17 45
65
87
j
11
53 23
i
23
17
j
i
最小堆的插入算法
int Insert ( MinHeap *H,HeapData x ) {
//在堆中插入新元素 x
if ( H->CSize == MaxHeapSize ) //堆满
{ cerr << "堆已满 " << endl; return 0; }
H->data[H->CSize] = x; //插在表尾
FilterUp ( &H,H->Csize ); //向上调整
H->CSize++; //堆元素增一
return 1;
}
最小堆的向上调整算法
void FilterUp ( MinHeap *H,int start ) {
//从 start 开始,向上直到 0,调整堆
int j = start,i = (j-1)/2; // i 是 j 的双亲
HeapData temp = H->data[j];
while ( j > 0 ) {
if ( H->data[i] <= temp ) break;
else { H->data[j] = H->data[i];
j = i; i = (i -1)/2;}
}
H->data[j] = temp;
}
53
17 17
78 78
09
23 45
65
87
31
23 45
65
87
31
用最后
一个元素填补
53
最小堆的删除和向下调整
删除
53
17 17
78 78
31
23 45
65
87
17
23 45
65
87
j
53
i向下调整
j 31
i
53
23 23
78 78
17
23 45
65
87
17
31 45
65
87j
53
31
i
向下调整
i
最小堆的删除算法
int RemoveMin ( MinHeap *H,HeapData &x ) {
if ( ! H->CSize )
{ cout <<, 堆已空 " << endl; return 0; }
x = H->data[0]; //最小元素出队列
H->data[0] = H->data[H->CSize-1];
H->CSize--; //用最后元素填补
FilterDown ( &H,0,H->CSize-1 ); //调整
return 1;
}
树的存储表示
? 双亲表示
树与森林
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
???
?????? ???
???
空链域 2n+1个
第二种解决方案 树的左子女 -右兄弟表示
data firstChild nextSibling
A
B C D
E F G
A
B
C
D
G
F
E
空链域 n+1个 ?
? ?
? ?
? ?
?
typedef char TreeData;
typedef struct node {
TreeData data;
struct node *firstChild,*nextSibling;
} TreeNode;
typedef TreeNode * Tree;
用左子女 -右兄弟表示实现的树定义
TreeNode *Parent ( Tree T,TreeNode * p ) {
//在树中找结点 *p的双亲
if ( T == NULL || T == p ) return NULL;
//空树或 *p为根,返回 NULL，无双亲
return FindParent ( T,p ); //从 T找 *p双亲
}
TreeNode * FindParent (Tree T,TreeNode *p) {
//在根为 T 的树中找 *p 的双亲
TreeNode *q = T->firstChild,*s;
while ( q != NULL && q != p ) {
//循根的长子的兄弟链,递归在子树中搜索
if (( s = FindParent ( q,p ) ) != NULL )
return s;
q = q->nextSibling;
}
if ( q != NULL && q == p ) return T;
else return NULL; //未找到双亲
}
TreeNode * FirstChild ( Tree T,TreeNode *p ) {
//在树 T中找当前结点 *p的第一个子女
if ( p != NULL ) return p->firstChild;
else return NULL;
}
TreeNode * NextSibling (Tree T,TreeNode *p) {
//在树 T中找结点 *p的兄弟
if ( p != NULL ) return p->nextSibling;
else return NULL;
}
T1 T2 T3A F H
T1 T2 T3A
B C D G I J
E K
F
B
C
D
E
G
H
I
K J
A
B
C
E
D
H
I
K J
F
G3 棵树的森林
各棵树的二叉树表示
森林的二叉树表示
森林与二叉树的对应关系
树的二叉树表示
树的遍历
? 深度优先遍历
? 先根次序遍历
? 后根次序遍历
? 广度优先遍历 AB
CE
D
A
B C D
E F G G
F
树的 先根次序 遍历
? 当树非空时
? 访问根结点
? 依次先根遍历根的各棵
子树
? 树先根遍历 ABEFCDG
? 对应二叉树前序遍历 ABEFCDG
? 树的先根遍历结果与其对应二叉树
表示的前序遍历结果相同
? 树的先根遍历可以借助对应二叉树的前
序遍历算法实现
A
B
CE
D
G
F
树的 后根次序 遍历
? 当树非空时
? 依次后根遍历根的各棵
子树
? 访问根结点
? 树后根遍历 EFBCGDA
? 对应二叉树中序遍历 EFBCGDA
? 树的后根遍历结果与其对应二叉树
表示的中序遍历结果相同
? 树的后根遍历可以借助对应二叉树的中序
遍历算法实现
A
B
CE
D
G
F
按广度优先次序遍历树的结果
ABCDEFG
广度优先遍历算法
void LevelOrder ( Tree T ) {
//分层遍历树,算法用到一个队列 。
Queue Q; InitQueue (&Q);
TreeNode *p = T;
if ( T != NULL ) { //树不空
EnQueue (&Q,p);
树的广度优先 (层次次序 )遍历
A
B
CE
D
G
F
while (! QueueEmpty (&Q) ) {
DeQueue (&Q,p); //队列中取一个
cout << p->data << endl; //访问之
p = p->firstChild ;
//待访问结点的子女结点进队列
while ( p != NULL ) {
EnQueue (&Q,p);
p = p->nextSibling;
}
}
}
}
满 k 叉树的性质
一棵高度为 h 的满 k 叉树有如下性质,
第 h层上的结点都是叶结点,其余各层上每
个结点都有 k 棵非空子树,如果按层次自顶
向下,同一层自左向右,顺序从 1 开始对全部
结点进行编号,
? 第 i 层的结点个数是 ki 个 ( i = 0,1,…,h )
? 编号为 i 的结点的父结点 (若存在 )的编号是
??
?
??
? ??
k
2ki
1
2
10 11 12 13 14 15 16 17 18 19 20 216 7 8 9
3 4 5
2level
1level
0level
? 编号为 i 的结点的第 m 个孩子结点 (若存在 )
的编号是 (i-1)*k+m+1
? 编号为 i 的结点有右兄弟的条件是
( i-1 ) % k ? 0
有右兄弟时，其右兄弟结点的编号是 i+1
? 设满 k 叉树的结点个数为 n，又设满 k 叉树
的高度为 h (根在第 0层 ),则
n = k0 + k1 + ? + kh = (kh+1-1) / (k-1)
则 kh+1 = (k-1)*n + 1
取对数 h+1 = logk( (k-1)*n+1))
h = logk( (k-1)*n+1)) - 1
霍夫曼树 (Huffman Tree)
路径长度 (Path Length)
两个结点之间的路径长度 PL 是连接两
结点的路径上的分支数。
树的外部路径长度是各叶结点 (外结点 )到
根结点的路径长度之和 EPL。
树的内部路径长度是各非叶结点 (内结点 )
到根结点的路径长度之和 IPL。
树的路径长度 PL = EPL + IPL
1 1
2 23 3
4 45 56
6
7
78
8树的外部路径长度
EPL = 3*1+2*3 = 9 树的外部路径长度
EPL = 1*1+2*1+3*1+4*1 = 10
n 个结点的二叉树的路径长度不小于
下述数列前 n 项的和，即
其路径长度最小者为
? ??
?
?
??
1
0
2 1)(l o g
n
i
iPL
带权路径长度 (Weighted Path Length,WPL)
扩充二叉树的带权 (外部 ) 路径长度是树的各
叶结点所带的权值 wi 与该结点到根的路径长
度 li 的乘积的和。
?
?
?
??
1
0
n
i
ii lwW P L
? ??
?
?
??
1
0
2 1)(l o g
n
i
iPL
??????????? 332222110
具有不同带权 (外部 )路径长度的扩充二叉树
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,…,wn-1}，
构造具有 n 棵扩充二叉树的森林 F = { T0,T1,
T2,…,Tn-1 }，其中每棵扩充二叉树 Ti 只有一
个带权值 wi 的根结点,其左、右子树均为空。
(2) 重复以下步骤,直到 F 中仅剩下一棵
树为止：
① 在 F 中选取两棵 根结点的权值最小 的
扩充二叉树,做为左、右子树 构造一棵新
的二叉树。置新的二叉树的 根结点的权值
为其左、右子树上根结点的权值之和 。
② 在 F 中删去这两棵二叉树。
③ 把新的二叉树加入 F。
霍夫曼树的构造过程
F, {7} {5} {2} {4} F, {7} {5} {6}
7 5 2 4
初始
合并 {2} {4}
F, {7} {11}
7 5
2 4
7 5
2 4
6
6
11
合并 {5} {6}
F, {18}
5
合并 {5} {6} 2
7
4
6
11
18
const int n = 20;
const int m = 2*n -1;
typedef struct {
float weight;
int parent,leftChild,rightChild;
} HTNode;
typedef HTNode HuffmanTree[m];
霍夫曼树的定义
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
建立霍夫曼树的算法
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)的结点，
它只有直接后继，但没有直接前驱；
?除根以外的其它结点划分为 m (m ? 0)
个 互不相交的有限集合 T0,T1,…,Tm-1，每
个集合又是一棵树, 并且称之为根的 子树 。
树的特点
? 每棵子树的根结点有且仅有一个直接前
驱，但可以有 0个或多个直接后继。
0层
1层
3层
2层
height
= 3
A
C
G
B D
E F
K L
H
M
I J
0层
1层
3层
2层
height
= 3
A
C
G
B D
E F
K L
H
M
I J
?结点
?结点的度
?分支结点
?叶结点
?子女
?双亲
?兄弟
?祖先
?子孙
?结点层次
?树的度
?树 高度
?森林
二叉树 (Binary Tree)
二叉树的定义
二叉树的五种不同形态
一棵二叉树是结点的一个有限集合，
该集合或者为空，或者是由一个根结点加
上两棵分别称为左子树和右子树的、互不
相交的二叉树组成。
L LR R
性质 1 若二叉树的层次从 0开始,则在二叉
树的第 i 层最多有 2i 个结点。 (i? 0)
[证明用数学归纳法 ]
性质 2 高度为 h 的二叉树最多有 2h+1-1个
结点。 (h? -1)
[证明用求等比级数前 k项和的公式 ]
20 + 21 + 22 + … + 2 h = 2h+1-1
二叉树的性质
性质 3 对任何一棵二叉树,如果其 叶结点
有 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)
定义 2 完全二叉树 (Complete Binary Tree)
若设二叉树的高度为 h，则共有 h+1层。除
第 h 层外，其它各层 (0 ? h-1) 的结点数都
达到最大个数，第 h 层从右向左连续缺若干
结点，这就是完全二叉树。
性质 4 具有 n (n ? 0) 个结点的完全二叉树
的高度为 ?log2(n+1)?-1
证明,设完全二叉树的高度为 h，则有
2h - 1 < n ? 2h+1 - 1
变形 2h < n+1 ? 2h+1
取对数 h < log2(n+1) ? h+1
因此有 ?log2(n+1)?= h+1
h = ?log2(n+1)?-1
上面 h层 结点数 包括 第 h层 的最大结点数
性质 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
0
1 2
3
7
4 5 6
8 9
完全二叉树 一般二叉树
的 顺序表示 的 顺序表示
二叉树的顺序表示
0
0 1 2 3 4 5 6 7 8 9
9
0 1 2 3 4 5 6 7 8 9
1
3
7 8 9
4 5 6
2
0
1 2
543
6 7 8
二叉树的链表表示
leftChild data rightChild
data
leftChild rightChild
二叉链表
二叉树的链表表示
leftChild data parent rightChild
parent
data
leftChild rightChild
三叉链表
二叉树链表表示的示例
?
? ?
? ? ? ? ? ? ? ?
??
??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;
//树定义，代表树的根指针
二叉树的定义
二叉树遍历
树的遍历就是按某种次序访问树中的结
点，要求每个结点访问一次且仅访问一次。
设 访问根结点 记作 V
遍历根的左子树 记作 L
遍历根的右子树 记作 R
则可能的遍历次序有
前序 VLR 镜像 VRL
中序 LVR 镜像 RVL
后序 LRV 镜像 RLV
中序遍历二叉树算法的框架是：
? 若二叉树为空，则空操作；
? 否则
? 中序遍历左子树 (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”表示字符序列或正整数序列空结点。
二叉树建立的递归算法
如图所示的二叉树的前序遍历顺序为
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。 fin是输入流对象
TreeData item;
ifstream fin (filename,ios::in | ios::nocreate );
//打开文件
if ( !fin ) {
cerr <<,文件未发现 !” << endl; exit (1);
}
Crt_BinTree ( ifstream& fin,Tree );
fin.close ( ); //关闭文件
}
删除二叉树的递归算法
void destroy ( BinTreeNode *T ) {
if ( T != NULL ) {
destroy ( T->leftChild );
destroy ( T->rightChild );
delete T;
}
}
int Count ( BinTreeNode *T ) {
if ( T == NULL ) return 0;
else return 1 + Count ( T->leftChild )
+ Count ( T->rightChild );
}
计算二叉树结点个数的递归算法
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;
}
求二叉树高度的递归算法
计算二叉树含 x 结点所在层次 k
void level ( BinTree T,TreeData x,int h,int &k )
{
if ( T == NULL ) k = -1;
else if ( T->data == x ) k = h;
else { level ( T->leftChild,x,h+1,k);
if ( k == -1 )
level ( T->rightChild,x,h+1,k);
}
}
主程序调用 level ( T,x,0,k );
将一棵以二叉链表存储的二叉树按
顺序方式存储到一维数组中
void Link2Array ( BinTreeNode * T,
TreeData C[ ],int k ) {
if ( T != NULL ) {
C[k] = T->data;
Link2Array ( T->leftChild,C,2*k+1 );
Link2Array ( T->rightChild,C,2*k+2 );
}
}
主程序调用方式 create ( T,C,0 );
从完全二叉树的顺序表示
转换为二叉链表表示
void Array2Link ( TreeData T[ ],int n,int i,
BinTreeNode *& ptr ) {
//将用 T[n]顺序存储的完全二叉树,以 i 为根
//的子树转换成用二叉链表表示的以 ptr 为
//根的完全二叉树。利用引用型参数 ptr 将
//形参的值带回实参。
if ( i >= n ) ptr = NULL;
else {
ptr = new BinTreeNode; //建立根结点
ptr->data = T[i];
Array2Link (T,n,2*i+1,ptr->leftChild);
Array2Link (T,n,2*i+2,ptr->rightChild);
}
}
利用栈的前序遍历的非递归算法
a
b c
d e
c
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
b
a a
d
a a
左空 退栈
访问
左空 退栈
访问
退栈
访问
左空
e
c
退栈访问
c c
右空 退栈访问 栈空结束
void InOrder ( BinTree T ) {
stack S; InitStack( &S ); //递归工作栈
BinTreeNode *p = T; //初始化
do {
while ( p != NULL )
{ Push(&S,p); p = p->leftChild; }
if ( !StackEmpty(&S) ) { //栈非空
Pop(&S,p); //退栈
cout << p->data << endl; //访问根
p = p->rightChild; //向右链走
}
} while ( p != NULL || !StackEmpty(&S) );
}
利用栈的后序遍历的非递归算法
后序遍历时使用的栈的结点定义
typedef struct {
BinTreeNode *ptr; //结点指针
enum tag{ L,R }; //该结点退栈标记
} StackNode;
根结点的
tag = L，表示从左子树退出,访问右子树。
tag = R,表示 从右子树退出,访问根。
ptr tag{L,R}
a
b c
d e
aL
bL
aL
bR
aL
dL
bR
aL
dR
bR
aL
bR
aL aL aR
eL
cL
aR
eR
cL
aR
cL
aR
cR
aR aR
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 );
}
}
}
二叉树的计数
由二叉树的前序序列和中序序列可唯一
地确定一棵二叉树。
例,前序序列 { ABHFDECKG } 和中序序
列 { HBDFAEKCG },构造二叉树过程如下：
HBDF EKCG
A
EKCG
A
B
H DF
KCG
前序序列 { ABHFDECKG }
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,中
序序列可能是 123,132,213,231,321。
1
2
3
1
2
3
1
2 3
1
2
3
1
2
3
有 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 个结点的不同二叉树的棵数
Catalan函数
bi bn-i-1
1
?
?
?
????
1
0
1
n
i
inin bbb
堆 ( Heap )
设有一个关键字集合，按完全二叉树的
顺序存储方式存放在一个一维数组中。对
它们从根开始，自顶向下，同一层自左向
右 从 0开始 连续编号。若满足
Ki ? K2i+1 && Ki? K2i+2
或 Ki ? K2i+1 && Ki? K2i+2,
则称该关键字集合构成一个堆。
前者成为最小堆，后者称为最大堆。
完全二叉树
顺序表示
Ki ? K2i+1 &&
Ki? K2i+2
完全二叉树
顺序表示
Ki ? K2i+1 &&
Ki? K2i+2
堆的定义
09
09
87
87
78
7845 45
65
65 31
3153 23
23
53
17
17
#define MaxHeapSize 100;
typedef int HeapData;
typedef struct {
HeapData data[MaxHeapSize];
//存放最小堆元素的数组
int CSize; //最小堆当前元素个数
} MinHeap;
最小堆的定义
void InitHeap ( MinHeap *H )
{ H->CSize = 0; }
//堆初始化，置空堆
int HeapEmpty ( MinHeap *H )
{ return H->CSize == 0; }
//判堆空否
int HeapFull ( MinHeap *H )
{ return H->CSize == MaxHeapSize; }
//判堆满否
自下向上逐步调整为最小堆
将一组用数组存放的任意数据调整成堆
53 53
17 1778 78
09
23 45 65 87
i
09
23
45 65 87
CPos = i = 3 CPos = i = 2
i
53 53
17
1778 7809
23
45
65
87
i
09
23
45
65
87
CPos = i = 1
i
53
53
17 1778 78
09
23
45
65
87
i
09
23
45
65
87
CPos = i = 0
i
09
53
53
17 17
78 78
09
23
45
65
87
i
09
23 45
65
87i17
void Crt_MinHeap ( MinHeap *H,
HeapData arr[ ],int n ) {
//根据给定数组中的数据和大小,建立堆
for ( int i = 0; i < n; i++ ) H->data[i] = arr[i];
H->CSize = n; //数组传送及当前堆大小
int CPos = (H->CSize-2)/2; //最后分支结点
while ( CPos >= 0 ) { //从下到上逐步扩大堆
FilterDown ( &H,CPos,H->CSize-1 );
CPos--;
}
}
堆的建立
void FilterDown ( MinHeap *H,int start,
int EndOfHeap ) {
int i = start,j = 2*i+1; // j 是 i 的左子女
HeapData temp = H->data[i];
while ( j <= EndOfHeap ) {
if ( j < EndOfHeap && //两子女中选小者
H->data[j] > H->data[j+1] ) j++;
if ( temp <= H->data[j] ) break;
else { H->data[i] = H->data[j];
i = j; j = 2*j+1; } //向下滑动
}
最小堆的向下调整算法
H->data[i] = temp;
}
53
17 17
78 78
09
23 45
65
87
i
09
23 45
65
87
j
11
在堆中插入新元素 11
53
j
11
23
i
最小堆的插入和向上调整
53
17 11
78 78
09
45
65
87
09
17 45
65
87
j
11
53 23
i
23
17
j
i
最小堆的插入算法
int Insert ( MinHeap *H,HeapData x ) {
//在堆中插入新元素 x
if ( H->CSize == MaxHeapSize ) //堆满
{ cerr << "堆已满 " << endl; return 0; }
H->data[H->CSize] = x; //插在表尾
FilterUp ( &H,H->Csize ); //向上调整
H->CSize++; //堆元素增一
return 1;
}
最小堆的向上调整算法
void FilterUp ( MinHeap *H,int start ) {
//从 start 开始,向上直到 0,调整堆
int j = start,i = (j-1)/2; // i 是 j 的双亲
HeapData temp = H->data[j];
while ( j > 0 ) {
if ( H->data[i] <= temp ) break;
else { H->data[j] = H->data[i];
j = i; i = (i -1)/2;}
}
H->data[j] = temp;
}
53
17 17
78 78
09
23 45
65
87
31
23 45
65
87
31
用最后
一个元素填补
53
最小堆的删除和向下调整
删除
53
17 17
78 78
31
23 45
65
87
17
23 45
65
87
j
53
i向下调整
j 31
i
53
23 23
78 78
17
23 45
65
87
17
31 45
65
87j
53
31
i
向下调整
i
最小堆的删除算法
int RemoveMin ( MinHeap *H,HeapData &x ) {
if ( ! H->CSize )
{ cout <<, 堆已空 " << endl; return 0; }
x = H->data[0]; //最小元素出队列
H->data[0] = H->data[H->CSize-1];
H->CSize--; //用最后元素填补
FilterDown ( &H,0,H->CSize-1 ); //调整
return 1;
}
树的存储表示
? 双亲表示
树与森林
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
???
?????? ???
???
空链域 2n+1个
第二种解决方案 树的左子女 -右兄弟表示
data firstChild nextSibling
A
B C D
E F G
A
B
C
D
G
F
E
空链域 n+1个 ?
? ?
? ?
? ?
?
typedef char TreeData;
typedef struct node {
TreeData data;
struct node *firstChild,*nextSibling;
} TreeNode;
typedef TreeNode * Tree;
用左子女 -右兄弟表示实现的树定义
TreeNode *Parent ( Tree T,TreeNode * p ) {
//在树中找结点 *p的双亲
if ( T == NULL || T == p ) return NULL;
//空树或 *p为根,返回 NULL，无双亲
return FindParent ( T,p ); //从 T找 *p双亲
}
TreeNode * FindParent (Tree T,TreeNode *p) {
//在根为 T 的树中找 *p 的双亲
TreeNode *q = T->firstChild,*s;
while ( q != NULL && q != p ) {
//循根的长子的兄弟链,递归在子树中搜索
if (( s = FindParent ( q,p ) ) != NULL )
return s;
q = q->nextSibling;
}
if ( q != NULL && q == p ) return T;
else return NULL; //未找到双亲
}
TreeNode * FirstChild ( Tree T,TreeNode *p ) {
//在树 T中找当前结点 *p的第一个子女
if ( p != NULL ) return p->firstChild;
else return NULL;
}
TreeNode * NextSibling (Tree T,TreeNode *p) {
//在树 T中找结点 *p的兄弟
if ( p != NULL ) return p->nextSibling;
else return NULL;
}
T1 T2 T3A F H
T1 T2 T3A
B C D G I J
E K
F
B
C
D
E
G
H
I
K J
A
B
C
E
D
H
I
K J
F
G3 棵树的森林
各棵树的二叉树表示
森林的二叉树表示
森林与二叉树的对应关系
树的二叉树表示
树的遍历
? 深度优先遍历
? 先根次序遍历
? 后根次序遍历
? 广度优先遍历 AB
CE
D
A
B C D
E F G G
F
树的 先根次序 遍历
? 当树非空时
? 访问根结点
? 依次先根遍历根的各棵
子树
? 树先根遍历 ABEFCDG
? 对应二叉树前序遍历 ABEFCDG
? 树的先根遍历结果与其对应二叉树
表示的前序遍历结果相同
? 树的先根遍历可以借助对应二叉树的前
序遍历算法实现
A
B
CE
D
G
F
树的 后根次序 遍历
? 当树非空时
? 依次后根遍历根的各棵
子树
? 访问根结点
? 树后根遍历 EFBCGDA
? 对应二叉树中序遍历 EFBCGDA
? 树的后根遍历结果与其对应二叉树
表示的中序遍历结果相同
? 树的后根遍历可以借助对应二叉树的中序
遍历算法实现
A
B
CE
D
G
F
按广度优先次序遍历树的结果
ABCDEFG
广度优先遍历算法
void LevelOrder ( Tree T ) {
//分层遍历树,算法用到一个队列 。
Queue Q; InitQueue (&Q);
TreeNode *p = T;
if ( T != NULL ) { //树不空
EnQueue (&Q,p);
树的广度优先 (层次次序 )遍历
A
B
CE
D
G
F
while (! QueueEmpty (&Q) ) {
DeQueue (&Q,p); //队列中取一个
cout << p->data << endl; //访问之
p = p->firstChild ;
//待访问结点的子女结点进队列
while ( p != NULL ) {
EnQueue (&Q,p);
p = p->nextSibling;
}
}
}
}
满 k 叉树的性质
一棵高度为 h 的满 k 叉树有如下性质,
第 h层上的结点都是叶结点,其余各层上每
个结点都有 k 棵非空子树,如果按层次自顶
向下,同一层自左向右,顺序从 1 开始对全部
结点进行编号,
? 第 i 层的结点个数是 ki 个 ( i = 0,1,…,h )
? 编号为 i 的结点的父结点 (若存在 )的编号是
??
?
??
? ??
k
2ki
1
2
10 11 12 13 14 15 16 17 18 19 20 216 7 8 9
3 4 5
2level
1level
0level
? 编号为 i 的结点的第 m 个孩子结点 (若存在 )
的编号是 (i-1)*k+m+1
? 编号为 i 的结点有右兄弟的条件是
( i-1 ) % k ? 0
有右兄弟时，其右兄弟结点的编号是 i+1
? 设满 k 叉树的结点个数为 n，又设满 k 叉树
的高度为 h (根在第 0层 ),则
n = k0 + k1 + ? + kh = (kh+1-1) / (k-1)
则 kh+1 = (k-1)*n + 1
取对数 h+1 = logk( (k-1)*n+1))
h = logk( (k-1)*n+1)) - 1
霍夫曼树 (Huffman Tree)
路径长度 (Path Length)
两个结点之间的路径长度 PL 是连接两
结点的路径上的分支数。
树的外部路径长度是各叶结点 (外结点 )到
根结点的路径长度之和 EPL。
树的内部路径长度是各非叶结点 (内结点 )
到根结点的路径长度之和 IPL。
树的路径长度 PL = EPL + IPL
1 1
2 23 3
4 45 56
6
7
78
8树的外部路径长度
EPL = 3*1+2*3 = 9 树的外部路径长度
EPL = 1*1+2*1+3*1+4*1 = 10
n 个结点的二叉树的路径长度不小于
下述数列前 n 项的和，即
其路径长度最小者为
? ??
?
?
??
1
0
2 1)(l o g
n
i
iPL
带权路径长度 (Weighted Path Length,WPL)
扩充二叉树的带权 (外部 ) 路径长度是树的各
叶结点所带的权值 wi 与该结点到根的路径长
度 li 的乘积的和。
?
?
?
??
1
0
n
i
ii lwW P L
? ??
?
?
??
1
0
2 1)(l o g
n
i
iPL
??????????? 332222110
具有不同带权 (外部 )路径长度的扩充二叉树
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,…,wn-1}，
构造具有 n 棵扩充二叉树的森林 F = { T0,T1,
T2,…,Tn-1 }，其中每棵扩充二叉树 Ti 只有一
个带权值 wi 的根结点,其左、右子树均为空。
(2) 重复以下步骤,直到 F 中仅剩下一棵
树为止：
① 在 F 中选取两棵 根结点的权值最小 的
扩充二叉树,做为左、右子树 构造一棵新
的二叉树。置新的二叉树的 根结点的权值
为其左、右子树上根结点的权值之和 。
② 在 F 中删去这两棵二叉树。
③ 把新的二叉树加入 F。
霍夫曼树的构造过程
F, {7} {5} {2} {4} F, {7} {5} {6}
7 5 2 4
初始
合并 {2} {4}
F, {7} {11}
7 5
2 4
7 5
2 4
6
6
11
合并 {5} {6}
F, {18}
5
合并 {5} {6} 2
7
4
6
11
18
const int n = 20;
const int m = 2*n -1;
typedef struct {
float weight;
int parent,leftChild,rightChild;
} HTNode;
typedef HTNode HuffmanTree[m];
霍夫曼树的定义
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
建立霍夫曼树的算法
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
