1
内容提要
? 6.1 树的定义及基本术语
? 6.2 二叉树
? 6.3 编历二叉树
? 6.4 线索二叉树
? 6.5 二叉排序树
? 6.6 平衡二叉树
? 6.7 树和森林
? 6.8 哈夫曼树及应用
2
6.1 树的定义及基本术语
1、树的定义
(1)树的一般定义
树 是包含 n个结点的有限集合，在这个集合上定义了
一个唯一的关系，这个关系满足下面的条件：
I,存在唯一的一个结点，它没有前驱，称为根
II,除了根结点外，其它结点有且仅有一个前驱
III,除了根结点外，任何结点 ai(0? i?m)，都存在唯一
的一个从根到 ai的结点序列 a0,a1,a2,..,am,其中，
a0是根。这个序列称为从根到 ai的路径。a0
a1 a2 a3
a4 a5
3
树的定义及基本术语 (cont’d)
(2)树的递归定义
树 是包含 n个结点的有限集，在这个集合上定义了
唯一的关系，它满足下面的条件：
I,有个特定的称为根的结点；
II,当 n>1时，除了根以外的其余结点根据它们之间
的关系可分为 m个不相交的有限集 T1,T2,..,Tm，其中
，每个有限集都是一棵树。这些树称为根的子树。
a
b c d
e f
T1={b,e,f};T2={c};T3={d}
4
树的定义及基本术语 (cont’d)
(3)树的基本术语
1,根,唯一没有前驱的结点
2,度,结点的度 是结点的子树数目,树的度 是指结点
度的最大值
3,叶子,度为 0的结点，也称 终端结点
4,分枝结点,叶子之外的结点，也称非终端结点。
除了根以外的分枝结点又称内部结点。
5,双亲, 子女, 祖先, 子孙,结点子树的根称为结
点的子女，该结点就是它子女的双亲；某结点的
祖先是指从根到该结点的路径上的全部结点；结
点的子树中全部结点都是该结点的子孙。
a
b c d
e f
5
树的定义及基本术语 (cont’d)
(3)树的基本术语
6,兄弟、堂兄弟,同一个结点的子女互为兄弟，双
亲为兄弟的结点互称堂兄弟。
7,结点的 层次, 树的深度 (高度 )，根为第 1层，结点
的层次是其双亲层次加 1。树的深度是指结点的最
大层数。
8,有序树、无序树,如果结点的各子树自左向右是
有次序的，则称有序树，否则称无序树
9,森林, m棵互不相交的树就构成了森林。
a
b c d
e f g
第 1层
第 2层
第 3层
6
6.2 二叉树
1,二叉树的概念
每个结点最多有 2棵子树，并且子树有左右之
分，不能任意颠倒。
二叉树有 5种形态：
①空树 ②只有一个根
③只有左子树 ④只有右子树
⑤有两个子树
2,二叉树的性质
①在二叉树的第 i层上至多有 2i－ 1个结点 (i>=1)
② 深度为 k的二叉树至多有 2k-1个结点。
1
2 3
4 5 6 7
8 9
7
二叉树 (cont’d)
2,二叉树的性质
③ 设二叉树中，叶结点数为 n0,度为 1的结点数为 n1,度
为 2的结点数为 n2,则有,n0 = n2 + 1
因为 N=n0+n1+n2=1+n1*1+n2*2
④ 具有 n个结点的完全二叉树的深度为 ?log2n? +1
?log2n? 表示 log2n取整
满二叉树,具有最多结点数的二叉树（即一棵深度为
k且有 2k-1 个结点的二叉树）
完全二叉树,将满二叉树从右向左
删除叶子的结果，因此,
结点数 n<=2k-1，并且 n>2k-1-1
1
2 3
4 5 6 7
8 9
9
二叉树 (cont’d)
3,二叉树的存储结构
(1) 顺序存储,利用数组按照完全二叉树的方式
对结点编号，根据编号将结点存放在数组中相应
的位置中。
#define N 50 //二叉树的最大结点数
typedef elemtype SQTREE[N]; //顺序存储的二叉树
SQTREE bt;
A
B C
E F
1
2 3
4 5
6
A B C E F
0 1 2 3 4 5 6 7 8 9
10
二叉树 (cont’d)
3,二叉树的存储结构
(2)链式存储, 利用二叉链表或三叉链表
typedef struct treenode
{elemtype data; //结点数据
//指向左右孩子的指针
struct treenode *lchild,*rchild /*,*parent*/;
}TREENODE,*TREENODEPTR,*BTREE
A
B^ C ^
E ^^ F ^^
DATA
PARENT
LCHILD RCHILD
lchild data rchild
lcjild data parent rchild
11
＃ define N 50 //定义二叉树最大结点数
void createtree(BTREE *root)
{int value,front,rear; TREENODEPTR t,q[N];
//q是队列,front,rear是队头队尾下标。
scanf("%d",&value); //开始创建根结点
if(value==0){*root=NULL; return;};
//输入 0，表示空结点
*root=(TREENODEPTR)malloc(sizeof(TREENODE));
(*root)?data=value;
rear=front=1; q[front]=*root;
//根指针入队
二叉树 (cont’d)
4,二叉树的建立 (1) 按层序遍历顺序为输入顺序
while(front<=rear) //只要队列不空
{ t＝ q[front]; front++; //出队一结点指针
scanf("%d",&value);
if(value==0) t?lchild=NULL;
else
{t?lchild=(TREENODEPTR)malloc(sizeof(TREENODE));
t?lchild?data=value; //建立左孩子结点
rear++; q[rear]=t?lchild; //左孩子入队
}
scanf("%d",&value);
if(value==0) t?rchild=NULL;
else
{t?rchild=(TREENODEPTR)malloc(sizeof(TREENODE));
t?rchild?data=value; //建立左孩子结点
rear++; q[rear]=t?rchild; //左孩子入队
}
}//while }
5
3 4
7 9
12
广义表字符串输入的形式是：
A(B(,D),C(E,))
这是个递归输入方式，因此这样建立二叉树也
是个递归的过程。这里给出非递归的算法。
算法思想,
(1) 从左向右扫描字符串，遇到字母就建立结点；
(2) 遇到 (表示前面字母有孩子，要将前面字母
的结点入栈，以便将左右孩子与双亲链接起来。
(3) (后面的字母是左孩子，逗号后面的字母是
右孩子，遇到 )表示以栈顶结点为根的子树建立
完毕，出栈。
二叉树 (cont’d)
4.二叉树的建立 (2) 根据广义表字符串建立二叉树
A
B C
D E
13
#define N 50
void creattree(BTREE *root,char *str) //假设结点数据是字母
{TREENODEPTR t,s[N];
char *p; int top=0,n=0,tag; //s是栈,top是栈顶下标
p=str;
for(;*p;p++)
{switch(*p)
{case '(', top++; s[top]=t;
tag=1;break; //将前面结点入栈，准备链接左孩子
case ')',top--;break; //栈顶结点的子树创建完毕，出栈
case ',',tag=0;break; //准备链接右孩子
二叉树 (cont’d)
4.二叉树的建立 (2)根据广义表字符串建立二叉树
default,//常规字母，直接创建结点
t=(TREENODEPTR)malloc( izeof(TREENODE));
t?data=*p;
t?lchild=t?rchild=NULL; //默认情况下,左右孩子为空
if(n==0) //第一次创建的结点是整个树的根
{ *root=t; n++; }
else
{
if(tag) s[top]?lchild=t; //栈顶结点的左孩子是 t
else s[top]?rchild=t; //栈顶结点的右孩子是 t
}
}//switch
}//for
}
A
B C
D E
14
6.3 遍历二叉树
1,二叉树的遍历方式
(1) 先序遍历 (DLR)，先输出根，再遍历左子树，最后
遍历右子树
(2) 中序遍历 (LDR)，先遍历左子树，再输出根，最后
遍历右子树
(3) 后序遍历 (LRD)，先遍历左子树，再遍历右子树，
最后输出根
A
B C
D E
DLR：
LDR：
LRD：
A B D C E
ABD CE
ABD CE
15
遍历二叉树 (cont’d)
2,二叉树的遍历算法 (1)中序遍历
void inorder(BTREE root)
{
if(root!=NULL)
{ inorder(root?lchild);
printf("%d",root?data);
inorder(root?rchild);
}
}
递归算法
16
遍历二叉树 (cont’d)
2,二叉树的遍历算法 (2)先序遍历
void preorder(BTREE root)
{
if(root!=NULL)
{
printf("%d",root?data);
preorder(root?lchild);
preorder(root?rchild);
}
}
递归算法
17
遍历二叉树 (cont’d)
2,二叉树的遍历算法 (3)后序遍历
void postorder(BTREE root)
{
if(root!=NULL)
{
postorder(root?lchild);
postorder(root?rchild);
printf("%d",root?data);
}
}
递归算法
18
算法思想,
开始时栈空，当前处理的结点指向根，只要遍历未完成，
则执行下面的操作：
(1) 递归：只要当前不空，就将当前结点入栈，向左孩子
推进一步，直到最左端
(2) 循环执行以下操作：
如果栈顶结点有右子树，则向右推进一步，进入右
子树并跳出循环，转到 (1)。
如果栈顶是叶子，开始返回 (出栈，并输出结点信息 )，
这时需要区分从左子树返回还是从右子树返回。如
果从左边返回，则寻找栈顶结点的右子树，继续递
归；否则继续循环出栈返回，直到不再是右边返回
或者返回到根。
遍历二叉树 (cont’d)
2.二叉树的遍历算法 (4)后序遍历
非递归算法
19
#define N 50 //定义二叉树最大结点数
void postorder(BTREE root)
{TREENODEPTR p,s[N]; int top=0;
//s是栈,top是栈顶下标
p=root;
while(1)
{
while(p!=NULL) //递归的循环
{top++; s[top]=p; p=p?lchild;
} //一直向左递归,直到最左端
遍历二叉树 (cont’d)
2,二叉树的遍历算法 (4)后序遍历
while(1)
{ if(s[top]?rchild!=NULL) //如果是左返回
{ p=s[top]?rchild;
break; } //向右进一步，跳出循环，进入递归
//开始从右边返回,包括右子树不空的右返回
while(top!=0&&
(s[top]?rchild==NULL||p==s[top]?rchild))
{p= [t ]; to --; printf("%d ",p?data);}
if(top==0) return;
}//while(1)
}//while(1)
}
非递归算法
20
void preorder(BTREE root)
{ TREENODEPTR p,s[N]; int top=0;
p=root;
while(1)
{ while(p!=NULL) //一直向左递归
{ printf("%d ",p?data);
top++; s[top]=p;
p=p?lchild;
}
if(top!=0) //弹出栈顶，右孩子转去递归
{p=s[top]; top--; p=p?rchild; }
else return;
}
}
遍历二叉树 (cont’d)
2,二叉树的遍历算法 (5)先序遍历
非递归算法
21
层序的次序,
15 14 13 12 11 10 9 8
4 5 6 7
3 2
1
树的遍历必须从根开始，上述顺序可以看成是下面的反
序,1 2 3 7 6 5 4 8 9 10 11 12 13 14 15
算法思想,
先将根入栈，然后从第二层开始，交替地自左向右和自
右向左将结点入栈。
最根本地问题是不能将上层入栈的结点序列看成队列，
而应该看成栈。为了获取下一层结点，
不能将上层结点出队而是出栈！
遍历二叉树 (cont’d)
2,二叉树的遍历算法 (6) 层序遍历
自下而上
左右交替
的那种
15
14
13
12
11
10
9
8
4
5
6
7
3
2
1
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
即栈中栈
22
void layerorder(BTREE root)
{ TREENODEPTR p,s[N]; int top,bottom,m,n;
//根结点入栈，第一层结点的小栈只有一个结点
p=root; top=1; s[top]=p; bottom=top; //bottom是小栈底
while(1)
{ n=bottom; m=top; //准备将当前层结点出栈
bottom=top+1; //形成下一层结点的栈底
while(m>=n)
{ p=s[m]; m--; //出栈一结点
if(p?lchild!=NULL) //自左向右入栈
{top++; s[top]=p?lchild;}
if(p?rchild!=NULL)
{top++; s[top]=p?rchild;}
}//while(m
if(top==bottom-1)break;//如果这层没有结点,表明遍历结束
遍历二叉树 (cont’d)
(2)二叉树的遍历算法 (6) 层序遍历
n=bottom; m=top; //准备下一层处理
bottom=top+1;
while(m>=n)
{ p=s[m]; m--; //出栈一结点
if(p?rchild!=NULL) //自右向左栈
{top++; s[top]=p?rchild;}
if(p?lchild!=NULL)
{top++; s[top]=p?lchild;}
}//while(m
if(top==bottom-1)break;
}//while
wh le(top>=1)
{printf("%d ",]?data);top--;}
printf("\n");
}
4
5
6
7
3
2
1
bottom(旧 )
top
bottom
23
遍历二叉树 (cont’d)
3,二叉树遍历算法的应用 (1)求树的深度
int depth(BTREE root)
{ int hr,hl; //记录左右子树的深度
if(!root) return 0; //空树深度为 0
else {
hl=depth(root?lchild);
hr=depth(root?rchild);
if(hl>=hr) return hl+1;
else return lr+1;
}
}
24
void inorder(PTREENODEPTR root)
{ //root是三叉链表的二叉树
PTREENODEPTR p; int n=0; p=root; //记录叶子数量
while(1)
{ while(p?lchild) p=p?lchild; //一直向左递归
while(1) //循环返回
{ if(p?rchild!=NULL)
{p=p?rchild; break;} //进入右子树，继续递归
if(p?rchild==NULL&&p?lchild==NULL) n++;
while(p?parent!=NULL&&(p==p?parent?rchild||
p?parent?rchild==NULL))
p=p?parent;
if(p?parent==NULL) //返回到了根
{ printf("the tree has %d leafs\n",n); return;}
p=p?parent?rchild;break;
}//while(1)
}//while(1) }
遍历二叉树 (cont’d)
3,二叉树遍历算法的应用 (2)求二叉树叶子结点的个数
25
6.4 线索化二叉树
1,线索化
遍历二叉树的结果是将二叉树的结点排列成某种顺
序，使这些结点形成线性关系。但这种线性关系只能在
重新遍历二叉树时才会重新获得。如果在第一次遍历二
叉树时就将这种线性关系保存下来，这种操作称为,线
索化,。
为了将二叉树线索化，需要重新定义二叉树结点的
数据类型。
中序线索化结果
A
B C
D E
NULL NULLtypedef struct treenode
{ elemtype data;
struct treenode *lchild,*rchild;
int ltag,rtag; /*ltag为 0,lchild指向左孩子，否则指
向线索化序列中的前驱； rtag为 0,rchild指向右孩子，
否则指向线索化序列中的后继 */
}TREENODE,*TREENODEPTR;
26
线索化二叉树 (cont’d)
0 lchild域指示结点的左孩子
ltag =
1 lchild域指示结点的前驱
0 rchild域指示结点的右孩子
rtag =
1 rchild域指示结点的后继
以这种结点结构构成的二叉链表作为二叉树的存储
结构，叫做 线索链表,其中指向结点前驱和后继的指针
，叫做 线索 。加上线索的二叉树称之为 线索二叉树 。对
二叉树以某种次序遍历使其变为线索二叉树的过程叫做
线索化 。
中序线索化结果
A
B C
D E
NULL NULL
lchild ltag data rtag rchild
27
TREENODEPTR pre;
void inordthread(TREENODEPTR *thrt,TREENODEPTR t)
{//为线索化后的树增加一个头结点 thrt，便于操作
(*thrt)=(TREENODEPTR)malloc(sizeof(TREENODE));
(*thrt)?ltag=0; (*thrt)?ltag=1;
(*thrt)?rchild=(*thrt); //开始右线索指向自身
if(t==NULL) //如果树 t为空，左指针也指向自己
(*thrt)?lchild=(*thrt);
else { //前驱指针指向线索头结点
(*thrt)?lchild=t; pre=(*thrt);
inthreading(t); //开始线索化
//线索化后,pre为最右端结点,它的后继指向头结点
pre?rchild=(*thrt); pre?rtag=1;
(*thrt)?rchild=pre; //头结点右线索指向最右结点
}
}
线索化二叉树 (cont’d)
2,线索化算法 (以中序线索为例 )：
void inthreading(TREENODEPTR p)
{/*对以 p为根的二叉树进行中序线索化 */
if(p)
{//在线索化过程中,pre一直是当前访问结点的前驱结点
inthreading(p?lc ild);
//p的左孩子为空,则指向前驱
if(p?lchild==NULL)
{p?ltag=1;
p?lchild=pre;}
//访问 p时，并不知道 p的后继
if(pre?rchild==NULL)
{pre?rtag=1;
pre?rchild=p;} //将 re的右孩子指向后继
pre=p; //进入右子树前，将前驱指针指向当前结点
inthreading(p?rchild);
}
}
A
B C
D E
28
void tinorder(TREENODEPTR thrt)
{//thrt是线索二叉树的头结点指针
TREENODEPTR p;
p=thrt?lchild; //p指向根
while(p!=thrt) //当遍历到最后有 p=thrt
{while(p?ltag==0)
p=p?lchild; //寻找最左端结点
printf("%d",p?data);
while(p?rtag==1&&p?rchild!=thrt)
{//顺着后继链，访问后继，直到后继链断掉
p=p?rchild;
printf("%d",p?data);}
p=p?rchild;
//转到上面寻找后继,p的后继就是 p的右子树最左端结点
}
}
线索化二叉树 (cont’d)
3,利用线索遍历二叉树 (以中序为例 )：
A
B C
D E
29
6.5 二叉排序树
1.二叉排序树,又称 二叉查找树 。二叉排序树或者是棵空
树，或者是棵具有下面特征的二叉树：
(1) 若它的左子树不空，左子树上的所有结点值都小
于 (大于 )根结点值
(2) 若它的右子树不空，右子树上的所有结点值都大
于 (小于 )根结点值
(3) 左右子树也都是二叉排序树
20
16 40
11 36 43
8 14 25 38
30
BTREE insert(BTREE root,int value)
{//将 value插入到二叉排序树 root中，将新的树返回
TREENODEPTR p,q,r;
r=(TREENODEPTR)mallloc(sizeof(TREENODE));
r?data=value; r?lchild=r?rchild=NULL;
if(root==NULL) return r;
p=root;
while(p)
{ q=p; //记下插入的位置
if(p?data > value) p=p?lchild; //向左子树方向插
else p=p?rchild; //向右子树方向插
}//while
if(q?data > value) q?lchild=r;
else q?rchild=r;
return root;
}
二叉排序树 (cont’d)
2、二叉排序树的建立算法
creattree(BTREE roo )
{
int value;
scanf("%d",&value);
while(value) //输入 0表示结束
{
root=insert(root,value);
scanf("%d",&value);
}
return root;
}
31
TREENODEPTR search(TREENODE root,TREENODEPTR
*f,int value)
{/*在二叉排序树 root中查找值是 value的结点，返回结点指
针，并用 f返回该结点双亲结点 */
TREENODEPTR p,q,r;
q=NULL; p=root;
while(p&&p?data!=value)
{q=p;
if(p?data>value) p=p?lchild;
else p=p?rchild;
}
*f=q;
return p;
}
二叉排序树 (cont’d)
3、二叉排序树的查找算法
32
算法思想,
由于删除结点后，二叉排序树仍必须是二叉排序树，并且最
好不增加树的深度，因此应该区分三种情况 (假设 P是要删除
的结点 )：
(1) 如果 P是叶子结点，直接删除即可
(2) 如果 P是单枝结点，可以直接用子树的根
代替 P做 P双亲的孩子
(3) 如果 P是双枝结点，则可以用 P的前驱或后继结点
H替换 P，然后在删除 H，对 H的删除必然属于 (1)(2)
两种情况。
二叉排序树 (cont’d)
4、二叉排序树的删除算法
F
P+
F
P+
H+
F
P+
H
+
F
P
H
S
C
33
BTREE delete(BTREE root,int value)
{//在二叉排序树中删除值是 value的结点，返回删除后的树
TREENODEPTR f,p,q,h;
p=search(root,&f,value); //f将是 p的双亲结点指针
if(p==NULL)return root;
if(p?lchild==NULL||p ? rchild==NULL) //p是叶子
h=NULL; //h将替代 p
else if(p?lchild==NULL) h=p?rchild;
else if(p?rchild==NULL) h=p?lchild;
二叉排序树 (cont’d)
4、二叉排序树的删除算法
else //p是双枝结点
{f=p; q=p ? rchild; //开始寻找 p的后继 q,f将是 q的双亲
while(q?lchild!=NULL)
{f=q; q=q?lchild; }
p?data=q?data; //将 q的数据复制到 p中，开始删除 q
if(q?lchild==NULL||q?rchild==NULL)h=NULL;
else if(q?lchild==NULL)h=q?rchild;
else h=q?lchild;
p=q; //p成为 f的子女
} //else
if(f==NULL) root=h;
else if(f?lchild==p) f?lchild=h;
else f?rchild=h;
free(p);
return root;
}
34
6.6 平衡二叉树
1、平衡二叉树, AVL树,左右子树的深度差的绝对
值不超过 1的二叉排序树，并且左右子树也是平衡二
叉树。
平衡二叉树的查找效率最高，因为 n个结点的二
叉树中，平衡二叉树的深度最低。二叉排序树的
深度决定了查找比较的次数。
平衡二叉树
非平衡二叉树
35
平衡二叉树 (cont’d)
2、平衡二叉树的平衡调整
当向平衡二叉树插入结点或删除结点时，会导致某棵
子树深度的变化，在某些情况下，就会导致平衡二叉树
失去平衡。这时就需要对二叉树进行平衡调整。
下面以插入结点为例，平衡调整需要两种旋转操作：
单旋 和 双旋 。
当插入新节点时,AVL树的根与插入位置之间路径上
的节点的平衡状态可能会变化。因此，插入完一个新节
点后，要沿着通向根的路径回溯，检查各节点的平衡状
态，一旦发现不平衡节点，就进行平衡化旋转。这样会
将不平衡限制最小范围内，并且通常每插入一个节点最
多需要一次调整。
36
平衡二叉树 (cont’d)
从发生不平衡的节点开始，沿回溯路径向下取两层节
点。
(1) 如果这三个节点成一条直线，则需要采用单旋进
行平衡化。 左旋是指将线上最左端节点向下旋转，右旋
是指将线上最右端节点向下旋转。
(2) 如果这三个节点成一条折线，则需要采用双旋进
行平衡化。
为了判断旋转的情况，我们将结点的左右子
树的深度差定义为“平衡因子”。当平衡因
子是正负 2时，该结点失去平衡。
37
平衡二叉树 (cont’d)
(1) 左单旋的情况
原来的 AVL树
插入一结点,A点不平衡
左单旋的结果
void LeftRotate(TREENODEPTR * Ptr)
{ //Ptr是发生不平衡的结点
TREENODEPTR *tmp=(*Ptr)?rchild;
(*Ptr)?rchild=tmp?lchild;
tmp?lchild=*Ptr;*Ptr=tmp;
}
38
平衡二叉树 (cont’d)
(2) 右单旋的情况
void RightRotate(TREENODEPTR * Ptr)
{ TREENODEPTR tmp=(*Ptr)?lchild;
(*Ptr)?lchild=tmp?rchild;
tmp?rchild=*Ptr;
*Ptr=tmp;
}
原来的 AVL树 插入一结点,A点不平衡 右单旋的结果
39
平衡二叉树 (cont’d)
(3) 先左后右双旋的情况
void LeftRightRotate(TREENODEPTR * Ptr)
{ LeftRotate(&(*Ptr)?lchild);
RightRotate(Ptr);
}
原来的 AVL树 插入一结点,A点不平衡
先左旋
再右旋
40
平衡二叉树 (cont’d)
(4) 先右后左双旋的情况
void RightLeftRotate(TREENODEPTR * Ptr)
{ RightRotate(&(*Ptr)?rchild);
LeftRotate(Ptr);
}
原来的 AVL树 插入一结点,A点不平衡
先右旋
再左旋
41
typedef struct node
{int data;
struct node *lchild,*rchild;
int balance; //平衡因子
}TREENODE,*TREENODEPTR;
int Insert(TREENODEPTR * root,int x)
{ //返回值表明树是否长高
int taller;
if(*root==NULL)
{*root=(TREENODEPTR)malloc(sizeof(TREENODE));
(*root)?data=x;
(*root)?balance=0;
return 1;
}
6,向 AVL树
插入结点
else if(x>(*root)?data){ taller=Insert(&(*root)?rchild,x);
if(taller==1) //右子树长高了
switch((*root)?balance)
{case 0:(*root)?balance=1;break;
case -1:(*root)?balance=0;taller=0;break;case 1,
//应该左旋或者先右后左双旋
if((*root)?rchild?balance==1)
{ //应该左旋，并调整平衡因子
LeftRotate(root);(*root)?balance=0;
(*root)?lchild?balance=0;}else if((*root)?rchild?balance==-1)
{ //应该双旋，并调整平衡因子
if((*root)?rchild?lchild?balance==1)
{(*root)?balance=-1;
(*root)?rchild?balance=0;}else {(*root)?balance=0;
(*root)?rchild?balance=1;}
(*root)?rchild?lchild?balance=0;
RightLeftRotate(root);
}taller=0;break;
//平衡了,没长高 }//switch
return taller; }//else if
<(
{ t ll r rt( r ) l il );
if(taller==1)//左子树长高了
switch((*root) balance)
{case 0:(*root) balance=-1;break;
case 1:(*root)?balance=0;taller=0;break;
case -1,//应该右旋或者先左后右双旋
if((*root)?lchild?balance== -1) //右旋
{RightRotate(root);(*root)?balance=0;
(*root)?rchild?balance=0;}
else if((*root) lchild balance==1) //双旋
{if((*root)?lchild?rchild?balance==1)
{(*root)?balance=0;
(*root)?lchild?balance=-1;}
else {(*root) balance=1;
(*root)?lchi d?balance=0;}
(*root)?lchild?rchild?balance=0;
LeftRightRotate(root);
}
taller=0;break; //平衡了，没长高 }//switch
return taller; }
return 0;}
42
6.7 树和森林
1、树的存储结构
(1) 孩子表示法
(2) 孩子－双亲表示法
(3) 双亲表示法
(4) 二叉链表法
43
树和森林 (cont’d)
(1) 树的孩子表示法和孩子 -双亲表示法
树结点中存放有孩子结点的指针的线性表以及双亲
指针。孩子指针线性表可以是顺序表或者链表。
typedef struct CTNode{//孩子结点
int child;
struct CTNode *next;
} *ChildPtr;
Typedef struct {
elemtype data;
ChildPtr firstchild;//孩子链表头指针
}CTBox;
Typedef struct {
CTBox nodes[N];
int n,r; //结点数和根的位置；
}Ctree;
R
B CA
F
H
D E
G K
44
树和森林 (cont’d)
(1) 树的孩子表示法和孩子 -双亲表示法
?K
?H
?G
F
?E
R
?D
C
?B
A 3 ?5
?6
0
0
1
2
3
4
5
6
7
8
9
1 ?2
8 ?97
0
1
2
3
4
5
6
7
8
9
4 A
4 B ?
4 C
0 D ?
-1 R
0 E ?
2 F
6 G ?
6 H ?
6 K ?
3 5 ?
0 1 2 ?
6 ?
7 8 9 ?
(a) 孩子链表
(b) 带双亲的孩子链表
45
树和森林 (cont’d)
(2) 树的双亲表示法
树结点数据存放到一个静态链表中，每个结点都保
存有双亲结点的下标。
#define N 100
typedef struct PTNode {
elemtype data;
int parent;// 双亲位置域
}PTNode;
typedef struct {
PTNode nodes[N];
int n; //结点数
}Ptree;
R -1
A 0
B 0
C 0
D 1
E 1
F 3
G 6
H 6
K 6
0
1
2
3
4
5
6
7
8
9
数组下标
R
B CA
F
H
D E
G K
data parent
以上存储结构大多情况下都使用静态链
表存放结点
46
树和森林 (cont’d)
(3) 树的二叉链表 (孩子－兄弟 )表示法
与二叉树链式存储结构相同，只不过含义不同：
左指针指向第一个孩子，右指针指向下一个兄弟
typedef struct CSNode {
int data;
struct CSNode *firstchild;
struct CSNode *nextsibling;
}CSNode,*CSTree;
?R
A
D? B?
?E? ?C
?F
G?
H?
K?二叉链表表示法
47
树和森林 (cont’d)
2、树和二叉树的转换规则
将树按照层序遍历，对于兄弟结点，第一个兄弟结
点作为双亲的左子树，其他兄弟结点作为前面兄弟结
点的右子树。
3、森林和二叉树的转换规则
首先将森林的每棵树都转化为二叉树
然后将每棵二叉树的根看作是兄弟，根结点作为前
面兄弟结点的右子树。
由二叉树向树和森林转化是上述过程的
逆过程
48
树和森林 (cont’d)
4、树和森林的遍历
(1) 树的层序遍历，从根开始，自上而下自左向右遍历
每个结点。
(2) 树的前序遍历，先访问根，然后自左向右依次前序
遍历每棵子树。
(3) 树的后序遍历，首先后序遍历每棵子树，最后访问
根
森林的遍历就是依次遍历每棵树的过程
49
6.8 哈夫曼树及其应用
1、基本概念
哈夫曼树, 最优树,分为二叉哈夫曼树和多叉哈夫
曼树。哈夫曼树是指树的带权路径长度最小的树。
路径长度,结点间路径上经过的分枝数目
树的路径长度,从根到其他结点路径长度总和
结点带权路径长度,结点的路径长度乘以结点的权
值
设 n个结点的二叉树，结点权值是 {W1,W2,..,Wn}，
每个结点的路径长度是 Li(i=1,2,…,n),那么这棵二叉树的
带权路径长度是：
当 WPL值最小时，就是 最优二叉树,也就是
二叉哈夫曼树 。
?
?
?
n
k
kkLWW P L
1
50
哈夫曼树及其应用 (cont’d)
2、哈夫曼树的应用实例：
假设我们需要通过网络传送字符串,ABACCDA”，就需
要对 ABCD四个字符进行编码，当然不能用 ASCII码，那
需要 7个字节 56位数据。因为只有 4个值需要传送，因此
只需要 2位数据就可以了，比如将 ABCD分别表示为 00、
01,10,11，这样只需要 14位数据。但如果将 ABCD作
为结点构建一棵下面的二叉树，将 ABCD结点路径上的 0
,1序列作为 ABCD的编码：
我们只需要 9位数据便可以了。根据定义，上面这棵
二叉树如果是哈夫曼树，整个编码长度将是最短的。
D
A
B
C
0
0
0 1
1
1
51
哈夫曼树及其应用 (cont’d)
3、哈夫曼树的建立算法
算法思想,
1）根据给定的权值 {w1,w2,···,wn}构造 n个二叉
树 F={T1,T2,···,Tn}每个 Ti只有一个根结点，权为
wi。
2）在 F中选取两棵根结点的权值最小的树构成
一棵新的二叉树，其根的权值为左 右子树根的
权值的和。
3） F中删去这两棵树，加上新得的树。
4）重复 2） 3）直到只剩一棵树。
52
哈夫曼树及其应用 (cont’d)
3、哈夫曼树的建立算法
5 36 4
A B C D C
7
56
A B D
C DBA
11 7
C DBA
18
53
#define N 20 //叶子结点编码的最大长度
typedef struct
{char ch; int weight; int lchild,rchild,parent;
}HTNODE; //哈夫曼树结点类型
typedef struct
{ char *code;
char leaf; }CODE; //叶编码类型
void hufcoding(HTNODE huftree[],CODE cd[],int w[],int n)
{ /*哈夫曼树存放在静态链表 huftree中,w存放结点权重，
按升序排列,n是叶子个数 */
int i,j,k,s1,s2,s,m,f,c,sum;
char temp[N]; //存放叶子编码字符串
m=2*n-1; //计算哈夫曼树的结点总数
for(i=1;i<=n;i++) //初始化静态链表，每个结点自成一棵树
{huftree[i].weight=w[i-1];
huftree[i].lchild=huftree[i].rchild=huftree[i].parent=0;
huftree[i].ch=getch();
}//for
哈夫曼树及其应用 (cont’d)
4、哈夫曼树的建立 (及编码 )算法
for(; <=m;i++)
{huftree[i].weight=0;
huftree[i].lchild=huf ree[i].rchild=huftree[i].parent=0;
}
k=0;
for(i=n+1;i<=m;i++) //生成 n-1个非叶子结点的循环
{s1=2*k+1; s2=s1+1; k++;
//s1,s2将是无双亲且权重最小的两个结点下标
sun=huftree[s1].weight+huftree[s2].weight;
j=i-1;
while(j>=s2+1&&s <huftree[j].weight)
{//将新生成的结点按照权重有序插入静态链表
huftree[j+1]=huftree[j]; j--;
}
huftree[j+1].weight=sum;
huftree[s1].parent=huftree[s2].parent=j+1;
huftree[j+1].lchild=s1; huftree[j+1].rchild=s2;
}//for
s=0; //开始求每个叶子结点的编码
for(i=1;i<=m;i++)
{c=0;
if(huftree[i].lchild==0&&huftree[i].rchild==0)
{j=i; //j是叶子结点下标
for(k=j,f=huftree[j].parent;f!=0;k=f,f=huftree[f].parent)
if(huftree[f].lchild==k){temp[c]='0';c++;}
else {temp[c]='1';c++;} //左分枝是 0右分枝是 1
cd[s].code=malloc(c+1);
cd[s].code[c]=0;
c--;
while(c>=0) cd[s].code[c]=temp[c--];
cd[s].leaf=huftree[j].ch;
s++;
if(s==n)break; //找到了所有的叶子结点了，结束
}//if
}// or
}
54
,数据结构,
第六章 树和二叉树
作业：
1,p233 一、复习 做书上
2,P234二、应用 4,5,6.做在作业本上
3、周四上机内容：串（简单文本编辑
器的制作，具体实习内容见周四的上机
要求）
内容提要
? 6.1 树的定义及基本术语
? 6.2 二叉树
? 6.3 编历二叉树
? 6.4 线索二叉树
? 6.5 二叉排序树
? 6.6 平衡二叉树
? 6.7 树和森林
? 6.8 哈夫曼树及应用
2
6.1 树的定义及基本术语
1、树的定义
(1)树的一般定义
树 是包含 n个结点的有限集合，在这个集合上定义了
一个唯一的关系，这个关系满足下面的条件：
I,存在唯一的一个结点，它没有前驱，称为根
II,除了根结点外，其它结点有且仅有一个前驱
III,除了根结点外，任何结点 ai(0? i?m)，都存在唯一
的一个从根到 ai的结点序列 a0,a1,a2,..,am,其中，
a0是根。这个序列称为从根到 ai的路径。a0
a1 a2 a3
a4 a5
3
树的定义及基本术语 (cont’d)
(2)树的递归定义
树 是包含 n个结点的有限集，在这个集合上定义了
唯一的关系，它满足下面的条件：
I,有个特定的称为根的结点；
II,当 n>1时，除了根以外的其余结点根据它们之间
的关系可分为 m个不相交的有限集 T1,T2,..,Tm，其中
，每个有限集都是一棵树。这些树称为根的子树。
a
b c d
e f
T1={b,e,f};T2={c};T3={d}
4
树的定义及基本术语 (cont’d)
(3)树的基本术语
1,根,唯一没有前驱的结点
2,度,结点的度 是结点的子树数目,树的度 是指结点
度的最大值
3,叶子,度为 0的结点，也称 终端结点
4,分枝结点,叶子之外的结点，也称非终端结点。
除了根以外的分枝结点又称内部结点。
5,双亲, 子女, 祖先, 子孙,结点子树的根称为结
点的子女，该结点就是它子女的双亲；某结点的
祖先是指从根到该结点的路径上的全部结点；结
点的子树中全部结点都是该结点的子孙。
a
b c d
e f
5
树的定义及基本术语 (cont’d)
(3)树的基本术语
6,兄弟、堂兄弟,同一个结点的子女互为兄弟，双
亲为兄弟的结点互称堂兄弟。
7,结点的 层次, 树的深度 (高度 )，根为第 1层，结点
的层次是其双亲层次加 1。树的深度是指结点的最
大层数。
8,有序树、无序树,如果结点的各子树自左向右是
有次序的，则称有序树，否则称无序树
9,森林, m棵互不相交的树就构成了森林。
a
b c d
e f g
第 1层
第 2层
第 3层
6
6.2 二叉树
1,二叉树的概念
每个结点最多有 2棵子树，并且子树有左右之
分，不能任意颠倒。
二叉树有 5种形态：
①空树 ②只有一个根
③只有左子树 ④只有右子树
⑤有两个子树
2,二叉树的性质
①在二叉树的第 i层上至多有 2i－ 1个结点 (i>=1)
② 深度为 k的二叉树至多有 2k-1个结点。
1
2 3
4 5 6 7
8 9
7
二叉树 (cont’d)
2,二叉树的性质
③ 设二叉树中，叶结点数为 n0,度为 1的结点数为 n1,度
为 2的结点数为 n2,则有,n0 = n2 + 1
因为 N=n0+n1+n2=1+n1*1+n2*2
④ 具有 n个结点的完全二叉树的深度为 ?log2n? +1
?log2n? 表示 log2n取整
满二叉树,具有最多结点数的二叉树（即一棵深度为
k且有 2k-1 个结点的二叉树）
完全二叉树,将满二叉树从右向左
删除叶子的结果，因此,
结点数 n<=2k-1，并且 n>2k-1-1
1
2 3
4 5 6 7
8 9
9
二叉树 (cont’d)
3,二叉树的存储结构
(1) 顺序存储,利用数组按照完全二叉树的方式
对结点编号，根据编号将结点存放在数组中相应
的位置中。
#define N 50 //二叉树的最大结点数
typedef elemtype SQTREE[N]; //顺序存储的二叉树
SQTREE bt;
A
B C
E F
1
2 3
4 5
6
A B C E F
0 1 2 3 4 5 6 7 8 9
10
二叉树 (cont’d)
3,二叉树的存储结构
(2)链式存储, 利用二叉链表或三叉链表
typedef struct treenode
{elemtype data; //结点数据
//指向左右孩子的指针
struct treenode *lchild,*rchild /*,*parent*/;
}TREENODE,*TREENODEPTR,*BTREE
A
B^ C ^
E ^^ F ^^
DATA
PARENT
LCHILD RCHILD
lchild data rchild
lcjild data parent rchild
11
＃ define N 50 //定义二叉树最大结点数
void createtree(BTREE *root)
{int value,front,rear; TREENODEPTR t,q[N];
//q是队列,front,rear是队头队尾下标。
scanf("%d",&value); //开始创建根结点
if(value==0){*root=NULL; return;};
//输入 0，表示空结点
*root=(TREENODEPTR)malloc(sizeof(TREENODE));
(*root)?data=value;
rear=front=1; q[front]=*root;
//根指针入队
二叉树 (cont’d)
4,二叉树的建立 (1) 按层序遍历顺序为输入顺序
while(front<=rear) //只要队列不空
{ t＝ q[front]; front++; //出队一结点指针
scanf("%d",&value);
if(value==0) t?lchild=NULL;
else
{t?lchild=(TREENODEPTR)malloc(sizeof(TREENODE));
t?lchild?data=value; //建立左孩子结点
rear++; q[rear]=t?lchild; //左孩子入队
}
scanf("%d",&value);
if(value==0) t?rchild=NULL;
else
{t?rchild=(TREENODEPTR)malloc(sizeof(TREENODE));
t?rchild?data=value; //建立左孩子结点
rear++; q[rear]=t?rchild; //左孩子入队
}
}//while }
5
3 4
7 9
12
广义表字符串输入的形式是：
A(B(,D),C(E,))
这是个递归输入方式，因此这样建立二叉树也
是个递归的过程。这里给出非递归的算法。
算法思想,
(1) 从左向右扫描字符串，遇到字母就建立结点；
(2) 遇到 (表示前面字母有孩子，要将前面字母
的结点入栈，以便将左右孩子与双亲链接起来。
(3) (后面的字母是左孩子，逗号后面的字母是
右孩子，遇到 )表示以栈顶结点为根的子树建立
完毕，出栈。
二叉树 (cont’d)
4.二叉树的建立 (2) 根据广义表字符串建立二叉树
A
B C
D E
13
#define N 50
void creattree(BTREE *root,char *str) //假设结点数据是字母
{TREENODEPTR t,s[N];
char *p; int top=0,n=0,tag; //s是栈,top是栈顶下标
p=str;
for(;*p;p++)
{switch(*p)
{case '(', top++; s[top]=t;
tag=1;break; //将前面结点入栈，准备链接左孩子
case ')',top--;break; //栈顶结点的子树创建完毕，出栈
case ',',tag=0;break; //准备链接右孩子
二叉树 (cont’d)
4.二叉树的建立 (2)根据广义表字符串建立二叉树
default,//常规字母，直接创建结点
t=(TREENODEPTR)malloc( izeof(TREENODE));
t?data=*p;
t?lchild=t?rchild=NULL; //默认情况下,左右孩子为空
if(n==0) //第一次创建的结点是整个树的根
{ *root=t; n++; }
else
{
if(tag) s[top]?lchild=t; //栈顶结点的左孩子是 t
else s[top]?rchild=t; //栈顶结点的右孩子是 t
}
}//switch
}//for
}
A
B C
D E
14
6.3 遍历二叉树
1,二叉树的遍历方式
(1) 先序遍历 (DLR)，先输出根，再遍历左子树，最后
遍历右子树
(2) 中序遍历 (LDR)，先遍历左子树，再输出根，最后
遍历右子树
(3) 后序遍历 (LRD)，先遍历左子树，再遍历右子树，
最后输出根
A
B C
D E
DLR：
LDR：
LRD：
A B D C E
ABD CE
ABD CE
15
遍历二叉树 (cont’d)
2,二叉树的遍历算法 (1)中序遍历
void inorder(BTREE root)
{
if(root!=NULL)
{ inorder(root?lchild);
printf("%d",root?data);
inorder(root?rchild);
}
}
递归算法
16
遍历二叉树 (cont’d)
2,二叉树的遍历算法 (2)先序遍历
void preorder(BTREE root)
{
if(root!=NULL)
{
printf("%d",root?data);
preorder(root?lchild);
preorder(root?rchild);
}
}
递归算法
17
遍历二叉树 (cont’d)
2,二叉树的遍历算法 (3)后序遍历
void postorder(BTREE root)
{
if(root!=NULL)
{
postorder(root?lchild);
postorder(root?rchild);
printf("%d",root?data);
}
}
递归算法
18
算法思想,
开始时栈空，当前处理的结点指向根，只要遍历未完成，
则执行下面的操作：
(1) 递归：只要当前不空，就将当前结点入栈，向左孩子
推进一步，直到最左端
(2) 循环执行以下操作：
如果栈顶结点有右子树，则向右推进一步，进入右
子树并跳出循环，转到 (1)。
如果栈顶是叶子，开始返回 (出栈，并输出结点信息 )，
这时需要区分从左子树返回还是从右子树返回。如
果从左边返回，则寻找栈顶结点的右子树，继续递
归；否则继续循环出栈返回，直到不再是右边返回
或者返回到根。
遍历二叉树 (cont’d)
2.二叉树的遍历算法 (4)后序遍历
非递归算法
19
#define N 50 //定义二叉树最大结点数
void postorder(BTREE root)
{TREENODEPTR p,s[N]; int top=0;
//s是栈,top是栈顶下标
p=root;
while(1)
{
while(p!=NULL) //递归的循环
{top++; s[top]=p; p=p?lchild;
} //一直向左递归,直到最左端
遍历二叉树 (cont’d)
2,二叉树的遍历算法 (4)后序遍历
while(1)
{ if(s[top]?rchild!=NULL) //如果是左返回
{ p=s[top]?rchild;
break; } //向右进一步，跳出循环，进入递归
//开始从右边返回,包括右子树不空的右返回
while(top!=0&&
(s[top]?rchild==NULL||p==s[top]?rchild))
{p= [t ]; to --; printf("%d ",p?data);}
if(top==0) return;
}//while(1)
}//while(1)
}
非递归算法
20
void preorder(BTREE root)
{ TREENODEPTR p,s[N]; int top=0;
p=root;
while(1)
{ while(p!=NULL) //一直向左递归
{ printf("%d ",p?data);
top++; s[top]=p;
p=p?lchild;
}
if(top!=0) //弹出栈顶，右孩子转去递归
{p=s[top]; top--; p=p?rchild; }
else return;
}
}
遍历二叉树 (cont’d)
2,二叉树的遍历算法 (5)先序遍历
非递归算法
21
层序的次序,
15 14 13 12 11 10 9 8
4 5 6 7
3 2
1
树的遍历必须从根开始，上述顺序可以看成是下面的反
序,1 2 3 7 6 5 4 8 9 10 11 12 13 14 15
算法思想,
先将根入栈，然后从第二层开始，交替地自左向右和自
右向左将结点入栈。
最根本地问题是不能将上层入栈的结点序列看成队列，
而应该看成栈。为了获取下一层结点，
不能将上层结点出队而是出栈！
遍历二叉树 (cont’d)
2,二叉树的遍历算法 (6) 层序遍历
自下而上
左右交替
的那种
15
14
13
12
11
10
9
8
4
5
6
7
3
2
1
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
即栈中栈
22
void layerorder(BTREE root)
{ TREENODEPTR p,s[N]; int top,bottom,m,n;
//根结点入栈，第一层结点的小栈只有一个结点
p=root; top=1; s[top]=p; bottom=top; //bottom是小栈底
while(1)
{ n=bottom; m=top; //准备将当前层结点出栈
bottom=top+1; //形成下一层结点的栈底
while(m>=n)
{ p=s[m]; m--; //出栈一结点
if(p?lchild!=NULL) //自左向右入栈
{top++; s[top]=p?lchild;}
if(p?rchild!=NULL)
{top++; s[top]=p?rchild;}
}//while(m
if(top==bottom-1)break;//如果这层没有结点,表明遍历结束
遍历二叉树 (cont’d)
(2)二叉树的遍历算法 (6) 层序遍历
n=bottom; m=top; //准备下一层处理
bottom=top+1;
while(m>=n)
{ p=s[m]; m--; //出栈一结点
if(p?rchild!=NULL) //自右向左栈
{top++; s[top]=p?rchild;}
if(p?lchild!=NULL)
{top++; s[top]=p?lchild;}
}//while(m
if(top==bottom-1)break;
}//while
wh le(top>=1)
{printf("%d ",]?data);top--;}
printf("\n");
}
4
5
6
7
3
2
1
bottom(旧 )
top
bottom
23
遍历二叉树 (cont’d)
3,二叉树遍历算法的应用 (1)求树的深度
int depth(BTREE root)
{ int hr,hl; //记录左右子树的深度
if(!root) return 0; //空树深度为 0
else {
hl=depth(root?lchild);
hr=depth(root?rchild);
if(hl>=hr) return hl+1;
else return lr+1;
}
}
24
void inorder(PTREENODEPTR root)
{ //root是三叉链表的二叉树
PTREENODEPTR p; int n=0; p=root; //记录叶子数量
while(1)
{ while(p?lchild) p=p?lchild; //一直向左递归
while(1) //循环返回
{ if(p?rchild!=NULL)
{p=p?rchild; break;} //进入右子树，继续递归
if(p?rchild==NULL&&p?lchild==NULL) n++;
while(p?parent!=NULL&&(p==p?parent?rchild||
p?parent?rchild==NULL))
p=p?parent;
if(p?parent==NULL) //返回到了根
{ printf("the tree has %d leafs\n",n); return;}
p=p?parent?rchild;break;
}//while(1)
}//while(1) }
遍历二叉树 (cont’d)
3,二叉树遍历算法的应用 (2)求二叉树叶子结点的个数
25
6.4 线索化二叉树
1,线索化
遍历二叉树的结果是将二叉树的结点排列成某种顺
序，使这些结点形成线性关系。但这种线性关系只能在
重新遍历二叉树时才会重新获得。如果在第一次遍历二
叉树时就将这种线性关系保存下来，这种操作称为,线
索化,。
为了将二叉树线索化，需要重新定义二叉树结点的
数据类型。
中序线索化结果
A
B C
D E
NULL NULLtypedef struct treenode
{ elemtype data;
struct treenode *lchild,*rchild;
int ltag,rtag; /*ltag为 0,lchild指向左孩子，否则指
向线索化序列中的前驱； rtag为 0,rchild指向右孩子，
否则指向线索化序列中的后继 */
}TREENODE,*TREENODEPTR;
26
线索化二叉树 (cont’d)
0 lchild域指示结点的左孩子
ltag =
1 lchild域指示结点的前驱
0 rchild域指示结点的右孩子
rtag =
1 rchild域指示结点的后继
以这种结点结构构成的二叉链表作为二叉树的存储
结构，叫做 线索链表,其中指向结点前驱和后继的指针
，叫做 线索 。加上线索的二叉树称之为 线索二叉树 。对
二叉树以某种次序遍历使其变为线索二叉树的过程叫做
线索化 。
中序线索化结果
A
B C
D E
NULL NULL
lchild ltag data rtag rchild
27
TREENODEPTR pre;
void inordthread(TREENODEPTR *thrt,TREENODEPTR t)
{//为线索化后的树增加一个头结点 thrt，便于操作
(*thrt)=(TREENODEPTR)malloc(sizeof(TREENODE));
(*thrt)?ltag=0; (*thrt)?ltag=1;
(*thrt)?rchild=(*thrt); //开始右线索指向自身
if(t==NULL) //如果树 t为空，左指针也指向自己
(*thrt)?lchild=(*thrt);
else { //前驱指针指向线索头结点
(*thrt)?lchild=t; pre=(*thrt);
inthreading(t); //开始线索化
//线索化后,pre为最右端结点,它的后继指向头结点
pre?rchild=(*thrt); pre?rtag=1;
(*thrt)?rchild=pre; //头结点右线索指向最右结点
}
}
线索化二叉树 (cont’d)
2,线索化算法 (以中序线索为例 )：
void inthreading(TREENODEPTR p)
{/*对以 p为根的二叉树进行中序线索化 */
if(p)
{//在线索化过程中,pre一直是当前访问结点的前驱结点
inthreading(p?lc ild);
//p的左孩子为空,则指向前驱
if(p?lchild==NULL)
{p?ltag=1;
p?lchild=pre;}
//访问 p时，并不知道 p的后继
if(pre?rchild==NULL)
{pre?rtag=1;
pre?rchild=p;} //将 re的右孩子指向后继
pre=p; //进入右子树前，将前驱指针指向当前结点
inthreading(p?rchild);
}
}
A
B C
D E
28
void tinorder(TREENODEPTR thrt)
{//thrt是线索二叉树的头结点指针
TREENODEPTR p;
p=thrt?lchild; //p指向根
while(p!=thrt) //当遍历到最后有 p=thrt
{while(p?ltag==0)
p=p?lchild; //寻找最左端结点
printf("%d",p?data);
while(p?rtag==1&&p?rchild!=thrt)
{//顺着后继链，访问后继，直到后继链断掉
p=p?rchild;
printf("%d",p?data);}
p=p?rchild;
//转到上面寻找后继,p的后继就是 p的右子树最左端结点
}
}
线索化二叉树 (cont’d)
3,利用线索遍历二叉树 (以中序为例 )：
A
B C
D E
29
6.5 二叉排序树
1.二叉排序树,又称 二叉查找树 。二叉排序树或者是棵空
树，或者是棵具有下面特征的二叉树：
(1) 若它的左子树不空，左子树上的所有结点值都小
于 (大于 )根结点值
(2) 若它的右子树不空，右子树上的所有结点值都大
于 (小于 )根结点值
(3) 左右子树也都是二叉排序树
20
16 40
11 36 43
8 14 25 38
30
BTREE insert(BTREE root,int value)
{//将 value插入到二叉排序树 root中，将新的树返回
TREENODEPTR p,q,r;
r=(TREENODEPTR)mallloc(sizeof(TREENODE));
r?data=value; r?lchild=r?rchild=NULL;
if(root==NULL) return r;
p=root;
while(p)
{ q=p; //记下插入的位置
if(p?data > value) p=p?lchild; //向左子树方向插
else p=p?rchild; //向右子树方向插
}//while
if(q?data > value) q?lchild=r;
else q?rchild=r;
return root;
}
二叉排序树 (cont’d)
2、二叉排序树的建立算法
creattree(BTREE roo )
{
int value;
scanf("%d",&value);
while(value) //输入 0表示结束
{
root=insert(root,value);
scanf("%d",&value);
}
return root;
}
31
TREENODEPTR search(TREENODE root,TREENODEPTR
*f,int value)
{/*在二叉排序树 root中查找值是 value的结点，返回结点指
针，并用 f返回该结点双亲结点 */
TREENODEPTR p,q,r;
q=NULL; p=root;
while(p&&p?data!=value)
{q=p;
if(p?data>value) p=p?lchild;
else p=p?rchild;
}
*f=q;
return p;
}
二叉排序树 (cont’d)
3、二叉排序树的查找算法
32
算法思想,
由于删除结点后，二叉排序树仍必须是二叉排序树，并且最
好不增加树的深度，因此应该区分三种情况 (假设 P是要删除
的结点 )：
(1) 如果 P是叶子结点，直接删除即可
(2) 如果 P是单枝结点，可以直接用子树的根
代替 P做 P双亲的孩子
(3) 如果 P是双枝结点，则可以用 P的前驱或后继结点
H替换 P，然后在删除 H，对 H的删除必然属于 (1)(2)
两种情况。
二叉排序树 (cont’d)
4、二叉排序树的删除算法
F
P+
F
P+
H+
F
P+
H
+
F
P
H
S
C
33
BTREE delete(BTREE root,int value)
{//在二叉排序树中删除值是 value的结点，返回删除后的树
TREENODEPTR f,p,q,h;
p=search(root,&f,value); //f将是 p的双亲结点指针
if(p==NULL)return root;
if(p?lchild==NULL||p ? rchild==NULL) //p是叶子
h=NULL; //h将替代 p
else if(p?lchild==NULL) h=p?rchild;
else if(p?rchild==NULL) h=p?lchild;
二叉排序树 (cont’d)
4、二叉排序树的删除算法
else //p是双枝结点
{f=p; q=p ? rchild; //开始寻找 p的后继 q,f将是 q的双亲
while(q?lchild!=NULL)
{f=q; q=q?lchild; }
p?data=q?data; //将 q的数据复制到 p中，开始删除 q
if(q?lchild==NULL||q?rchild==NULL)h=NULL;
else if(q?lchild==NULL)h=q?rchild;
else h=q?lchild;
p=q; //p成为 f的子女
} //else
if(f==NULL) root=h;
else if(f?lchild==p) f?lchild=h;
else f?rchild=h;
free(p);
return root;
}
34
6.6 平衡二叉树
1、平衡二叉树, AVL树,左右子树的深度差的绝对
值不超过 1的二叉排序树，并且左右子树也是平衡二
叉树。
平衡二叉树的查找效率最高，因为 n个结点的二
叉树中，平衡二叉树的深度最低。二叉排序树的
深度决定了查找比较的次数。
平衡二叉树
非平衡二叉树
35
平衡二叉树 (cont’d)
2、平衡二叉树的平衡调整
当向平衡二叉树插入结点或删除结点时，会导致某棵
子树深度的变化，在某些情况下，就会导致平衡二叉树
失去平衡。这时就需要对二叉树进行平衡调整。
下面以插入结点为例，平衡调整需要两种旋转操作：
单旋 和 双旋 。
当插入新节点时,AVL树的根与插入位置之间路径上
的节点的平衡状态可能会变化。因此，插入完一个新节
点后，要沿着通向根的路径回溯，检查各节点的平衡状
态，一旦发现不平衡节点，就进行平衡化旋转。这样会
将不平衡限制最小范围内，并且通常每插入一个节点最
多需要一次调整。
36
平衡二叉树 (cont’d)
从发生不平衡的节点开始，沿回溯路径向下取两层节
点。
(1) 如果这三个节点成一条直线，则需要采用单旋进
行平衡化。 左旋是指将线上最左端节点向下旋转，右旋
是指将线上最右端节点向下旋转。
(2) 如果这三个节点成一条折线，则需要采用双旋进
行平衡化。
为了判断旋转的情况，我们将结点的左右子
树的深度差定义为“平衡因子”。当平衡因
子是正负 2时，该结点失去平衡。
37
平衡二叉树 (cont’d)
(1) 左单旋的情况
原来的 AVL树
插入一结点,A点不平衡
左单旋的结果
void LeftRotate(TREENODEPTR * Ptr)
{ //Ptr是发生不平衡的结点
TREENODEPTR *tmp=(*Ptr)?rchild;
(*Ptr)?rchild=tmp?lchild;
tmp?lchild=*Ptr;*Ptr=tmp;
}
38
平衡二叉树 (cont’d)
(2) 右单旋的情况
void RightRotate(TREENODEPTR * Ptr)
{ TREENODEPTR tmp=(*Ptr)?lchild;
(*Ptr)?lchild=tmp?rchild;
tmp?rchild=*Ptr;
*Ptr=tmp;
}
原来的 AVL树 插入一结点,A点不平衡 右单旋的结果
39
平衡二叉树 (cont’d)
(3) 先左后右双旋的情况
void LeftRightRotate(TREENODEPTR * Ptr)
{ LeftRotate(&(*Ptr)?lchild);
RightRotate(Ptr);
}
原来的 AVL树 插入一结点,A点不平衡
先左旋
再右旋
40
平衡二叉树 (cont’d)
(4) 先右后左双旋的情况
void RightLeftRotate(TREENODEPTR * Ptr)
{ RightRotate(&(*Ptr)?rchild);
LeftRotate(Ptr);
}
原来的 AVL树 插入一结点,A点不平衡
先右旋
再左旋
41
typedef struct node
{int data;
struct node *lchild,*rchild;
int balance; //平衡因子
}TREENODE,*TREENODEPTR;
int Insert(TREENODEPTR * root,int x)
{ //返回值表明树是否长高
int taller;
if(*root==NULL)
{*root=(TREENODEPTR)malloc(sizeof(TREENODE));
(*root)?data=x;
(*root)?balance=0;
return 1;
}
6,向 AVL树
插入结点
else if(x>(*root)?data){ taller=Insert(&(*root)?rchild,x);
if(taller==1) //右子树长高了
switch((*root)?balance)
{case 0:(*root)?balance=1;break;
case -1:(*root)?balance=0;taller=0;break;case 1,
//应该左旋或者先右后左双旋
if((*root)?rchild?balance==1)
{ //应该左旋，并调整平衡因子
LeftRotate(root);(*root)?balance=0;
(*root)?lchild?balance=0;}else if((*root)?rchild?balance==-1)
{ //应该双旋，并调整平衡因子
if((*root)?rchild?lchild?balance==1)
{(*root)?balance=-1;
(*root)?rchild?balance=0;}else {(*root)?balance=0;
(*root)?rchild?balance=1;}
(*root)?rchild?lchild?balance=0;
RightLeftRotate(root);
}taller=0;break;
//平衡了,没长高 }//switch
return taller; }//else if
<(
{ t ll r rt( r ) l il );
if(taller==1)//左子树长高了
switch((*root) balance)
{case 0:(*root) balance=-1;break;
case 1:(*root)?balance=0;taller=0;break;
case -1,//应该右旋或者先左后右双旋
if((*root)?lchild?balance== -1) //右旋
{RightRotate(root);(*root)?balance=0;
(*root)?rchild?balance=0;}
else if((*root) lchild balance==1) //双旋
{if((*root)?lchild?rchild?balance==1)
{(*root)?balance=0;
(*root)?lchild?balance=-1;}
else {(*root) balance=1;
(*root)?lchi d?balance=0;}
(*root)?lchild?rchild?balance=0;
LeftRightRotate(root);
}
taller=0;break; //平衡了，没长高 }//switch
return taller; }
return 0;}
42
6.7 树和森林
1、树的存储结构
(1) 孩子表示法
(2) 孩子－双亲表示法
(3) 双亲表示法
(4) 二叉链表法
43
树和森林 (cont’d)
(1) 树的孩子表示法和孩子 -双亲表示法
树结点中存放有孩子结点的指针的线性表以及双亲
指针。孩子指针线性表可以是顺序表或者链表。
typedef struct CTNode{//孩子结点
int child;
struct CTNode *next;
} *ChildPtr;
Typedef struct {
elemtype data;
ChildPtr firstchild;//孩子链表头指针
}CTBox;
Typedef struct {
CTBox nodes[N];
int n,r; //结点数和根的位置；
}Ctree;
R
B CA
F
H
D E
G K
44
树和森林 (cont’d)
(1) 树的孩子表示法和孩子 -双亲表示法
?K
?H
?G
F
?E
R
?D
C
?B
A 3 ?5
?6
0
0
1
2
3
4
5
6
7
8
9
1 ?2
8 ?97
0
1
2
3
4
5
6
7
8
9
4 A
4 B ?
4 C
0 D ?
-1 R
0 E ?
2 F
6 G ?
6 H ?
6 K ?
3 5 ?
0 1 2 ?
6 ?
7 8 9 ?
(a) 孩子链表
(b) 带双亲的孩子链表
45
树和森林 (cont’d)
(2) 树的双亲表示法
树结点数据存放到一个静态链表中，每个结点都保
存有双亲结点的下标。
#define N 100
typedef struct PTNode {
elemtype data;
int parent;// 双亲位置域
}PTNode;
typedef struct {
PTNode nodes[N];
int n; //结点数
}Ptree;
R -1
A 0
B 0
C 0
D 1
E 1
F 3
G 6
H 6
K 6
0
1
2
3
4
5
6
7
8
9
数组下标
R
B CA
F
H
D E
G K
data parent
以上存储结构大多情况下都使用静态链
表存放结点
46
树和森林 (cont’d)
(3) 树的二叉链表 (孩子－兄弟 )表示法
与二叉树链式存储结构相同，只不过含义不同：
左指针指向第一个孩子，右指针指向下一个兄弟
typedef struct CSNode {
int data;
struct CSNode *firstchild;
struct CSNode *nextsibling;
}CSNode,*CSTree;
?R
A
D? B?
?E? ?C
?F
G?
H?
K?二叉链表表示法
47
树和森林 (cont’d)
2、树和二叉树的转换规则
将树按照层序遍历，对于兄弟结点，第一个兄弟结
点作为双亲的左子树，其他兄弟结点作为前面兄弟结
点的右子树。
3、森林和二叉树的转换规则
首先将森林的每棵树都转化为二叉树
然后将每棵二叉树的根看作是兄弟，根结点作为前
面兄弟结点的右子树。
由二叉树向树和森林转化是上述过程的
逆过程
48
树和森林 (cont’d)
4、树和森林的遍历
(1) 树的层序遍历，从根开始，自上而下自左向右遍历
每个结点。
(2) 树的前序遍历，先访问根，然后自左向右依次前序
遍历每棵子树。
(3) 树的后序遍历，首先后序遍历每棵子树，最后访问
根
森林的遍历就是依次遍历每棵树的过程
49
6.8 哈夫曼树及其应用
1、基本概念
哈夫曼树, 最优树,分为二叉哈夫曼树和多叉哈夫
曼树。哈夫曼树是指树的带权路径长度最小的树。
路径长度,结点间路径上经过的分枝数目
树的路径长度,从根到其他结点路径长度总和
结点带权路径长度,结点的路径长度乘以结点的权
值
设 n个结点的二叉树，结点权值是 {W1,W2,..,Wn}，
每个结点的路径长度是 Li(i=1,2,…,n),那么这棵二叉树的
带权路径长度是：
当 WPL值最小时，就是 最优二叉树,也就是
二叉哈夫曼树 。
?
?
?
n
k
kkLWW P L
1
50
哈夫曼树及其应用 (cont’d)
2、哈夫曼树的应用实例：
假设我们需要通过网络传送字符串,ABACCDA”，就需
要对 ABCD四个字符进行编码，当然不能用 ASCII码，那
需要 7个字节 56位数据。因为只有 4个值需要传送，因此
只需要 2位数据就可以了，比如将 ABCD分别表示为 00、
01,10,11，这样只需要 14位数据。但如果将 ABCD作
为结点构建一棵下面的二叉树，将 ABCD结点路径上的 0
,1序列作为 ABCD的编码：
我们只需要 9位数据便可以了。根据定义，上面这棵
二叉树如果是哈夫曼树，整个编码长度将是最短的。
D
A
B
C
0
0
0 1
1
1
51
哈夫曼树及其应用 (cont’d)
3、哈夫曼树的建立算法
算法思想,
1）根据给定的权值 {w1,w2,···,wn}构造 n个二叉
树 F={T1,T2,···,Tn}每个 Ti只有一个根结点，权为
wi。
2）在 F中选取两棵根结点的权值最小的树构成
一棵新的二叉树，其根的权值为左 右子树根的
权值的和。
3） F中删去这两棵树，加上新得的树。
4）重复 2） 3）直到只剩一棵树。
52
哈夫曼树及其应用 (cont’d)
3、哈夫曼树的建立算法
5 36 4
A B C D C
7
56
A B D
C DBA
11 7
C DBA
18
53
#define N 20 //叶子结点编码的最大长度
typedef struct
{char ch; int weight; int lchild,rchild,parent;
}HTNODE; //哈夫曼树结点类型
typedef struct
{ char *code;
char leaf; }CODE; //叶编码类型
void hufcoding(HTNODE huftree[],CODE cd[],int w[],int n)
{ /*哈夫曼树存放在静态链表 huftree中,w存放结点权重，
按升序排列,n是叶子个数 */
int i,j,k,s1,s2,s,m,f,c,sum;
char temp[N]; //存放叶子编码字符串
m=2*n-1; //计算哈夫曼树的结点总数
for(i=1;i<=n;i++) //初始化静态链表，每个结点自成一棵树
{huftree[i].weight=w[i-1];
huftree[i].lchild=huftree[i].rchild=huftree[i].parent=0;
huftree[i].ch=getch();
}//for
哈夫曼树及其应用 (cont’d)
4、哈夫曼树的建立 (及编码 )算法
for(; <=m;i++)
{huftree[i].weight=0;
huftree[i].lchild=huf ree[i].rchild=huftree[i].parent=0;
}
k=0;
for(i=n+1;i<=m;i++) //生成 n-1个非叶子结点的循环
{s1=2*k+1; s2=s1+1; k++;
//s1,s2将是无双亲且权重最小的两个结点下标
sun=huftree[s1].weight+huftree[s2].weight;
j=i-1;
while(j>=s2+1&&s <huftree[j].weight)
{//将新生成的结点按照权重有序插入静态链表
huftree[j+1]=huftree[j]; j--;
}
huftree[j+1].weight=sum;
huftree[s1].parent=huftree[s2].parent=j+1;
huftree[j+1].lchild=s1; huftree[j+1].rchild=s2;
}//for
s=0; //开始求每个叶子结点的编码
for(i=1;i<=m;i++)
{c=0;
if(huftree[i].lchild==0&&huftree[i].rchild==0)
{j=i; //j是叶子结点下标
for(k=j,f=huftree[j].parent;f!=0;k=f,f=huftree[f].parent)
if(huftree[f].lchild==k){temp[c]='0';c++;}
else {temp[c]='1';c++;} //左分枝是 0右分枝是 1
cd[s].code=malloc(c+1);
cd[s].code[c]=0;
c--;
while(c>=0) cd[s].code[c]=temp[c--];
cd[s].leaf=huftree[j].ch;
s++;
if(s==n)break; //找到了所有的叶子结点了，结束
}//if
}// or
}
54
,数据结构,
第六章 树和二叉树
作业：
1,p233 一、复习 做书上
2,P234二、应用 4,5,6.做在作业本上
3、周四上机内容：串（简单文本编辑
器的制作，具体实习内容见周四的上机
要求）
