第7章 树形结构

第七章树和二叉树7.1-2 树和二叉树的概念与性质7.3 二叉树的存储结构7.4 二叉树的操作算法7.6-7 线索二叉树的操作算法树、森林与二叉树的转换7.8 树的应用---Huffman编码决策分析小王是一家著名高尔夫俱乐部的经理。但是他被雇员数量问题搞得心情十分不好。某些天好像所有人都來玩高尔夫，以至于所有员工都忙的团团转还是应付不过来，而有些天不知道什么原因却一个人也不来，俱乐部为雇员数量浪费了不少资金。小王的目的是通过下周天气预报寻找什么时候人们会打高尔夫，以适时调整雇员数量。因此首先他必须了解人们决定是否打球的原因。在2周时间内我们得到以下记录:

天气状况（sun）有晴，云和雨；气温用华氏温度表示；相对湿度用百分比；还有有无风。当然还有顾客是不是在这些日子光顾俱乐部。最终他得到了14行5列的数据表格：树结构和线性结构的比较线性结构树结构第一个数据元素根结点（只有一个）无前驱无双亲最后一个数据元素叶子结点(可以有多个)无后继无孩子其它数据元素其它结点一个前驱,一个后继一个双亲,多个孩子一对一一对多树的逻辑结构7.1树的基本概念

7.1.1树的定义

7.1.3树的基本术语7.1.2树的表示7.1.1树的定义：核心关系：层次关系。

树：n（n≥0）个结点的有限集合。当n＝0时，称为空树；任意一棵非空树满足以下条件：⑴

有且仅有一个特定的称为根的结点；⑵

当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。1.1通俗定义树形表示法广义表表示法a(b(e,f,g),c(h),d(i,j))树是n(n>0)个结点的有限集，在任意一棵树中：1有且只有一个特定的根(root)结点；2当n>1时，其余结点可分为m(m>0)个互不相交的有限子集T1,T2...Tm，每个子集是一棵树，称为子树。判断以下是否为树型结构7.1.3树的基本术语

1.树的结点：包含一个数据元素和指向其子树的所有分支。

2.结点的度：一个结点拥有的子树的个数。

A

C

G

J

B

E

D

F

I

H

M

K

L

树形表示法

AA的度：3B的度：2C的度：1D的度：2E的度：0I的度：33.分支结点与叶结点：度不为零的结点称为非终端结点,又叫分支结点。度为零的结点称为终端结点或叶结点。4.树的度：树中所有结点的度的最大值max(D(I))。含义：树中最大分支数为树的度。A的度：3B的度：2C的度：1D的度：2E的度：0I的度：3

A

C

G

B

D

I

JEFH

MKL

树形表示法

树的度：3结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。树的深度：树中所有结点的最大层数，也称高度。1层2层4层3层高度＝4CGBDEFKLHMIJC树的基本术语 5.CBDEFKLHJA71234568910层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。树的基本术语有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。数据结构中讨论的一般都是有序树

树的基本术语 6.ACBGFEDACBGFEDCBDEFKLHJ森林：m(m≥0)棵互不相交的树的集合。

树的基本术语 7.A路径：如果树的结点序列n1,n2,…,nk有如下关系：则把n1,n2,…,nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。CGBDEFKLHMIJA树的基本术语 8.祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。CGBDEFKLHMIJA树的基本术语 9.

总结基本术语的理解：结点的度：一个结点含有的子树的个数称为该结点的度；如结点D含有3个子树，则结点D的度为3，而结点C的度为1，结点K的度为0。叶结点或终端结点：度为零的结点称为叶结点；如结点F的度为0，则为叶子结点。非终端结点或分支结点：度不为零的结点；

双亲结点（父结点）：含有孩子的结点称为其孩子的双亲结点；例如，结点B是E,F的双亲结点（父结点）。孩子结点：一个结点子树的根结点称为该结点的孩子结点；例如，结点B的孩子结点有E,F两个。兄弟结点：具有相同双亲结点的结点互称为兄弟结点；如E,F互为兄弟结点。CGBDEFKLHMIJA

总结基本术语的理解：树的度：一棵树中，最大的结点的度称为树的度；结点的层次：从根开始定义起，根为第一层，根的孩子为第二层；

树的高度或深度：树中结点的最大层次；堂兄弟：双亲在同一层的结点互为堂兄弟；

