计算机软件基础
3,2 树一．树的定义树 是由 n（ n≥0） 个结点构成的有限集合 。
当 n=0时称为空树；否则,任意一棵非空树必符合以下两个条件：
1） 树中有且仅有一个特定的称为根的结点；
2）除根结点外，其余结点可分为 m个互不相交的有限集合 T1,T2,T3,?,Tm,其中每一个集合本身又是一棵树，称之为根的子树。
计算机软件基础
树的主要特点 （形态与自然界中的树十分相似）
1.只有一个根结点
2,结点分布呈明显的层次关系
3,递归定义
B C D
E HF
A
G I
树的示意图
计算机软件基础
树的逻辑结构分析,对于树中的任意结点来说，若其为根结点，则其无双亲结点；若其为叶子，则其无孩子结点；否则，此结点有且仅有一个双亲结点，并且有若干个孩子结点。
结论,树中结点的逻辑关系是一种一对多的关系，体现在一个结点只能有一个双亲，
但可以有多个孩子。
计算机软件基础
二、树的有关术语
结点的度,每个结点的子树个数 。
树的度,树中所有结点的度的最大值 。
叶子,又称终端结点,是指度为 0的结点 。
分支结点,又称非终端结点,度不为 0的结点 。
双亲和孩子,一个结点的子树的根结点称为此结点的孩子；若结点 1是结点 2的孩子,则结点 2
就被称为是结点 1的双亲 。
结点的层次,规定根为第一层,其下面的一层为第二层,依次类推 。
计算机软件基础
树的深度,树中结点的最大层次数 。
兄弟和堂兄弟,同一双亲的孩子之间互称兄弟；
其双亲在同一层的结点互为堂兄弟 。
有序树和无序树,如果树中任一结点的各个子树规定从左到右是有次序的,即不能互换位置,
则称该树为有序树,否则称为无序树 。
森林,由 m（ m≥0） 棵互不相交的树构成的集合 。
计算机软件基础三,二叉树
1,二叉树的定义二叉树是一个由 n（ n≥0） 个结点构成的有限集合，它或者为空树，或者是由一个根结点和两个分别被称为左子树和右子树的互不相交的子集构成的，其左、右子树也是二叉树。
计算机软件基础
B C
D E
G
F
H
A
二叉树示意图
二叉树的特点
（ 1） 度小于等于 2,即树中不存在度大于 2的结点；
（ 2）有序树，即每个结点的子树有左右之分，
不能交换。
计算机软件基础
2,二叉树的性质
（ 1） 二叉树的第 i层上至多有 2i-1个结点 。
（ 2） 深度为 k的二叉树的结点总数至多为 2k -1
个 。
（ 3） 若一棵二叉树上度为 0（ 叶子 ） 和度为 2的结点数分别为 n0和 n2，
则,n0=n2+1。
计算机软件基础
3,特殊的二叉树
（ 1）满二叉树若一棵二叉树的深度为 k,其结点总数为 2k -1
个，则称此二叉树为满二叉树。
B C
D E G
A
F
满二叉树示例
计算机软件基础
（ 2）完全二叉树若一棵深度为 k,具有 n个结点的二叉树，能够与一棵同深度的满二叉树中编号从 1 到 n的结点（从上到下，从左到右编号）相对应，则称此二叉树为完全二叉树。
B C
D E
A
完全二叉树示例思考：
深度为 3的完全二叉树有几种形态？
计算机软件基础
完全二叉树的性质：
[性质 1] 一棵具有 n个结点的完全二叉树的深度为?log2n? +1。
[性质 2] 若一棵完全二叉树中共有 n个结点,
对于其中编号为 i（ 1≤i≤n） 的结点,有：
1） 若 i≠1,则 i结点的双亲结点为?i/2? ； 若
i=1,则其为根结点,无双亲 。
2） 若 2i≤n,则 i结点的左孩子为 2i； 若 2i>n，
则 i结点无左孩子 。
3）若 2i+1≤n,则 i结点的右孩子为 2i+1； 若
2i+1>n,则 i结点无右孩子。
计算机软件基础若一棵二叉树中每个结点的左,右子树的深度之差 （ 平衡因子 ） 均不大于 1，
则称该二叉树为平衡二叉树 。
（ 3）平衡二叉树
B C
D E
A
F
平衡二叉树示例
计算机软件基础
三种特殊二叉树之间的关系满二叉树 完全二叉树平衡二叉树
计算机软件基础
4,二叉树的存储
（ 1）顺序存储结构实现方法,二叉树的顺序存储结构是用一组地址连续的存储单元依次（从上到下，从左到右）存放二叉树中的各个结点的数据信息，
借助于各个结点在存储结构中存放的相对位置来反映其逻辑关系。
适用范围,只适合 完全二叉树 。
计算机软件基础
B C
D E F G
A
IH J
例：对如下完全二叉树进行顺序存储。
A B C D E F G H I J
1 2 3 4 5 6 7 8 9 10
计算机软件基础思考：如何设法将顺序存储方法扩展应用于一棵非完全二叉树？
A
B C
D E F
G H
A
B C
D E F
G H
A B C D E F G H
1 2 3 4 5 6 7 8 9 10 11 12 13 14
添加虚结点
计算机软件基础
分析以上采用的存储方法的利弊。
结论：
虽然通过添加虚结点的办法可将一棵普通二叉树构造成一棵完全二叉树并对其进行顺序存储，但这种做法既繁琐，又造成了大量存储空间的浪费，故该方法在实际工作中很少被使用。
lchild data rchild
计算机软件基础
（ 2）链式存储结构实现方法,二叉树的链式存储结构中最常用的是二叉链表，其结点结构包括三个域，其中一个是数据域，用于存放结点的数据值；
另外两个是指针域，分别存放该结点的左孩子和右孩子的地址。除此之外，为了存储根结点的地址，还需设立一个指针变量 tree。
计算机软件基础 F ∧
∧
A
B C
D∧ E∧ ∧
tree
G∧ ∧ H∧ ∧
A
B C
D E F
HG
例：对如下二叉树采用二叉链表方式进行链式存储。
二叉树示意图 链式存储示意图
计算机软件基础
二叉链表中结点类型的定义：
注意,datatype在此处代表任意数据类型，实现时应根据结点的实际数据类型用对应的类型标识符代替。
lchild data rchild
计算机软件基础
typedef struct node
{ datatype data;
struct node * lchild,* rchild;
}bstree；
计算机软件基础
5,二叉树的遍历
遍历是二叉树所有算法中最重要和最基本的算法。
遍历是指按照一定的顺序访问二叉树中的所有结点，使得每个结点都能被访问且仅访问一次。这里所谓的访问有很广的含义，可以是对结点的各种操作，如修改、计算、输出等。
计算机软件基础
（ 1）先（根）序遍历
具体遍历过程：
若遍历的二叉树不为空,依次执行以下操作：
1） 访问根结点；
2） 先序访问左子树；
3）先序访问右子树；
计算机软件基础
B C
D E
G
F
H
A
E
G
例：写出对下面的二叉树进行先序遍历的序列。
先序遍历序列,A B D E G H C F
计算机软件基础
算法实现 (假定结点的值为字符型 )
void preorder (bstree?p)
{
if (p!=NULL)
{ printf(“%5c”,p->data); /*访问根结点 */
preorder(p->lchild); /*先序遍历左子树 */
preorder(p->rchild); /*先序遍历右子树 */
}
}
计算机软件基础
B C
D E
A
P
第 0层递归 (根结点 ),p!=NULL 输出 p->data
A
跟踪遍历算法的执行过程：
计算机软件基础
B C
D E
AP
A B
第 1层递归 (左子树 ),p!=NULL 输出 p->data
计算机软件基础
B C
D E
A
P==NULL
第 2层递归 (左子树 ->左子树 ),p==NULL 递归结束,返回上一层递归断点处
A B
计算机软件基础
B C
D E
A
第 1层递归 (左子树 ),进入下一层递归,访问右子树
A B
计算机软件基础
B C
D E
A
P==NULL
第 2层递归 (左子树 ->右子树 ),p==NULL 递归结束,返回上一层递归断点处
A B
计算机软件基础
B C
D E
A
第 1层递归 (左子树 ),递归结束,返回上一层断点处
A B
计算机软件基础
B C
D E
A
第 0层递归 (根结点 ),进入下一层递归,访问右子树
A B
计算机软件基础
B C
D E
A
P
第 1层递归 (右子树 ),p!=NULL 输出 p->data
A B C
计算机软件基础
B C
D E
A
P
第 2层递归 (右子树 ->左子树 ),p!=NULL 输出
p->data
A B C D
计算机软件基础
B C
D E
A
第 3层递归 (右子树 ->左子树 ->左子树 ),
p==NULL 递归结束 返回上一层递归断点处
P==NULL
A B C D
计算机软件基础
B C
D E
A
第 2层递归 (右子树 ->左子树 ):进入下一层递归,访问右子树
A B C D
计算机软件基础
B C
D E
A
第 3层递归 (右子树 ->左子树 ->右子树 ),
p==NULL 递归结束 返回上一层递归断点处
P==NULL
A B C D
计算机软件基础
B C
D E
A
第 2层递归 (右子树 ->左子树 ):递归结束,返回上一层递归断点处
A B C D
计算机软件基础
B C
D E
A
第 1层递归 (右子树 ):进入下一层递归,访问右子树
A B C D
计算机软件基础
B C
D E
A
P
第 2层递归 (右子树 ->右子树 ),p!=NULL 输出
p->data
A B C D E
计算机软件基础
B C
D E
A
第 3层递归 (右子树 ->右子树 ->左子树 ),
p==NULL 递归结束 返回上一层递归断点处
P==NULL
A B C D E
计算机软件基础
B C
D E
A
第 2层递归 (右子树 ->右子树 ):进入下一层递归,访问右子树
A B C D E
计算机软件基础
B C
D E
A
第 3层递归 (右子树 ->右子树 ->右子树 ),
p==NULL 递归结束 返回上一层递归断点处
P==NULL
A B C D E
计算机软件基础
B C
D E
A
第 2层递归 (右子树 ->右子树 ):递归结束,返回上一层递归断点处
A B C D E
计算机软件基础
B C
D E
A
第 1层递归 (右子树 ->右子树 ),递归调用结束返回上一层递归断点处
A B C D E
计算机软件基础
B C
D E
A
第 0层递归 (根结点 ),遍历函数结束
A B C D E （ 结束）
计算机软件基础
（ 2）中（根）序遍历
具体遍历过程：
若遍历的二叉树不为空,依次执行以下操作：
1） 中序访问左子树；
2） 访问根结点；
3）中序访问右子树；
例：写出对下面的二叉树进行中序遍历的序列。
计算机软件基础
B C
D E
G
F
H
A
E
G
中序遍历序列,D B G E H A C F
计算机软件基础
算法实现：
void inorder (bstree?p)
{ if (p!=NULL)
{ inorder(p->lchild); /*中序遍历左子树 */
printf(“%5c”,p->data); /*访问根结点 */
inorder(p->rchild); /*中序遍历右子树 */
}
}
算法思想：
与先序遍历算法类似，也采用递归方法实现。
计算机软件基础
（ 3）后（根）序遍历
具体遍历过程：
若遍历的二叉树不为空,依次执行以下操作：
1） 后序访问左子树；
2）后序访问右子树；
3）访问根结点；
计算机软件基础
例：写出对下面的二叉树进行后序遍历的序列。
B C
D E
G
F
H
A
E
G
后序遍历序列,D G H E B F C A
计算机软件基础
算法实现：
void postorder (bstree?p)
{ if (p!=NULL)
{ postorder(p->lchild); /*后序遍历左子树 */
postorder(p->rchild); /*后序遍历右子树 */
printf(“%5c”,p->data); /*访问根结点 */
}
}
算法思想：
与先、中序遍历算法类似，也采用递归方法实现。
计算机软件基础
思考题：
若已知一棵二叉树的中序遍历序列为,D B G E H A C F
后序遍历序列为,D G H E B F C A
请根据这两种遍历序列的规律，得到对应的二叉树并写出其先序遍历序列。
说明：只要二叉树的两种遍历序列确定，其对应的二叉树就确定下来，且对应的二叉树是唯一的。
计算机软件基础四．树的存储结构只能采用链式存储结构，最常用的方法称为孩子 —兄弟表示法。
first data next
实现方法,每个结点包括三个域，其中一个是数据域，用于存放结点的数据值；另外两个是指针域，分别存放该结点的第一个孩子和下一个相邻兄弟的的地址。除此之外，为了存储根结点的地址，还需设立一个指针变量 tree。
计算机软件基础
B C D
E GF
A
F∧ ∧
A
B
D ∧
G∧ ∧
E∧ C∧
∧
tree
例：对下面的树采用孩子 —兄弟法进行存储。
树及其链式存储示意图
计算机软件基础五．树的遍历
1,先（根）序遍历
具体遍历过程：
若遍历的树不为空,依次执行以下操作：
① 访问根结点；
② 从左到右依次先序访问各个子树；
计算机软件基础
B C D
E GF
A
例：写出对下面的树进行先序遍历的序列。
先序遍历序列,A B E F C D G
计算机软件基础
2,后（根）序遍历
具体遍历过程：
若遍历的树不为空,依次执行以下操作：
① 从左到右依次后序访问各个子树；
② 访问根结点；
计算机软件基础
B C D
E GF
A
例：写出对下面的树进行后序遍历的序列。
后序遍历序列,E F B C G D A
计算机软件基础
树的遍历算法
分析：
1.树的孩子 —兄弟链式存储结构和二叉树的链式存储结构在存储形式上是完全相同的，都是二叉链表的形式；
2,对树作先序和后序遍历分别与对其孩子 —兄弟链式存储生成的二叉链表作先序和中序遍历的结果相同 。
结论：
对树进行先序和后序遍历可分别通过调用二叉树的先序和中序遍历算法实现。
计算机软件基础六,树、森林与二叉树的转换
转换的基本思想,
按照孩子 —兄弟法建立起树、森林与二叉树的一一对应关系。
具体实现方法：
1,分析法
2,作图法
计算机软件基础
转换步骤：
（ 1） 在原树所有兄弟结点之间加一连线；
（ 2） 对每个结点,除保留与其长子间的连线外,将该结点与其余孩子间的连线全部抹除；
（ 3） 以根结点为轴心,顺时针旋转 45o；
将树转换为二叉树
计算机软件基础
B C D
E GF
A
连线
B C D
E GF
A
抹线
B C D
E GF
A
A
旋转
例：将下面的树转换成对应的二叉树。
计算机软件基础
将森林转换为二叉树
转换步骤：
与树转换成二叉树的过程类似 。
注意：
（ 1） 森林中各棵树的根结点互为兄弟 。
（ 2） 旋转时以第一棵树的根结点为轴心 。
计算机软件基础
G
HB C
D F
A
E
I
J LK
G
HB C
D F
A
E
I
J LK
连线
B
C
A
G
H I
J
L
K
D
F
E
旋转
G
HB C
D F
A
E
I
J LK抹线
例：将下面的森林转换成对应的二叉树。
计算机软件基础七,树的应用
( 一 )二叉排序树
1,二叉排序树的定义二叉排序树或是一棵空树,或是满足以下条件的二叉树：
① 若其左子树非空,则其左子树中所有结点的关键字值均小于根结点的关键字值；
② 若其右子树非空,则其右子树中所有结点的关键字值均大于或等于根结点的关键字值；
③ 其左,右子树本身均为二叉排序树 。
计算机软件基础
12 8830
82
49
18 62
45
4425
二叉排序树示例
二叉排序树的重要特点：
对其进行中序遍历可得到一个按关键字值升序排列的结点序列。
计算机软件基础
2,二叉排序树的生成
插入一个结点的操作过程：
① 若原二叉排序树为空,则将待插结点作为此树的根结点 。
② 若原二叉排序树不空,则比较待插结点和根结点的关键字值 。 若待插元素的关键字值小于根结点的关键字值,则将其插入到左子树中；否则,将其插入到右子树中 。
③ 在二叉排序树的左、右子树中的插入过程同上。
主要思想,二叉排序树的生成就是从一棵空的二叉排序树开始,按关键字值逐个将一组结点依次插入到树中的恰当位置上 。
计算机软件基础
例：对于一组关键字 {51,34,79,18，
45,86}，生成对应的二叉排序树。
51
51
34
51
34 79
51
34 79
18 45
51
34 79
18
86
51
34 79
18 45
计算机软件基础
算法：
void insert(bstree *p,bstree *s) /*插入一个新结点的算法 */
{
if(s->data<p->data)
{ if (p->lchild==NULL)
p->lchild=s;
else
insert(p->lchild,s);}
else
{ if (p->rchild==NULL)
p->rchild=s;
else
insert(p->rchild,s);
}
}
二叉排序树根结点的指针新结点的指针
计算机软件基础
bstree* bstreecreate() /*二叉排序树的生成算法 */
{ int x;
bstree *s,*t;
t=NULL;
printf("input the elements of bstree,end flag is -1\n");
scanf("%d",&x);
while(x!=-1)
{ s=(bstree*)malloc(sizeof(bstree));
s->data=x;
s->lchild=s->rchild=NULL;
if (t==NULL)
t=s;
else
insert(t,s);
scanf("%d",&x);
}
return (t);
}
a?80
a?90
不及格良好中等及格优秀
a?60
a?70
分数 0-59 60-69 70-79 80-89 90-100
比例数 0.05 0.15 0.40 0.30 0.10
0.05
0.10
假定分数分布规律为：
若有 10000个输入数据，
按图 (a)需 31500次比较，而按图 (b)仅需 22000次比较。对于同一个问题，不同的判定树，
其效率大不一样。什么情况下效率最高？这就是哈夫曼树要解决的问题。
图 (a)
≥ ≥
不及格 及格中 良 优<60?
<70?
<80?
<90?
0.15
0.40 0.30
≥
≥
<
<
<
<
图 (b)
1．问题引入编制一个将百分制转换成五分制的程序。最直观的方法是利用
if语句来实现。可用二叉树描述判定过程。
(二 )哈夫曼树
2,哈夫曼树的基本概念及其构造方法
a,哈夫曼树 的 基本 概念
路径：从一个结点到另一个结点之间的若干个分支。
路径长度：路径上的分支数目称为路径长度。
结点的路径长度：从根到该结点的路径长度。
树的路径长度：树中所有结点的路径长度之和 ;一般记为 PL。
结点的权：根据应用的需要可以给树的结点赋权值。
B C
D E
G
F
H
A
结点的带权路径长度：从根到该结点的路径长度与该结点权值的乘积。
树的带权路径长度 =树中所有叶子结点的带权路径之和。
通常记作,
WPL=? wi? Li
B C
D E
G
F
H
A
2 5
3
思考：此二叉树的 WPL=？
WPL=2*3+3*2+5*3=27
哈夫曼树：假设有 n个权值 (w1,w2,…,w n ),构造有 n
个叶子结点的二叉树,每个叶子结点有一个 wi 作为它的权值，则 带权路径长度最小的二叉树称为哈夫曼树 (即 WPL
最小的 二叉树 )。
思考：给定叶子结点，如何使构造的二叉树 WPL最小
？
策略：使权值最大的叶子离根最近，权值最小的叶子离根最远。
哈夫曼树的概念可以证明图 (c),
图 (d)都是 哈夫曼树。由此看出 要使二叉树 WPL小,就须在构造二叉树时,将 权值大的结点靠近根 。
B DA C
7 5 2 4
WPL=7*2+5*2+2*2+4*2=36
图 (a)
A
C
D
B
4
7 5
2
WPL=7*3+5*3+2*1+4*2=46
图 (b)
C
A
D4
7
52
B
WPL=7*1+5*2+2*3+4*3=35
图 (c)
C
A
B
D 4
7
5
2
WPL=7*1+5*2+2*3+4*3=35
图 (d)
b,哈夫曼树的构造根据 权值大的结点靠近根 这一原则，哈夫曼树的构造算法具体步骤为：
(1) 根据给定的 n个权值,构造 n棵只有一个根结点的二叉树，
n个权值分别是这些二叉树根结点的权。设 F是由这 n棵二叉树构成的集合。
(2) 在 F中选取两棵根结点权值最小的二叉树作为左、右子树，
构造一棵新的二叉树，置新二叉树根的权值 =左、右子树根结点权值之和。
(3) 从 F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到 F中。
(4) 重复 (2),(3)，直到 F中只含一棵二叉树为止。
例：构造以 W=(5,15,40,30,10)为权的哈夫曼树。
305 1015 40
40 30155 10
15
40 30
30
15
5 10
15
哈夫曼树中权值小的叶子离根远,权值大的叶子离根近
405
30
15
10
15
30
60
100
40
5
30
15
10
15
30
60
哈夫曼树构造练习
WPL=(2+3)*4+5*3+11*2+(7+8)*2
=87
试以 a,b,c,d,e,f（ 其权值分别为 2,7,5,11,3,8）
为叶子结点构造一棵哈夫曼树，并计算该哈夫曼树的 WPL值。
da eb c f
2 7 5 11 3 8
哈夫曼树的特点：
(1)WPL最小。
(2)权值大的结点离根近，权值小的结点离根远。
(3)树形不唯一。
(4)没有度为 1的结点。
36
21
b f
7 8
15
d 11
c 5
10
a e
2 3
5
4.哈夫曼树在编码问题中的应用在进行数据通讯时，涉及数据编码问题。所谓数据编码就是数据与二进制字符串的转换。
例如邮局发电报：
例,要传输的原文为 ABACCDA
等长编码 A,00 B,01 C,10 D,11
发送方：将 ABACCDA 转换成 00010010101100
接收方：将 00010010101100 还原为 ABACCDA
原文 电文（二进制字符串） 原文发送方 接收方不等长编码 A,0 B,00 C,1 D,01
发送方：将 ABACCDA 转换成 000011010
接收方,000011010 转换成 AAAACCDA
BBCCDA
A的编码是
B的前缀
前缀编码,任何字符编码不是其它字符编码的前缀。
设 A,0 B,110 C,10 D,111
发送方：将 ABACCDA 转换成 0110010101110 总长度是 13
所得的译码是唯一的。
以字符出现的频率为权值，设计一棵 哈夫曼树，约定左分支为 ‘ 0’,右分支为 ‘ 1’ 而得到的二进制前缀编码，称作哈夫曼 编码。
例,某通讯系统只使用 8种字符 a,b,c,d,e,f,g,h,其使用频率分别为 0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,哈夫曼 编码过程为：
（ 1）构造以 a,b,c,d,e,f,g,h为叶子结点的 哈夫曼 树；
（ 2）将 哈夫曼 树所有左分支标记 0，所有右分支标记 1；
（ 3）从根到叶子结点路径上标记作为叶子结点所对应字符的编码。
哈夫曼 编码
a,0110
b,10
c,1110
d,1111
e,110
f,00
g,0111
h,010
构造以字符使用频率作为权值的哈夫曼树将 哈夫曼 树所有左分支标记 0,所有右分支标记 1
根到叶子结点路径上标记即叶子结点所对应字符的 哈夫曼 编码
f 2919
5842
100
158
7 3 5 8
11
23
14
29
a g
h e
c d
b
0
0
0
0
0
0
0
1
1
1
1
1
1
1
得到的编码使电文对应的二进制串总长最短,为什么？
哈夫曼编码
3,2 树一．树的定义树 是由 n（ n≥0） 个结点构成的有限集合 。
当 n=0时称为空树；否则,任意一棵非空树必符合以下两个条件：
1） 树中有且仅有一个特定的称为根的结点；
2）除根结点外，其余结点可分为 m个互不相交的有限集合 T1,T2,T3,?,Tm,其中每一个集合本身又是一棵树，称之为根的子树。
计算机软件基础
树的主要特点 （形态与自然界中的树十分相似）
1.只有一个根结点
2,结点分布呈明显的层次关系
3,递归定义
B C D
E HF
A
G I
树的示意图
计算机软件基础
树的逻辑结构分析,对于树中的任意结点来说，若其为根结点，则其无双亲结点；若其为叶子，则其无孩子结点；否则，此结点有且仅有一个双亲结点，并且有若干个孩子结点。
结论,树中结点的逻辑关系是一种一对多的关系，体现在一个结点只能有一个双亲，
但可以有多个孩子。
计算机软件基础
二、树的有关术语
结点的度,每个结点的子树个数 。
树的度,树中所有结点的度的最大值 。
叶子,又称终端结点,是指度为 0的结点 。
分支结点,又称非终端结点,度不为 0的结点 。
双亲和孩子,一个结点的子树的根结点称为此结点的孩子；若结点 1是结点 2的孩子,则结点 2
就被称为是结点 1的双亲 。
结点的层次,规定根为第一层,其下面的一层为第二层,依次类推 。
计算机软件基础
树的深度,树中结点的最大层次数 。
兄弟和堂兄弟,同一双亲的孩子之间互称兄弟；
其双亲在同一层的结点互为堂兄弟 。
有序树和无序树,如果树中任一结点的各个子树规定从左到右是有次序的,即不能互换位置,
则称该树为有序树,否则称为无序树 。
森林,由 m（ m≥0） 棵互不相交的树构成的集合 。
计算机软件基础三,二叉树
1,二叉树的定义二叉树是一个由 n（ n≥0） 个结点构成的有限集合，它或者为空树，或者是由一个根结点和两个分别被称为左子树和右子树的互不相交的子集构成的，其左、右子树也是二叉树。
计算机软件基础
B C
D E
G
F
H
A
二叉树示意图
二叉树的特点
（ 1） 度小于等于 2,即树中不存在度大于 2的结点；
（ 2）有序树，即每个结点的子树有左右之分，
不能交换。
计算机软件基础
2,二叉树的性质
（ 1） 二叉树的第 i层上至多有 2i-1个结点 。
（ 2） 深度为 k的二叉树的结点总数至多为 2k -1
个 。
（ 3） 若一棵二叉树上度为 0（ 叶子 ） 和度为 2的结点数分别为 n0和 n2，
则,n0=n2+1。
计算机软件基础
3,特殊的二叉树
（ 1）满二叉树若一棵二叉树的深度为 k,其结点总数为 2k -1
个，则称此二叉树为满二叉树。
B C
D E G
A
F
满二叉树示例
计算机软件基础
（ 2）完全二叉树若一棵深度为 k,具有 n个结点的二叉树，能够与一棵同深度的满二叉树中编号从 1 到 n的结点（从上到下，从左到右编号）相对应，则称此二叉树为完全二叉树。
B C
D E
A
完全二叉树示例思考：
深度为 3的完全二叉树有几种形态？
计算机软件基础
完全二叉树的性质：
[性质 1] 一棵具有 n个结点的完全二叉树的深度为?log2n? +1。
[性质 2] 若一棵完全二叉树中共有 n个结点,
对于其中编号为 i（ 1≤i≤n） 的结点,有：
1） 若 i≠1,则 i结点的双亲结点为?i/2? ； 若
i=1,则其为根结点,无双亲 。
2） 若 2i≤n,则 i结点的左孩子为 2i； 若 2i>n，
则 i结点无左孩子 。
3）若 2i+1≤n,则 i结点的右孩子为 2i+1； 若
2i+1>n,则 i结点无右孩子。
计算机软件基础若一棵二叉树中每个结点的左,右子树的深度之差 （ 平衡因子 ） 均不大于 1，
则称该二叉树为平衡二叉树 。
（ 3）平衡二叉树
B C
D E
A
F
平衡二叉树示例
计算机软件基础
三种特殊二叉树之间的关系满二叉树 完全二叉树平衡二叉树
计算机软件基础
4,二叉树的存储
（ 1）顺序存储结构实现方法,二叉树的顺序存储结构是用一组地址连续的存储单元依次（从上到下，从左到右）存放二叉树中的各个结点的数据信息，
借助于各个结点在存储结构中存放的相对位置来反映其逻辑关系。
适用范围,只适合 完全二叉树 。
计算机软件基础
B C
D E F G
A
IH J
例：对如下完全二叉树进行顺序存储。
A B C D E F G H I J
1 2 3 4 5 6 7 8 9 10
计算机软件基础思考：如何设法将顺序存储方法扩展应用于一棵非完全二叉树？
A
B C
D E F
G H
A
B C
D E F
G H
A B C D E F G H
1 2 3 4 5 6 7 8 9 10 11 12 13 14
添加虚结点
计算机软件基础
分析以上采用的存储方法的利弊。
结论：
虽然通过添加虚结点的办法可将一棵普通二叉树构造成一棵完全二叉树并对其进行顺序存储，但这种做法既繁琐，又造成了大量存储空间的浪费，故该方法在实际工作中很少被使用。
lchild data rchild
计算机软件基础
（ 2）链式存储结构实现方法,二叉树的链式存储结构中最常用的是二叉链表，其结点结构包括三个域，其中一个是数据域，用于存放结点的数据值；
另外两个是指针域，分别存放该结点的左孩子和右孩子的地址。除此之外，为了存储根结点的地址，还需设立一个指针变量 tree。
计算机软件基础 F ∧
∧
A
B C
D∧ E∧ ∧
tree
G∧ ∧ H∧ ∧
A
B C
D E F
HG
例：对如下二叉树采用二叉链表方式进行链式存储。
二叉树示意图 链式存储示意图
计算机软件基础
二叉链表中结点类型的定义：
注意,datatype在此处代表任意数据类型，实现时应根据结点的实际数据类型用对应的类型标识符代替。
lchild data rchild
计算机软件基础
typedef struct node
{ datatype data;
struct node * lchild,* rchild;
}bstree；
计算机软件基础
5,二叉树的遍历
遍历是二叉树所有算法中最重要和最基本的算法。
遍历是指按照一定的顺序访问二叉树中的所有结点，使得每个结点都能被访问且仅访问一次。这里所谓的访问有很广的含义，可以是对结点的各种操作，如修改、计算、输出等。
计算机软件基础
（ 1）先（根）序遍历
具体遍历过程：
若遍历的二叉树不为空,依次执行以下操作：
1） 访问根结点；
2） 先序访问左子树；
3）先序访问右子树；
计算机软件基础
B C
D E
G
F
H
A
E
G
例：写出对下面的二叉树进行先序遍历的序列。
先序遍历序列,A B D E G H C F
计算机软件基础
算法实现 (假定结点的值为字符型 )
void preorder (bstree?p)
{
if (p!=NULL)
{ printf(“%5c”,p->data); /*访问根结点 */
preorder(p->lchild); /*先序遍历左子树 */
preorder(p->rchild); /*先序遍历右子树 */
}
}
计算机软件基础
B C
D E
A
P
第 0层递归 (根结点 ),p!=NULL 输出 p->data
A
跟踪遍历算法的执行过程：
计算机软件基础
B C
D E
AP
A B
第 1层递归 (左子树 ),p!=NULL 输出 p->data
计算机软件基础
B C
D E
A
P==NULL
第 2层递归 (左子树 ->左子树 ),p==NULL 递归结束,返回上一层递归断点处
A B
计算机软件基础
B C
D E
A
第 1层递归 (左子树 ),进入下一层递归,访问右子树
A B
计算机软件基础
B C
D E
A
P==NULL
第 2层递归 (左子树 ->右子树 ),p==NULL 递归结束,返回上一层递归断点处
A B
计算机软件基础
B C
D E
A
第 1层递归 (左子树 ),递归结束,返回上一层断点处
A B
计算机软件基础
B C
D E
A
第 0层递归 (根结点 ),进入下一层递归,访问右子树
A B
计算机软件基础
B C
D E
A
P
第 1层递归 (右子树 ),p!=NULL 输出 p->data
A B C
计算机软件基础
B C
D E
A
P
第 2层递归 (右子树 ->左子树 ),p!=NULL 输出
p->data
A B C D
计算机软件基础
B C
D E
A
第 3层递归 (右子树 ->左子树 ->左子树 ),
p==NULL 递归结束 返回上一层递归断点处
P==NULL
A B C D
计算机软件基础
B C
D E
A
第 2层递归 (右子树 ->左子树 ):进入下一层递归,访问右子树
A B C D
计算机软件基础
B C
D E
A
第 3层递归 (右子树 ->左子树 ->右子树 ),
p==NULL 递归结束 返回上一层递归断点处
P==NULL
A B C D
计算机软件基础
B C
D E
A
第 2层递归 (右子树 ->左子树 ):递归结束,返回上一层递归断点处
A B C D
计算机软件基础
B C
D E
A
第 1层递归 (右子树 ):进入下一层递归,访问右子树
A B C D
计算机软件基础
B C
D E
A
P
第 2层递归 (右子树 ->右子树 ),p!=NULL 输出
p->data
A B C D E
计算机软件基础
B C
D E
A
第 3层递归 (右子树 ->右子树 ->左子树 ),
p==NULL 递归结束 返回上一层递归断点处
P==NULL
A B C D E
计算机软件基础
B C
D E
A
第 2层递归 (右子树 ->右子树 ):进入下一层递归,访问右子树
A B C D E
计算机软件基础
B C
D E
A
第 3层递归 (右子树 ->右子树 ->右子树 ),
p==NULL 递归结束 返回上一层递归断点处
P==NULL
A B C D E
计算机软件基础
B C
D E
A
第 2层递归 (右子树 ->右子树 ):递归结束,返回上一层递归断点处
A B C D E
计算机软件基础
B C
D E
A
第 1层递归 (右子树 ->右子树 ),递归调用结束返回上一层递归断点处
A B C D E
计算机软件基础
B C
D E
A
第 0层递归 (根结点 ),遍历函数结束
A B C D E （ 结束）
计算机软件基础
（ 2）中（根）序遍历
具体遍历过程：
若遍历的二叉树不为空,依次执行以下操作：
1） 中序访问左子树；
2） 访问根结点；
3）中序访问右子树；
例：写出对下面的二叉树进行中序遍历的序列。
计算机软件基础
B C
D E
G
F
H
A
E
G
中序遍历序列,D B G E H A C F
计算机软件基础
算法实现：
void inorder (bstree?p)
{ if (p!=NULL)
{ inorder(p->lchild); /*中序遍历左子树 */
printf(“%5c”,p->data); /*访问根结点 */
inorder(p->rchild); /*中序遍历右子树 */
}
}
算法思想：
与先序遍历算法类似，也采用递归方法实现。
计算机软件基础
（ 3）后（根）序遍历
具体遍历过程：
若遍历的二叉树不为空,依次执行以下操作：
1） 后序访问左子树；
2）后序访问右子树；
3）访问根结点；
计算机软件基础
例：写出对下面的二叉树进行后序遍历的序列。
B C
D E
G
F
H
A
E
G
后序遍历序列,D G H E B F C A
计算机软件基础
算法实现：
void postorder (bstree?p)
{ if (p!=NULL)
{ postorder(p->lchild); /*后序遍历左子树 */
postorder(p->rchild); /*后序遍历右子树 */
printf(“%5c”,p->data); /*访问根结点 */
}
}
算法思想：
与先、中序遍历算法类似，也采用递归方法实现。
计算机软件基础
思考题：
若已知一棵二叉树的中序遍历序列为,D B G E H A C F
后序遍历序列为,D G H E B F C A
请根据这两种遍历序列的规律，得到对应的二叉树并写出其先序遍历序列。
说明：只要二叉树的两种遍历序列确定，其对应的二叉树就确定下来，且对应的二叉树是唯一的。
计算机软件基础四．树的存储结构只能采用链式存储结构，最常用的方法称为孩子 —兄弟表示法。
first data next
实现方法,每个结点包括三个域，其中一个是数据域，用于存放结点的数据值；另外两个是指针域，分别存放该结点的第一个孩子和下一个相邻兄弟的的地址。除此之外，为了存储根结点的地址，还需设立一个指针变量 tree。
计算机软件基础
B C D
E GF
A
F∧ ∧
A
B
D ∧
G∧ ∧
E∧ C∧
∧
tree
例：对下面的树采用孩子 —兄弟法进行存储。
树及其链式存储示意图
计算机软件基础五．树的遍历
1,先（根）序遍历
具体遍历过程：
若遍历的树不为空,依次执行以下操作：
① 访问根结点；
② 从左到右依次先序访问各个子树；
计算机软件基础
B C D
E GF
A
例：写出对下面的树进行先序遍历的序列。
先序遍历序列,A B E F C D G
计算机软件基础
2,后（根）序遍历
具体遍历过程：
若遍历的树不为空,依次执行以下操作：
① 从左到右依次后序访问各个子树；
② 访问根结点；
计算机软件基础
B C D
E GF
A
例：写出对下面的树进行后序遍历的序列。
后序遍历序列,E F B C G D A
计算机软件基础
树的遍历算法
分析：
1.树的孩子 —兄弟链式存储结构和二叉树的链式存储结构在存储形式上是完全相同的，都是二叉链表的形式；
2,对树作先序和后序遍历分别与对其孩子 —兄弟链式存储生成的二叉链表作先序和中序遍历的结果相同 。
结论：
对树进行先序和后序遍历可分别通过调用二叉树的先序和中序遍历算法实现。
计算机软件基础六,树、森林与二叉树的转换
转换的基本思想,
按照孩子 —兄弟法建立起树、森林与二叉树的一一对应关系。
具体实现方法：
1,分析法
2,作图法
计算机软件基础
转换步骤：
（ 1） 在原树所有兄弟结点之间加一连线；
（ 2） 对每个结点,除保留与其长子间的连线外,将该结点与其余孩子间的连线全部抹除；
（ 3） 以根结点为轴心,顺时针旋转 45o；
将树转换为二叉树
计算机软件基础
B C D
E GF
A
连线
B C D
E GF
A
抹线
B C D
E GF
A
A
旋转
例：将下面的树转换成对应的二叉树。
计算机软件基础
将森林转换为二叉树
转换步骤：
与树转换成二叉树的过程类似 。
注意：
（ 1） 森林中各棵树的根结点互为兄弟 。
（ 2） 旋转时以第一棵树的根结点为轴心 。
计算机软件基础
G
HB C
D F
A
E
I
J LK
G
HB C
D F
A
E
I
J LK
连线
B
C
A
G
H I
J
L
K
D
F
E
旋转
G
HB C
D F
A
E
I
J LK抹线
例：将下面的森林转换成对应的二叉树。
计算机软件基础七,树的应用
( 一 )二叉排序树
1,二叉排序树的定义二叉排序树或是一棵空树,或是满足以下条件的二叉树：
① 若其左子树非空,则其左子树中所有结点的关键字值均小于根结点的关键字值；
② 若其右子树非空,则其右子树中所有结点的关键字值均大于或等于根结点的关键字值；
③ 其左,右子树本身均为二叉排序树 。
计算机软件基础
12 8830
82
49
18 62
45
4425
二叉排序树示例
二叉排序树的重要特点：
对其进行中序遍历可得到一个按关键字值升序排列的结点序列。
计算机软件基础
2,二叉排序树的生成
插入一个结点的操作过程：
① 若原二叉排序树为空,则将待插结点作为此树的根结点 。
② 若原二叉排序树不空,则比较待插结点和根结点的关键字值 。 若待插元素的关键字值小于根结点的关键字值,则将其插入到左子树中；否则,将其插入到右子树中 。
③ 在二叉排序树的左、右子树中的插入过程同上。
主要思想,二叉排序树的生成就是从一棵空的二叉排序树开始,按关键字值逐个将一组结点依次插入到树中的恰当位置上 。
计算机软件基础
例：对于一组关键字 {51,34,79,18，
45,86}，生成对应的二叉排序树。
51
51
34
51
34 79
51
34 79
18 45
51
34 79
18
86
51
34 79
18 45
计算机软件基础
算法：
void insert(bstree *p,bstree *s) /*插入一个新结点的算法 */
{
if(s->data<p->data)
{ if (p->lchild==NULL)
p->lchild=s;
else
insert(p->lchild,s);}
else
{ if (p->rchild==NULL)
p->rchild=s;
else
insert(p->rchild,s);
}
}
二叉排序树根结点的指针新结点的指针
计算机软件基础
bstree* bstreecreate() /*二叉排序树的生成算法 */
{ int x;
bstree *s,*t;
t=NULL;
printf("input the elements of bstree,end flag is -1\n");
scanf("%d",&x);
while(x!=-1)
{ s=(bstree*)malloc(sizeof(bstree));
s->data=x;
s->lchild=s->rchild=NULL;
if (t==NULL)
t=s;
else
insert(t,s);
scanf("%d",&x);
}
return (t);
}
a?80
a?90
不及格良好中等及格优秀
a?60
a?70
分数 0-59 60-69 70-79 80-89 90-100
比例数 0.05 0.15 0.40 0.30 0.10
0.05
0.10
假定分数分布规律为：
若有 10000个输入数据，
按图 (a)需 31500次比较，而按图 (b)仅需 22000次比较。对于同一个问题，不同的判定树，
其效率大不一样。什么情况下效率最高？这就是哈夫曼树要解决的问题。
图 (a)
≥ ≥
不及格 及格中 良 优<60?
<70?
<80?
<90?
0.15
0.40 0.30
≥
≥
<
<
<
<
图 (b)
1．问题引入编制一个将百分制转换成五分制的程序。最直观的方法是利用
if语句来实现。可用二叉树描述判定过程。
(二 )哈夫曼树
2,哈夫曼树的基本概念及其构造方法
a,哈夫曼树 的 基本 概念
路径：从一个结点到另一个结点之间的若干个分支。
路径长度：路径上的分支数目称为路径长度。
结点的路径长度：从根到该结点的路径长度。
树的路径长度：树中所有结点的路径长度之和 ;一般记为 PL。
结点的权：根据应用的需要可以给树的结点赋权值。
B C
D E
G
F
H
A
结点的带权路径长度：从根到该结点的路径长度与该结点权值的乘积。
树的带权路径长度 =树中所有叶子结点的带权路径之和。
通常记作,
WPL=? wi? Li
B C
D E
G
F
H
A
2 5
3
思考：此二叉树的 WPL=？
WPL=2*3+3*2+5*3=27
哈夫曼树：假设有 n个权值 (w1,w2,…,w n ),构造有 n
个叶子结点的二叉树,每个叶子结点有一个 wi 作为它的权值，则 带权路径长度最小的二叉树称为哈夫曼树 (即 WPL
最小的 二叉树 )。
思考：给定叶子结点，如何使构造的二叉树 WPL最小
？
策略：使权值最大的叶子离根最近，权值最小的叶子离根最远。
哈夫曼树的概念可以证明图 (c),
图 (d)都是 哈夫曼树。由此看出 要使二叉树 WPL小,就须在构造二叉树时,将 权值大的结点靠近根 。
B DA C
7 5 2 4
WPL=7*2+5*2+2*2+4*2=36
图 (a)
A
C
D
B
4
7 5
2
WPL=7*3+5*3+2*1+4*2=46
图 (b)
C
A
D4
7
52
B
WPL=7*1+5*2+2*3+4*3=35
图 (c)
C
A
B
D 4
7
5
2
WPL=7*1+5*2+2*3+4*3=35
图 (d)
b,哈夫曼树的构造根据 权值大的结点靠近根 这一原则，哈夫曼树的构造算法具体步骤为：
(1) 根据给定的 n个权值,构造 n棵只有一个根结点的二叉树，
n个权值分别是这些二叉树根结点的权。设 F是由这 n棵二叉树构成的集合。
(2) 在 F中选取两棵根结点权值最小的二叉树作为左、右子树，
构造一棵新的二叉树，置新二叉树根的权值 =左、右子树根结点权值之和。
(3) 从 F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到 F中。
(4) 重复 (2),(3)，直到 F中只含一棵二叉树为止。
例：构造以 W=(5,15,40,30,10)为权的哈夫曼树。
305 1015 40
40 30155 10
15
40 30
30
15
5 10
15
哈夫曼树中权值小的叶子离根远,权值大的叶子离根近
405
30
15
10
15
30
60
100
40
5
30
15
10
15
30
60
哈夫曼树构造练习
WPL=(2+3)*4+5*3+11*2+(7+8)*2
=87
试以 a,b,c,d,e,f（ 其权值分别为 2,7,5,11,3,8）
为叶子结点构造一棵哈夫曼树，并计算该哈夫曼树的 WPL值。
da eb c f
2 7 5 11 3 8
哈夫曼树的特点：
(1)WPL最小。
(2)权值大的结点离根近，权值小的结点离根远。
(3)树形不唯一。
(4)没有度为 1的结点。
36
21
b f
7 8
15
d 11
c 5
10
a e
2 3
5
4.哈夫曼树在编码问题中的应用在进行数据通讯时，涉及数据编码问题。所谓数据编码就是数据与二进制字符串的转换。
例如邮局发电报：
例,要传输的原文为 ABACCDA
等长编码 A,00 B,01 C,10 D,11
发送方：将 ABACCDA 转换成 00010010101100
接收方：将 00010010101100 还原为 ABACCDA
原文 电文（二进制字符串） 原文发送方 接收方不等长编码 A,0 B,00 C,1 D,01
发送方：将 ABACCDA 转换成 000011010
接收方,000011010 转换成 AAAACCDA
BBCCDA
A的编码是
B的前缀
前缀编码,任何字符编码不是其它字符编码的前缀。
设 A,0 B,110 C,10 D,111
发送方：将 ABACCDA 转换成 0110010101110 总长度是 13
所得的译码是唯一的。
以字符出现的频率为权值，设计一棵 哈夫曼树，约定左分支为 ‘ 0’,右分支为 ‘ 1’ 而得到的二进制前缀编码，称作哈夫曼 编码。
例,某通讯系统只使用 8种字符 a,b,c,d,e,f,g,h,其使用频率分别为 0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,哈夫曼 编码过程为：
（ 1）构造以 a,b,c,d,e,f,g,h为叶子结点的 哈夫曼 树；
（ 2）将 哈夫曼 树所有左分支标记 0，所有右分支标记 1；
（ 3）从根到叶子结点路径上标记作为叶子结点所对应字符的编码。
哈夫曼 编码
a,0110
b,10
c,1110
d,1111
e,110
f,00
g,0111
h,010
构造以字符使用频率作为权值的哈夫曼树将 哈夫曼 树所有左分支标记 0,所有右分支标记 1
根到叶子结点路径上标记即叶子结点所对应字符的 哈夫曼 编码
f 2919
5842
100
158
7 3 5 8
11
23
14
29
a g
h e
c d
b
0
0
0
0
0
0
0
1
1
1
1
1
1
1
得到的编码使电文对应的二进制串总长最短,为什么？
哈夫曼编码
