1
第六章
第六章
树和二叉树
树和二叉树
基本概念
二叉树
二叉树的遍历和线索树
树
赫夫曼树
数
据
结
构
之
树
和
二
叉
树
2
只有根结点的树 一般树
层次
1
2
3
4
A
DCB
E
G
F
K L
H I J
M
A
2
数
据
结
构
之
树
和
二
叉
树
3
6.1 树的基本概念
? 树的基本概念
1. 树：是 n(n>=0)个结点的有限集。
n=0 称空树。
在任一非空树 (n>0)中 :
(1) 有且仅有一个称为根的结点；
(2) 其余结点可分为 m(m>=0)个互不相交的
有限集 T1， T2， ……， Tm，其中，每个集
合本身又是一棵树，并且称为根的子树。
2. 结点的度：树的结点所拥有的子树数；
3. 树的度：是树内各结点的度的最大值；
4. 度为 0的结点称为叶结点或终端结点
数
据
结
构
之
树
和
二
叉
树
4
5. 孩子结点、双亲结点、兄弟结点、堂兄弟
结点、祖先结点、子孙结点 ……
6. 结点的层次从根开始，根为第一层，根的
孩子为第二层；若某结点在第 L层，则其
子树的根就在第 L+1层。
7. 树的深度或高度：树中结点的最大层次。
8. 有序树：如果将树中结点的各子树看成是
从左至右有次序的；反之，则是无序树。
9. 森林：是 m棵互不相交的树的集合。
3
数
据
结
构
之
树
和
二
叉
树
5
例： 9个根结点的树： A是根，其他结点为三
个互不相交的有限集， T
1
= {B, E, F, G, I},
T
2
={C},T
3
={D,H},T
1-3
都是根 A的子树，而本
身又都是一棵树。
A
B C D
E F G
H
I
数
据
结
构
之
树
和
二
叉
树
6
? 树的表示法
? 分支图表示法
? 嵌套集合表示法
? 广义表表示法
(A(B(D),C))
A
B C
D
A
B
C
D
4
数
据
结
构
之
树
和
二
叉
树
7
? 树的基本操作
? 初始化操作INITIATE(T)：创建一棵空树。
? 求根函数ROOT(T)：求树T的根；ROOT(X)：求
结点x所在树的根。
? 求双亲函数PARENT(T,x)：在树T中求x的双亲。
? 求第i个孩子函数CHILD(T,x,i)：在树T中求
结点x的第i个孩子。
? 求兄弟函数：
?LSIBLING(T,x):在T中求x的左兄弟
?RSIBLING(T,x):在树T中求x的右兄弟
数
据
结
构
之
树
和
二
叉
树
8
? 建树函数CRT-TREE(x,F)：建立以结点x为
根，森林F为子树的树。
? 插入子树操作INS-CHILD(y,i,x)：将x作为
y的第i棵子树。
? 删除子树操作DEL-CHILD(x,i)：删除x的第
i棵子树。
? 遍历树操作TRAVERSE(T)：按顺序访问树T
中各个结点。
? 置空树操作CLEAR(T)：将树T置为空树。
5
数
据
结
构
之
树
和
二
叉
树
9
6. 2 二叉树
? 二叉树的概念
1、特点：每个结点至多只有两棵子树，左右子树次
序不能改变。
2、满二叉树：一个深度为 k，且有 2 -1个结点的二
叉树。特点：树中没有度为 1的结点。
3、完全二叉树：当树中每个结点都与相同深度的满
二叉树中编号从 1至 n的结点一一对应。
一
般
二
叉
树
满
二
叉
树
完
全
二
叉
树
k
数
据
结
构
之
树
和
二
叉
树
10
例：有5种类型的二叉树如下
A
A
B
A
B
A
B
C
空
只一个根结点
只有左子树
只有右子树 左右子树都有
6
数
据
结
构
之
树
和
二
叉
树
11
? 二叉树的性质
1、在二叉树的第 i 层上至多有 2 个结点 (i>=1);
2、深度为 k的二叉树至多有 2 -1个结点 (k>=1);
3、对任何一棵二叉树 T，如果其终端结点数为
n0，度为 2的结点数为 n2，则 n0=n2+1。
4、具有 n个结点的完全二叉树的深度为 :
?log2 n? +1
k
i-1
数
据
结
构
之
树
和
二
叉
树
12
5、如果对一棵有 n个结点的完全二叉树的结
点按层序编号（每层从左到右），则对任
一结点 i有
(1)可求得其双亲结点的序号为 ? i / 2 ? (i>1),i=1
时为二叉树的根结点 ,无双亲结点；
(2)如果存在的话，可求得其左右孩子结点的
序号 :Rchild(i)=2i+1;Lchild(i)=2i;
7
数
据
结
构
之
树
和
二
叉
树
13
? 二叉树的存储结构
1、顺序存储结构：用一组连续的
存储单元 Bt(1:n)存储二叉树的
数据元素。按完全二叉树的规
则对二叉树中的结点进行编号，
相应的空位也编上号，将二叉
树中编号为 i的结点的数据元
素存放在 Bt[i]中，若编号为 j
的结点为空，则 Bt[j]=0.
1 2 3 4 5 6 7 8 9
10
A B C 0 D E F 0 0 G
数
据
结
构
之
树
和
二
叉
树
14
?二叉树顺序存储的算法描述
? 初始化二叉树
#define Max_Size 100
typedef int TElemType;
typedef TElemType SqBT[Max_Size+1];
void InitBT(SqBT bt){//设置空树
int i;
for(i=1;i<=Max_Size;i++)
bt[i]=0;
}
8
数
据
结
构
之
树
和
二
叉
树
15
? 插入一个元素的算法
void Insert(SqBT bt){
int k ,done=1; TElemType e;
while (done) {
printf("\n Number,data\n");
scanf("%d,%d",&k,&e);
if(k<=Max_Size && bt[k/2]) {
bt[k]=e; done=0; }
else
printf("\n\tERROR, input again.");
}
}
数
据
结
构
之
树
和
二
叉
树
16
?创建二叉树的算法
void CreateBT(SqBT bt) {
int n,i,k;
TElemType e;
printf("\n Please Input n=");
scanf("%d",&n); bt[0]=1;
printf("\n Number,data\n");
for(i=1;i<=n;i++) Insert(bt);
}
9
数
据
结
构
之
树
和
二
叉
树
17
?前序遍历顺序二叉树算法
void PreBT(SqBT bt,int i){
if(i>=Max_Size||!bt[i]) return;
printf("%3d ",bt[i]);
PreBT(bt,2*i);
PreBT(bt,2*i+1);
}
数
据
结
构
之
树
和
二
叉
树
18
?中序打印二叉树的树形算法
void InBT(SqBT bt,int i,int k){ int j;
if(i>Max_Size||!bt[i]) return;
InBT(bt,2*i+1,k+10);
for(j=0;j<k;j++) printf(" ");
printf("%3d\n",bt[i]);
InBT(bt,2*i,k+10);
}
10
数
据
结
构
之
树
和
二
叉
树
19
?后序遍历顺序二叉树算法
void PostBT(SqBT bt,int i){
if(i>Max_Size||!bt[i]) return;
PostBT(bt,2*i);
PostBT(bt,2*i+1);
printf("%3d ",bt[i]);
}
数
据
结
构
之
树
和
二
叉
树
20
? 两棵顺序二叉树的比较算法
?形状和元素值完全相同
Status EqualSq(SqBT bt, SqBT bt1){
for(i=1;i<=Max_Size;i++)
if(bt[i]!=bt1[i]) return FALSE;
return TRUE;}
?形状相同
Status SampleSq(SqBT bt, SqBT bt1){
for(i=1;i<=Max_Size
&&((bt[i]&&bt1[i])||!(bt[i]||bt1[i]));i++);
if(i<Max_Size) return FALSE;
return TRUE;}
11
数
据
结
构
之
树
和
二
叉
树
21
? 形状比较的递归算法
Status Compare(SqBT bt,SqBT bt1,int i){
Status k;
if(bt[i] && bt1[i])
{if((k=Compare(bt, bt1, 2*i)))
k=Compare(bt, bt1, 2*i+1);}
else if(bt[i]==0 && bt1[i]==0) k=TRUE;
else k=FALSE;
return k;
}
数
据
结
构
之
树
和
二
叉
树
22
? 求元素 e在二叉树中层次
int FindNode(SqBT bt,int i,TElemType e){
static k; int k1;
k++;
if(i<Max_Size && bt[i] ){
if(e==bt[i]) k1=k;
else if(!(k1=FindNode(bt,2*i,e)))
k1=FindNode(bt,2*i+1,e); }
else k1=0;
k--; return k1; }
12
数
据
结
构
之
树
和
二
叉
树
23
? 求二叉树 T的深度
int DepthBT(SqBT bt,int i){
int k1,k2;
if(i>=Max_Size||!bt[i]) return 0;
k1=DepthBT(bt,2*i);
k2=DepthBT(bt,2*i+1);
return(1+((k1>=k2) ? k1 : k2));
}
数
据
结
构
之
树
和
二
叉
树
24
?前序打印树中所有结点的层次
void PrintNode(SqBT bt,int i){
static k;
k++;
if(i<Max_Size&&bt[i]){
printf("(%d,%3d) ",k,bt[i]);
PrintNode(bt,2*i);
PrintNode(bt,2*i+1);}
k- -; }
13
数
据
结
构
之
树
和
二
叉
树
25
?打印一维数组
void printSq(SqBT bt){
int i;
printf("\nSeqArray:");
for(i=1;i<=Max_Size;i++)
printf("%3d ",bt[i]);
}
数
据
结
构
之
树
和
二
叉
树
26
MenuList(){ /*显示菜单 */
printf("\n\t........................................");
printf("\n\t\t1. Insert or change One ElemData");
printf("\n\t\t2. Pre, In and Post Order Traverse");
printf("\n\t\t3. Compare two btree");
printf("\n\t\t4. In Order Traverse Print Tree");
printf("\n\t\t5. Print SqList");
printf("\n\t\t6. Count the Depth of a Tree");
printf("\n\t\t7. Pre Order Print the Step of a Node");
14
数
据
结
构
之
树
和
二
叉
树
27
printf("\n\t\t8. Locate a Elememt");
printf("\n\t\t9. Find Depth of a
Element");
printf("\n\t\t10.Init Empty Tree");
printf("\n\t\t11.Create one tree");
printf("\n\t\t0. Exit");
printf("\n\t...............................................
....");}
数
据
结
构
之
树
和
二
叉
树
28
main(){ int choice; SqBT BT; TElemType e;
static SqBT BT1={1,12,34,56,0,23,45,77,0,0,
12,34,89,12,0,0,0,0,0,0,1,22,0,3,45};
InitBT(BT); CreateBT(BT,BT1);
while(1){MenuList();
printf("\Please Press your choice(0~10):");
scanf("%d",&choice);
switch(choice){
case 1: Insert(BT);break;
case 2: printf("Pre Order:");PreBT(BT,1);
printf("\nIn Order:");InOrderBT(BT,1);
printf("\nPost Order:");
PostBT(BT,1);break;
15
数
据
结
构
之
树
和
二
叉
树
29
case 3: printf("BT compare BT1 is %s",
(Compare(BT,BT1,1)==True?"Sample":"No
t Sample"));break;
case 5: printSq(BT);break;
case 4: printf("");InBT(BT,1,20);
case 6: printf("\nThe depth of the tree is
%d",DepthBT(BT,1));break;
case 7: printf("\n");PrintNode(BT,1);break;
数
据
结
构
之
树
和
二
叉
树
30
case 8:
case 9: printf("\n Input a data:");
scanf("%d",&e);
printf("\nDepth(%d)=%d",e,FindNode(BT,1,
e));break;
case 10: InitBT(BT);break;
case 11: CreateBT(BT,BT1);break;
case 0: return; }
} /* while(1)*/ } /*end of main*/
16
数
据
结
构
之
树
和
二
叉
树
31
?链式存储结构（二叉链表）
? 二叉树中的结点包含一个
数据元素和分别指向其左、
右子树的两个分支（指
针）；
? C语言类型定义如下：
typedef struct Btn{
TElemType data;
struct Btn *lchild ,
*rchild;
}BTN ,*BT;
D
左子树 右子树
lchild data rchild
数
据
结
构
之
树
和
二
叉
树
32
? 例：用二叉链表表示下面的二叉树。
A
B
C D
E
F
G
A ^
B
^ C ^ D
^ E ^ F ^
^ g ^
17
数
据
结
构
之
树
和
二
叉
树
33
二叉链表中指针域的情况
? 在含有 n个结点的二叉链表中：
（ 1）共有 2n个指针域，其中，
（ 2）有 n+1个空链域，
（ 3）实际使用了 n-1个链指针；
数
据
结
构
之
树
和
二
叉
树
34
? 二叉树的基本操作
?CreateBT(BT &T)//构造二叉链表表示的二叉树 T
?PreOrderT(BT T ) //前序遍历二叉树 T：打印每
个结点的数据域一次且仅一次
?InOrderT(BT T) //中序遍历二叉树 T：打印每个
结点的数据域一次且仅一次
?PostOrderT(BT T) //后序遍历二叉树 T：打印每
个结点的数据域一次且仅一次
?LevelOrderT(BT T) //层序遍历二叉树 T：打印每
个结点的数据域一次且仅一次
18
数
据
结
构
之
树
和
二
叉
树
35
6.3 二叉树的遍历
? 定义：二叉树的遍
历就是按一定的规
则访问树中的结点，
使得每个结点被访
问且仅被访问一次。
? 前序遍历：
对非空二叉树：
(1) 访问根结点；
(2) 前序遍历左子树；
(3) 前序遍历右子树。
前序遍历：
A , B , D , C , E , F
数
据
结
构
之
树
和
二
叉
树
36
? 中序遍历：
对非空二叉树
(1) 中序遍历左子树 ;
(2) 访问根结点；
(3)中序遍历右子树。
? 后序遍历：
对非空二叉树：
(1) 后序遍历左子树；
(2) 后序遍历右子树 ;
(3) 访问根结点。
中序遍历：
D , B , A , E , C , F
后序遍历：
D , B , E , F , C , A
19
数
据
结
构
之
树
和
二
叉
树
37
a
c d
e f
／
－b
×
＋
－
+
遍历结果 :
中序 : a+b × c － d － e /f
后序 : abcd －× +ef / －
前序 : － +a × b－ cd /ef
?例：表达式 a+b × (c-d)-e/f
数
据
结
构
之
树
和
二
叉
树
38
T
A
B
C
D
E
F
T
rchild
lchild
?前序遍历递归算法
PreOrderT(BT T){
if(T){
printf(“ %d ,”,T→data );
PreOrderT(T→lchild);
PreOrderT(T→rchild); }}
20
数
据
结
构
之
树
和
二
叉
树
39
? 中序遍历递归算法
InOrderT(BT T){
if(T){
InOrderT(T→lchild);
printf(“%d ,”,T→data );
InOrderT(T→rchild);
}
}
后序遍历递归算法
PostOrderT(BT T){
if(T){
PostOrderT(T→lchild);
PostOrderT(T→rchild);
printf(“%d ,”,T→data );
}
}
数
据
结
构
之
树
和
二
叉
树
40
?三种遍历过程示意图例
a
c
b
×
－
a b
* c
-
ba
*
-
c
a b
* c
-
－
×
a
b
c
? 虚线表示执行过程 : 向下表示更深层的递归调用 ;
向上表示递归调用返回 ;
? 沿虚线记下各类符号 ,便得到遍历的结果 。
21
数
据
结
构
之
树
和
二
叉
树
41
前序
遍历
的非
递归
算法
+
* E
/ D
A **
B C
栈
+*/A**BCDE
输出
设立一个后
进先出栈，
用以存放结
点信息。
top=0
+ +
*
/
A
+
*
/
top=1
+
*
**
top=4
top=3
top=3
+
*
**
B
top=4
+
*
C
top=3
do{ while(p<>NULL) {
printf(p->data);
push(S,p) ;p=p->Lchild;}
if(top<>0) {
pop(S,p); p=p->rchild; }
}while((top==0)&&(p== NULL));
数
据
结
构
之
树
和
二
叉
树
42
? 算法描述：
1、当前指针指向根结点。
2、若当前指针不为空，则访问该结点。
3、当前指针指向该结点的左孩子，并将该结点
指针入栈；
4、循环 2， 3步，直到当前指针为空；
5、若栈顶指针不为空，则弹出栈顶元素；
6、访问右孩子；
7、循环 2~6步，直到栈顶指针为空，或者当前
指针为空。
22
数
据
结
构
之
树
和
二
叉
树
43
void Preorder（ BT T） {
int BT p; p=T; initstack(S);
do{
while(p<>NULL) {
printf(“Results of Preorder is: %c ”, p->data); //访问当前结
点
push(S,p) //当前结点指针入栈
p=p->Lchild; //当前指针指向左孩子 }
if(top<>0) { //若栈顶指针不为 0
pop(S,p); //弹出栈顶元素
p=p->rchild; }
}while((top==0)&&(p== NULL)); //直到栈顶或当前指针为空
}
数
据
结
构
之
树
和
二
叉
树
44
中序遍历的非递归算法
过程： 先沿着树向左下方移动，直到不能再走为
止，然后访问结点，打印信息，往右移动一
个结点，再继续下去，如无法再往右移动，
则再后退一个结点，重新开始。
23
数
据
结
构
之
树
和
二
叉
树
45
+
*
**
top=3
+
*
**
B
top=4
+
*
C
top=3
+
D
top=2
E
top=1
+
* E
/ D
A **
B C
A/B**C*D+E
输出
栈
top=0
+ +
*
/
A
+
*
/
top=1
top=4
top=3
数
据
结
构
之
树
和
二
叉
树
46
InOrderT(BT T){
if(T) {
Initstack(S); //建立结点指针型堆栈；
p=T;
do{
if ( p ) { Push( S, p ); p=p→ lchild; }
else { Pop( S, p ) ;
printf(“ %d “,p→ data);
p=p → rchild;
}
} while ( 堆栈不空 || p );
}
24
数
据
结
构
之
树
和
二
叉
树
47
建
立
二
叉
树
链
式
存
储
的
算
法
描
述
利
用
完
全
二
叉
树
的
性
质
建
立
链
表
CreateBT( BT &T, int k, int m){
// BT nar[50]; 用于存储各结点的地址
n=pow(2,k)-1; for(i=1;i<=n;i++)nar[i]=^;
for(i=1;i<=m;i++){
输入结点的数据域值 x 和编号 j ；
p=(BT)malloc(sizeof(BTN)); nar[j]=p ;
p→ data=x ; p→ lchild=^; p→rchild=^;
if(j==1) T=p ;
else{ parent=(int)(j/2); q=nar[parent];
if( j % 2) q → rchild=p;
else q → lchild=p; }
} }//时间复杂度 O(m),空间复杂度 O(2 )
k
数
据
结
构
之
树
和
二
叉
树
48
建立链表
示意图
nar
123456789
10
^^^
2
A
3
^
B
5
6
C
7
10
D
^
^
E
^
^
F
^
^
G
^
25
数
据
结
构
之
树
和
二
叉
树
49
按层次遍历二叉树的算法
void Levelorder(BT T){
if(T){ 建立结点指针型队列 Q；
EnQueue(Q,T);
while(!EmptyQueue(Q)){
DeQueue(Q,p); printf(p->data);
if(p->lchild) EnQueue(Q,p->lchild);
if(p->rchild) EnQueue(Q,p->rchile);
} //while }//if
}//时间复杂度 O(n)，空间复杂度 O( 2 )
k
数
据
结
构
之
树
和
二
叉
树
50
按层次遍历二叉树的递归算法
void Levelorder(BT T){
if(T){ printf(T->data);
if(T->lchild) EnQueue(Q,T->lchild);
if(T->rchild) EnQueue(Q,T->rchile);
DeQueue(Q,T);
Levelorder(T);
}//if
}//时间复杂度 O(n)，空间复杂度 O( 2 )
空间复杂度包括栈和队列
k
26
数
据
结
构
之
树
和
二
叉
树
51
用层次遍历统计每层的结点数
void LeveNum(BT T ， int A[ ]){
if(T){ 建立结点指针型队列 Q；
EnQueue(Q,T);k=1;i=1;
while(!EmptyQueue(Q)) {
printf( i , k ); A[ i ]=k; n=0;
for(j=0;j<k; j++) {
DeQueue(Q,p);
if(p->lchild) {EnQueue(Q,p->lchild);n++;}
if(p->rchild) {EnQueue(Q,p->rchile);n++;}
} //for
k=n; i++;
}//while
A[ 0 ]=i-1; }//if }//
数
据
结
构
之
树
和
二
叉
树
52
用前序递归统计每层的结点数
void ProLeveNum(BT T ， int A[ ] ){
// 数组 A的初值为全 0， A[0]记录树的高度，其余元素
记录每层的结点数
static k; // k为递归层次，也就是结点 T在树中的层次
k++;
if(T){ A[k]++;
if(k>A[ 0 ])A[ 0 ]=k;
ProLeveNum(T->lchild, A);
ProLeveNum(T->rchild,A);
}
k--;
}//
27
数
据
结
构
之
树
和
二
叉
树
53
6.4 线索二叉树
充分利用二叉树中 n+1个空链域
? 若结点有左子树，则其 lchild域指示其左
孩子，否则，令 lchild指示其前驱；
? 若结点有右子树，则其 rchild域指示其
右孩子，否则，令 rchild指示其后继；
? 修改结点结构：
ltag lchild data rchild rtag
数
据
结
构
之
树
和
二
叉
树
54
0 lchild域指示结点的左孩子
ltag =
1 lchild域指示遍历时的结点前驱
0 rchild域指示结点的右孩子
rtag=
1 rchild域指示遍历时的结点后继
前序线索二叉树、中序线索二叉树、
后序线索二叉树
28
数
据
结
构
之
树
和
二
叉
树
55
? 二叉树的二叉线索存储表示
typedef enum{Link,Thread}PointerTag;
typedef struct Bthn{
TElemType data;
struct Bthn *lchild,*rchile;
PointerTag Ltag , Rtag ;
}BTHN , *BTHT ;
? 指向结点前驱和后继的指针叫做线索；
? 加上线索的二叉树称为线索二叉树。
? 对二叉树以某种次序遍历将其变为线索
二叉树的过程叫做线索化。 (参见 Page
134~135 算法 )
数
据
结
构
之
树
和
二
叉
树
56
? 中序线索二叉树
? 查找结点p的后继: 所有叶子结点的右链直接指示
了后继，所有非终端结点的后继应是其右子树中第一
个中序遍历的结点 。
程序实现如下：
void next(p,var,x) {
q=p->rchild;
if(p->rtag= =0){ // 若 rchild指向右孩子
do { //循环直到找到最左边的孩子
q=q->lchild;
} while(q->ltag = =0)；
} //否则 rchild指向后继
x=q; }
-
+ /
a * e +
b -
c d
NULL
NULL
29
数
据
结
构
之
树
和
二
叉
树
57
? 中序线索二叉树
? 查找结点p的前驱
特点： 若其左标志为 “1”，
则左链为线索，指示其前驱，
其前驱为左子树上最后遍历
的一个结点。
-
+ /
a * e +
b -
c d
NULL
NULL
程序实现如下：
void pre(p,var,x) {
q=p->lchild;
if(p->ltag= =0){ // 若 lchild指向左孩子
do { //找到左孩子最右边的结点
q=q->rchild;
} while(q->rtag = =0);
} //否则 rchild指向前驱
x=q;
}
数
据
结
构
之
树
和
二
叉
树
58
? 中序线索链表的中序遍历
void InOrderTraverseThr（ BiThrTree T） {
BiThrTree p;
p=T->lchild; // 指针 p初始化
while (p!=T) {
while (p->ltag= =Link)
p=p->lchild;
printf(“Result of preorder is %c ”, p->data); //访问左
子树为空的结点
while(p->rtag= =Thread && p->rchild!=T) {
p=p->rchild;
printf(“Result of preorder is %c ”, p->data); // 访
问后继结点
}
p=p->rchild;
} }
30
数
据
结
构
之
树
和
二
叉
树
59
? 中序线索化
线索化的实质是将二叉链表中的空指针该
为指向前驱或后继的线索，而前驱或后继的信
息只有在遍历时才能得到，因此线索化的过程
即为在遍历的过程中修改空指针的过程。
数
据
结
构
之
树
和
二
叉
树
60
Status InorderThreading( BiThrTree *Thrt, BiThrTree T) {
if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))
exit(OVERFLOW);
Thrt->ltag=Link;
Thrt->rtag=Thread; //建立头结点
Thrt->rchild=Thrt; //右指针回指
if (!T) Thrt->lchild=Thrt;
else { Thrt->lchild=T; pre=Thrt;
InThreading(T); //中序遍历进行中序线索化
pre->rchild=Thrt;pre->rtag=Thread; //最后一个结点线索化
Thrt->rchild=pre; } return OK; }
31
数
据
结
构
之
树
和
二
叉
树
61
Void InThreading(BiThrTree p) {
if(p){
InThreading(p->lchild); //左子树线索化
if(!p->lchild) {
p->ltag=Thread; //前驱线索化
p->lchild=pre; }
if(!pre->rchild) {
pre->rtag=Thread; //后继线索化
pre->rchild=p; }
pre=p; //保持 pre指向 p的前驱
InThreading(p->rchild); //右子树线索化
} }
数
据
结
构
之
树
和
二
叉
树
62
6.5 树和森林
?树的存储结构
? 双亲表示法：树中的结点由数据元素值和
指向其双亲结点的指针。
特点：求结
点的双亲很
容易，但求
结点的孩子
需要遍历整
个向量。
1
3
4
5
6
7
8
9
2
结点号 data parent
9 59
8 58
7 57
6 36
5 25
4 24
3 13
2 12
1 01
双亲表示法
32
数
据
结
构
之
树
和
二
叉
树
63
? 孩子表示法：是把每个结点的孩子
结点链接形成单链表， n个结点有 n
个孩子链表（叶子 结点的孩子链表
为空）。
1
3
4
5
6
7
8
9
2
孩子链表
1
2
3
^4
5
^6
^7
^8
^9
2 3 ^
6 ^
7 9 ^8
4 5 ^
1
2
3
4
5
6
7
8
9
数
据
结
构
之
树
和
二
叉
树
64
? 孩子兄弟表示法：又称二叉树表示法。
结点中的两个指针分别指向“第一个
孩子结点”和“下一个兄弟结点”
1 ^
2
4^ 5 ^ 6 ^^
7^ 8^ 9 ^^
3 ^
孩子兄弟表示法
1
3
4
5
6
7
8
9
2
33
数
据
结
构
之
树
和
二
叉
树
65
? 树与二叉树之间的转换
? 一般树转换成二叉树：加线、抹线、旋转。
? 转换成的二叉树有两个特点：
?根结点没有右子树；
?转换生成的二叉树中各结点的右孩子是原来树中该
结点的兄弟，而该结点的左孩子还是原来树中该结
点的孩子。
? 二叉树还原成一般树：加线、抹线、规整化。
? 思考题：已知一棵一般树 T 的二叉链表存储，
写出求树中结点 q (q是结点指针 )
?有多少孩子结点的算法；
?有多少兄弟结点的算法。
数
据
结
构
之
树
和
二
叉
树
66
D
E F
I
B
C
G
H
J
A
D
E F
I
B
C
G
H
J
A
A
B
C
DE
F
G
H
I
J
二叉树
例：将下面的树转换成二叉树。
34
数
据
结
构
之
树
和
二
叉
树
67
6.6 哈夫曼树及哈夫曼编码
? 概念：
? 结点之间的路径：由从树中一个结点
到另一个结点之间的分支构成。
? 路径长度：路径上的分支数目。
? 树的路径长度：是从树根到每个结点
的路径长度之和。
问题：对结点数相同的树来说，路径
长度最短的是 二叉树。
数
据
结
构
之
树
和
二
叉
树
68
? 叶子结点的带权路径长度：从该 结点到树根 之
间的路径长度 Lk与结点上的权值 Wk的乘积
Lk*Wk
? 树的带权路径长度：为树中所有叶子结点的带
n
权路径之和 WPL=∑ Wk*Lk
k=1
? 最优二叉树或哈夫曼树：假设有 n个权值 { w1,
w2 , w3 , ... , wn } , 构造一棵有 n个叶子结点的二
叉树，每个叶子结点带一个权值，则其中带权
路径长度 WPL最小的二叉树称做最优二叉树或
哈夫曼树。
35
数
据
结
构
之
树
和
二
叉
树
69
例如：有一组权值为 ( 7, 5, 2, 3 )
? 电文总长为 18个字符， a, b , c , d 出现的次数分别
为（ 7， 5， 2， 3），制定各字符的编码。
a(00) b(01)
c(10) d(11)
电报码长为 34
2*(7+5+2+3)
a(010) b(011)
c(1) d(00)
电报码长为 44
3*(7+5)+1*2+2*3
a(0) b(10)
c(110) d(111)
电报码长为 32
1*7+2*5+3*(2+3)
7
7
7
5
2
3
3
5
2
3
5
2
01
01
01
01
01
01
01
01
01
数
据
结
构
之
树
和
二
叉
树
70
? 构造哈夫曼树的步骤
? 根据给定的 n个权值 { w1, w2 , w3 , ... , wn } ，
构成 n棵二叉树的 集合 F ={ T1, T2 , T3 , ... ,
Tn } ，其中，每棵二叉树 Ti 中只有一个带权
为 wi 的根结点，其左右子树均空；
? 在 F 中选取两棵根结点的权值最小的树作为左
右子树构造一棵新的二叉树，且置新的二叉树
的根结点的权值为其左、右子树上根结点的权
值之和；
? 在 F 中删除这两棵子树，同时将新得到的二叉
树加入 F中；
? 重复 2 和 3 ，直到 F 只含一棵子树为止。
这棵树便是哈夫曼树
36
数
据
结
构
之
树
和
二
叉
树
71
例：根据下面的权值分布，试设计一棵具有最小
权值的二叉树。
a
7
b
5
c
2
d
4
树的生成过程
a
b
d
7
5
2
4
c
c
d
2
4
6
b
c
d
2
4
6
5
11
数
据
结
构
之
树
和
二
叉
树
72
? 哈夫曼树的存储表示
一棵有 n个叶子结点的 Haffman 树共有
2n-1个结点，可以存储在一个大小为 2n-1
的一维 HTN型 数组中。（下标链）
typedef struct { unsigned int weight ;
unsigned int parent;
unsigned int lchild, rchild ;
} HTN , *HFT;
37
数
据
结
构
之
树
和
二
叉
树
73
? 构造哈夫曼树的算法描述
void HaffmTree(HFT &HT , int w[ ] , int n ){
if(n<=1) return;
m=2*n-1; /* n=n
2
+1, 0下标不用
HT=(HFT)malloc((m+1)*sizeof(HTN));
for(k=1;k<=n;k++) HT[k]={w[k],0,0,0 }；
for(; k <=m;k++) HT[k]={0,0,0,0};
for(k=n+1;k<=m;k++){ Select(HT , k-1,s1,s2);
HT[s1].parent=k; HT[s2].parent=k;
HT[k].lchild=s1; HT[k].rchild=s2;
HT[k].weight=HT[s1].weight+HT[s2].weight;
} }
数
据
结
构
之
树
和
二
叉
树
74
? 哈夫曼编码哈夫曼编码
? 前缀编码：在设计长短不等的编码时，必
须是任一个字符的编码都不是另一个字符
的编码的前缀。
? 可以用二叉树设计二进制的前缀编码。其
中，哈夫曼树的编码（哈夫曼编码）最短。
? 哈夫曼树是严格的二叉树，即哈夫曼树中
没有度为 1的结点。
38
数
据
结
构
之
树
和
二
叉
树
75
例：根据下面字母出现的概率，采用哈夫曼
编码方法，设计每个字母的编码。
P(A)=0.25, P(B)=0.3, P(C) =0.15, P(D)=0.3。
解：根据每个字母出现的概率，按大到小的顺序排
列如下：
A的编码： 11
B的编码： 10
C的编码： 01
D的编码： 00
P（ D） =0.3
P（ B） =0.3
P（ A） =0.25
P（ C） =0.15
0
1
0
1
0
1
数
据
结
构
之
树
和
二
叉
树
76
? 从叶子到根逆向求哈夫曼编码
void HaffmCode(HFT &HT , char *HC[ ] , int n ){
if(n<=1) return;
cd=(char*)malloc(n*sizeof(char)); cd[n-1]=‘\0’;
for(k=1;k<=n;k++){ start=n-1; // start从后往前移动
for( c=k,f=HT[k].parent; f!=0 ; c=f,f=HT[f].parent)
if(HT[f].lchild==c) cd[--start]=‘0’;
else cd[--start]=‘1’;
HC[k]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[k],&cd[start]); }
free(cd);
}
39
数
据
结
构
之
树
和
二
叉
树
77
?本章重点
1、二叉树的基本概念和性质；
2、二叉树的存储方式：顺序和链式；
3、二叉树的遍历：先序、中序及后序遍历；
4、与二叉树有关的运算及程序设计；
5、 二叉树的线索化：先序、中序及后序线索化的存储和表示；
6、树的存储方式，树与二叉树的相互转换 ；
7、最优二叉树及哈夫曼编码。