结点的祖先：从根到该结点所经分支上的所有结点；子孙：以某结点为根的子树中任一结点都称为该结点的子孙。森林：由m（m>=0）棵互不相交的树的集合称为森林；CGBDEFKLHMIJA1.有一棵树如图所示，回答下面的问题（1）这棵树的叶子结点是___________。（2）结点k3的度是______________（3）这棵树的度是_____________（4）这棵树的深度是____________（5）结点k3的孩子结点是___________（6）这棵树的根结点是___________（7）结点k3的双亲结点是____________树的表示方法（广义表法）二叉树的定义

二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。二叉树的逻辑结构问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。研究二叉树的意义？设有八枚硬币，分别表示为a、b、c、d、e、f、g、h，其中有且仅有一枚硬币是假币，并且假币的重量与真币的重量不同，可能轻，也可能重。现要求以天平为工具，用最少的比较次数挑选出假币，并同时确定这枚假币的重量比其它真币是轻还是重。把硬币分成三组，从八枚硬币中任取六枚a、b、c、d、e、f，在天平两端各放三枚进行比较。假设a、b、c三枚放在天平的一端，d、e、f三枚放在天平的另一端，可能出现如图所示的三种比较结

7.2二叉树概念和性质

7.2.1二叉树概念7.2.2二叉树性质7.2.3二叉树存储结构7.2.1二叉树概念二叉树也称为二次树或二分树，它是结点数为0或当节点数不为0时每个结点最多只有左右两棵子树的树。特点是：（1）每个结点最多只有两棵树，既不存在度大于2的结点。（2）子树有左右之分，不能颠倒。思考：二叉树和度为2的树一样吗有什么区别？结点的孩子数结点孩子的有序性二叉树的特点：⑴每个结点最多有两棵子树；⑵二叉树是有序的，其次序不能任意颠倒。

7.2.1二叉树的逻辑结构注意：二叉树和树是两种树结构。ABCDEFGABAB二叉树的基本形态Ф空二叉树只有一个根结点左子树根结点只有左子树右子树根结点只有右子树左子树右子树根结点同时有左右子树二叉树的逻辑结构二叉树的逻辑结构具有3个结点的树和具有3个结点的二叉树的形态二叉树和树是两种树结构。特殊的二叉树斜树1.所有结点都只有左子树的二叉树称为左斜树；2.所有结点都只有右子树的二叉树称为右斜树；3.左斜树和右斜树统称为斜树。1.在斜树中，每一层只有一个结点；2.斜树的结点个数与其深度相同。

二叉树的逻辑结构---斜树的特点：ABCABC满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。满二叉树的特点：叶子只能出现在最下一层；只有度为0和度为2的结点。CDEFGHIJKLMNO1112131415特殊的二叉树二叉树的逻辑结构---满二叉树?不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在同一层上。满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多A1523467BCDEFGLM89特殊的二叉树二叉树的逻辑结构---完全二叉树对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。CDEFGHIJKLMNO1112131415CDEFGHIJ特殊的二叉树二叉树的逻辑结构---在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点特殊的二叉树二叉树的逻辑结构---1.叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部；2.完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。

3.深度为k的完全二叉树在k-1层上一定是满二叉树。完全二叉树的特点CDEFGHIJ特殊的二叉树二叉树的逻辑结构---总结二叉树的概念二叉树的五种形态斜二叉树满二叉树完全二叉树7.2.2二叉树性质（5个）

性质1非空二叉树上第i层上至多有2i-1个结点,这里应有i≥1。

性质1非空二叉树上第i层上至多有2i-1个结点,这里应有i≥1。证明：用归纳法（1）当i=120有一个根结点成立（2）假设对所有的j(1<=j<i)上述性质成立。即第j层上至多有2j-1个结点成立（3）要证明j=i时，命题也成立由归纳假设：第j=i-1层上至多有2i-2

个结点，又由于二叉树上每个结点的度最大为2，所以第i层上结点总数最大为第i-1层上最大结点数的2倍，即2×2i-2=2i-1

性质2高度为h的二叉树至多有2h-1个结点(h≥1)。证明：深度为h的二叉树的最大结点数是二叉树中每层结点的最大数之和，即=20+21+22+……+2h-1=2h-1(等比级数求和)

性质3非空二叉树上叶结点数等于度为2的结点数加1。有如下关系：n0=n2+1

证明：设二叉树上叶结点数为n0,单分支结点数为n1,双分支结点数为n2,则总结点数n=n0+n1+n2。在一棵二叉树中,度为i(i=0,1,2)的结点，有i个孩子。孩子数=n1+2n2。由于二叉树中除根结点以外,每个结点都是另一个结点的孩子,因此二叉树中有：孩子数=总结点数-1=n-1。由上述三个等式可得：n1+2n2=n-1=n0+n1+n2-1即：n0=n2+1

A

B

C

D

E

H

J

K

F

G

L

M

N

O

二叉树

(1)一棵二叉树中双分支结点有15个，单分支结点30个，则叶子结点有（）。(2)若一棵满二叉树有2047个结点，则该二叉树中叶结点的个数为

A)512 B)1024 C)2048 D)4096(3)若一棵度为7的树具有n1=8,n2=7,n3=6,n4=5,n5=4,n6=3,n7=2,则该树一共有（）个叶结点[提示：此不是二叉树，用性质3的证明方法来推导]

在一棵二叉树中,如果所有分支结点都有左孩子结点和右孩子结点,并且叶结点都集中在二叉树的最下一层,这样的二叉树称为满二叉树。下图所示就是一棵满二叉树。可以对满二叉树的结点进行连续编号,约定编号从树根为1开始,按照层数从小到大、同一层从左到右的次序进行。图中每个结点外边的数字为对该结点的编号。每一层上结点树都达到最大度为1的结点n1=0完全二叉树:若二叉树中度小于2的结点只能出现在最大层或次大层,并且最下面一层的叶结点都依次排列在该层最左边的位置上,则这样的二叉树称为完全二叉树。如下图所示为一棵完全二叉树。同样可以对完全二叉树中每个结点进行连续编号,编号的方法同满二叉树相同。

12

3

4

1

2

3

4

5

6

判断是否为：完全二叉树？（1）LH1=2RH1=1LH2=0RH2=10-1=-1不满足（2）叶结点只能出现在最大层或次大层从左边开始结论：不是（1）LH1=3RH1=1LH1-RH1=2不满足（2）叶结点只能出现在最大层或次大层且从从左边开始结论：不是

性质4具有n个(n＞0)结点的完全二叉树的高（深）度为log2n+1。证明：设深度为H余下的性质是针对完全二叉树的：证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立

2k-1≤n＜2k

2k-1-1…2k-12k-1———第k-1层———第k层…最少结点数最多结点数

log2n+1[log2n]log2n[log2n]+1k所在区间证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立

2k-1≤n＜2k性质4

具有n个结点的完全二叉树的深度为log2n+1。

对不等式取对数，有：

k-1≤log2n＜k即：

log2n＜k≤log2n+1由于k是整数，故必有k＝log2n+1一棵具有n个结点的完全二叉树中从1开始按层序编号，则结点i的双亲结点为

i/2；结点i的左孩子为2i；结点i的右孩子为2i＋1。

在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。完全二叉树的基本性质

性质5对n个结点的完全二叉树中编号为i的结点(1≤i≤n,n≥1,n为结点数)有：

(1)若i=1时，结点i是树根；否则（i>1）,结点i的双亲为

i/2.(2)若2i>n时。结点i无左孩子，是叶结点；否则结点i的左孩子为结点2i。

(3)若2i+1>n时。结点i无右孩子；否则结点i的左孩子为结点2i+1。余下的性质是针对完全二叉树的（很重要）：先证明（2）（3）用归纳法

(2)若2i>n时。结点i无左孩子，是叶结点；否则结点i的左孩子为结点2i。

(3)若2i+1>n时。结点i无右孩子；否则结点i的左孩子为结点2i+1。1）当i=1时，如果2i=2>n无左孩子，否则2i=2<=n

结点2存在是结点1的左孩子。第二条成立当i=1时，如果2i+1=3>n无右孩子，否则2i+1=3<=n

结点3存在是结点1的右孩子。第三条成立2）假设对所有的结点j(1<=j<=i)有：j的左孩子为2j(2j<=n),右孩子为2j+1(2j+1<=n)3)要证明j=i+1时等式成立i+1的左孩子为2（i+1） (2(i+1)<=n)i+1的右孩子为2（i+1）+1 (2(i+1)+1<=n)i2i2i+1

i+12i+22i+3…………i与i+1同层……

i2i2i+1……

i+12i+22i+3……i与i+1不同层结论：得证(1)若i=1时，结点i是树根；否则（i>1）,结点i的双亲为

i/2.用归纳法自己证明第五条性质非常重要，是二叉树顺序存储的理论基础7.2.3树、森林与二叉树的转换1.兄弟加线.树转化为二叉树ABCDEFG2.保留双亲与第一孩子连线,删去与其他孩子的连线.ABCDEFG1.兄弟加线.7.2.3树、森林与二叉树的转换3.顺时针转动,使之层次分明.2.保留双亲与第一孩子连线,删去与其他孩子的连线.1.兄弟加线.ABCDEFG7.2.3树、森林与二叉树的转换树和二叉树之间的对应关系3.顺时针转动,使之层次分明.2.保留双亲与第一孩子连线,删去与其他孩子的连线.1.兄弟加线.GDABECF7.2.3树、森林与二叉树的转换树和二叉树之间的对应关系总结：树转换为二叉树

⑴加线——树中所有相邻兄弟之间加一条连线。

⑵去线——对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。

⑶层次调整——以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。

森林转换为二叉树

⑴将森林中的每棵树转换成二叉树；⑵从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。7.2.3树、森林与二叉树的转换IHGBCDAFE二叉树转换为树或森林

⑴加线——若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来；⑵去线——删去原二叉树中所有的双亲结点与右孩子结点的连线；⑶

层次调整——整理由⑴、⑵两步所得到的树或森林，使之层次分明。

7.2.3树、森林与二叉树的转换FHGEAICDBFHGDCEBAIFEDCBAHGI加线去线层次调整IHGBCDAFE树、森林与二叉树的转换例题:将下面的深林转化为二叉树ACDBEFGJIH7.3二叉树存储结构

7.3.1二叉树的顺序存储结构

7.3.2二叉树的链式存储结构7.3.1二叉树的顺序存储结构用一组地址连续的存储单元，以层序的顺序存放二叉树的数据元素，结点的相对位置蕴含着结点的关系。【注意】逻辑关系蕴含在这里：结点的相对位置蕴含着结点的关系。ABCDEFGHIJK123456789101112131415顺序存储结构一般二叉树的顺序存储没有左右孩子的地方填0

A

B

C

D

E

FG

一般二叉树

ABCDE0000FG0000123456789101112131415顺序存储结构例：深度为K,只有K个结点的右单支树的存放：分析:根据性质2：二叉树深度为K最多有2k-1个结点按顺序存储实际只使用K个存储单元，浪费掉2k-1-K

1

2

K

1

K

结论：顺序存储只适合完全二叉树，既不浪费空间，又能很快的确定结点存放的位置，以及结点的双亲和左右孩子。但是对于一般二叉树可能造成存储空间的浪费。7.3.2二叉树的链式存储结构

常用的：二叉链表三叉链表线索链表

A

B

C

D

E

FG

一般二叉树

在二叉树的链接存储中,结点的结构如下:typedefstructnode{ ElemTypedata; structnode*lchild,*rchild;}BTNode;

其中,data表示值域,用于存储对应的数据元素,lchild和rchild分别表示左指针域和右指针域,用于分别存储左孩子结点和右孩子结点(即左、右子树的根结点)的存储位置。lchilddatarchild二叉树及其链式存储结构优点：找孩子比较容易，找双亲很难

A

B

C

E

F

D

G

A

B∧

C

∧

D

∧

E∧

∧

F∧

∧

G∧

(a)

(b)

在三叉链表的存储中,结点的结构如下:

typedefstructnode{ ElemTypedata; structnode*lchild,*parent,*rchild;}BTNode;

其中,data表示值域,用于存储对应的数据元素,lchild和rchild分别表示左指针域和右指针域,用于分别存储左孩子结点和右孩子结点(即左、右子树的根结点)的存储位置，parent

指向结点的双亲。lchilddataparentrchild二叉树及其链式存储结构

A

B

C

E

F

D

G

(a)

∧A∧BCD∧∧F∧∧E∧∧G∧性质6：含有n个结点的二叉链表中，有n+1个空链域证明：（1）n=n0+n1+n2（2）空链域=2n0+n1（3）no=n2+1

A

B

C

E

F

D

G

A

B∧

C

∧

D

∧

E∧

∧

F∧

∧

G∧

(a)

(b)

7.5二叉树的遍历7.5.1二叉树遍历的概念7.5.2二叉树遍历的实现递归及非递归算法二叉树的遍历操作

二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。二叉树遍历操作的结果？非线性结构线性化7.5二叉树的逻辑结构抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。前序遍历中序遍历后序遍历层序遍历

如果限定先左后右，则二叉树遍历方式有三种：前序：DLR中序：LDR后序：LRD层序遍历：按二叉树的层序编号的次序访问各结点。

7.5.1二叉树的逻辑结构考虑二叉树的组成：根结点D左子树L右子树R二叉树前序遍历若二叉树为空，则空操作返回；否则：①访问根结点；②前序遍历根结点的左子树；③前序遍历根结点的右子树。前序遍历序列：ABDGCEFABCDEFG二叉树的遍历操作

7.5二叉树的逻辑结构中序遍历若二叉树为空，则空操作返回；否则：①中序遍历根结点的左子树；②访问根结点；③中序遍历根结点的右子树。

中序遍历序列：DGBAECFABCDEFG二叉树的遍历操作

7.5二叉树的逻辑结构后序遍历若二叉树为空，则空操作返回；否则：①后序遍历根结点的左子树；②后序遍历根结点的右子树。③访问根结点；后序遍历序列：GDBEFCAABCDEFG二叉树的遍历操作

7.5二叉树的逻辑结构层序遍历二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。

层序遍历序列：ABCDEFGABCDEFG二叉树的遍历操作

7.5二叉树的逻辑结构

A

B

C

D

E

H

I

J

K

F

G

1

2

3

4

5

6

7

8

9

10

11

先序序列：ABDHIEJKCFG中序序列：HDIBJEKAFCG后序序列：HIDJKEBFGCA先序序列：ABDEHJKLMNCFGI中序序列：DBJHLKMNEAFCGI后序序列：DJLMNKHEBFGICA在二叉树的链接存储中,结点的结构如下:typedefstructnode{ ElemTypedata; structnode*lchild,*rchild;}BTNode;

其中,data表示值域,用于存储对应的数据元素,lchild和rchild分别表示左指针域和右指针域,用于分别存储左孩子结点和右孩子结点(即左、右子树的根结点)的存储位置。lchilddatarchild二叉树及其链式存储结构

(a)

(b)

A

B

C

E

F

D

A

B

C

∧

D∧

∧

E∧

∧

F∧

∧1.先序遍历DLR先序遍历二叉树的过程是：(1)访问根结点D；(2)先序遍历左子树L；(3)先序遍历右子树R。先序序列：ABDECF/*先序遍历的递归算法*/voidPreOrder(BTNode*b){if(b!=NULL){printf("%c",b->data);/*访问根结点*/PreOrder(b->lchild);PreOrder(b->rchild);}}

A

B

C

E

F

D

lchilddatarchild/*先序遍历的递归算法*/voidPreOrder(BTNode*b){if(b!=NULL){printf("%c",b->data);

/*访问根结点*/PreOrder(b->lchild);PreOrder(b->rchild);}}PreOrder(&A)APreOrder(A->lchild=B);BPreOrder(B->lchild=D);DPreOrder(D->lchild=NULL);PreOrder(D->rchild=NULL);PreOrder(B->rchild=E);EPreOrder(E->lchild=NULL);PreOrder(E->rchild=NULL);PreOrder(A->rchild=C);CPreOrder(C->lchild=NULL);PreOrder(C->rchild=F);FPreOrder(F->lchild=NULL);PreOrder(F->rchild=NULL);

A

B

C

∧

D∧

∧

E∧

∧

F∧

∧2.中序遍历LDR中序遍历二叉树的过程是：(1)中序遍历左子树L；(2)访问根结点D；(3)中序遍历右子树R。中序序列：DBEACF/*中序遍历的递归算法*/voidInOrder(BTNode*b){if(b!=NULL){/*访问根结点*/

InOrder(b->lchild);

printf("%c",b->data);

InOrder(b->rchild);}}

A

B

C

E

F

D

3.后序遍历后序遍历二叉树的过程是：(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。后序序列：DEBFCA

voidPostOrder(BTNode*b)/*后序遍历递归算法*/{if(b!=NULL)