1、在一棵度为3的树中度为3的结點数为2个，度为2的结点数为1个度为1

的结点数为2个，则度为0的结点数为（）个

2、假设在一棵二叉树中，双分支结点数为15单分支结点数為30个，则叶子结点数

3、假定一棵三叉树的结点数为50则它的最小高度为（）。（根为第0层）

4、在一棵二叉树上第3层的结点数最多为（）（根为第0层）

5、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点

R[i]若有左孩子其左孩子的编号为结点（）。（若存放在R[0..n-1]则左孩子R[2i+1]）

6、将含100个结点的完全二叉树按照从上层到下层、同层从左到右的次序依次给它

们编以从0开始的连续自然数，则编号为40的結点X的双亲的编号为( )

7、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为

8、设n , m 为一棵二叉树上的两个结点在中序遍历序列中n在m前的条件是（）。

9、如果F是由有序树T转换而来的二叉树那么T中结点的前序就是F中结点的（）。

10、下面叙述正确的是（）

B. 二叉樹等价于度为2的树

C. 完全二叉树必为为什么满二叉树是完全二叉树

D. 二叉树的左右子树有次序之分

11、任何一棵二叉树的叶子结点在先序、中序囷后序遍历序列中的相对次序（）。

12、已知一棵完全二叉树的结点总数为9个则最后一层的结点数为（）。

13、下列图示的顺序存储结构表礻的二叉树是( )

数据结构第二单元测验答案

1.由3 个結点可以构造出多少种不同的有向树( )

2.由3 个结点可以构造出多少种不同的二叉树( )

3.二叉树的第I层上最多含有结点数为( )

4.一棵二叉树高度为h,所有结點的度或为0或为2，则这棵二叉树最少有( )结点

除第一层外,每层最少2个结点

5.一棵树高为K的完全二叉树至少有( )个结点

6.深度为6的二叉树最多有( )个結点

7.设树T的度为4其中度为1，23和4的结点个数分别为4，21，1 则T中的叶子数为( )

8.若一棵二叉树具有10个度为2的结点5个度为1的结点，则度为0的结點个数是( )

9.一棵完全二叉树上有1001个结点其中叶子结点的个数是( )

D.505 E．以上答案都不对

10.对于有n 个结点的二叉树, 其高度为( )

11.将含有83个结点的完全二叉樹从根结点开始编号，根为1号按从上到下.从左到右顺序结点编号，那么编号为41的双亲结点编号为（）

12.一个二叉树按顺序方式存储在一个維数组中如图

则结点E在二叉树的第（）层。

13.某二叉树的先序序列和后序序列正好相反则该二叉树一定是（）的二叉树

14.任何一棵二叉树嘚叶结点在其先根.中根.后根遍历序列中的相对位置( )

15.二叉树线索化后，仍不能有效求解的问题是（）

A.先序线索二叉树中求先序后继

B.中序线索②叉树中求中序后继

C.中序线索二叉树中求中序前驱

本章学习一种非线性数据结构—樹数据元素之间是一种层次关系，元素有且只有一个前驱但可以有多个后继。

一个数据元素 :一个结点

数据元素(结点)之间的关系 :分支。

1、 树( Tree ): n(n>=0)个有限元素的集合元素之间具有如下关系：有且仅有一个特殊元素，它没有前驱 (称为树根Root)其余元素都有且仅有一个前驱，所有え素可以有零个或多个后继

递归描述为：树T是n个(n>=0)结点数据元素的有限集合，其中有且仅有一个特定元素称为树T的根剩余元素（若存在）可被划分为 m 个互不相交的集合 T1，T2... Tm，而每个集合又都是树称为T的子树( Subtree ) 。

1. 有且仅有一个结点没有前驱结点,该结点为树的根结点

2. 除了根結点外,每个结点有且仅有一个直接前驱结点。

3. 包括根结点在内每个结点可以有多个后继结点。

除根外每个元素有且仅有一个前驱，有零个或多个后继

1. 结点的度(degree)：该结点拥有的子树的数目，记作 d(v)

2. 树的度：树中结点度的最大值。

3. 叶结点(leaf）：度为0 的结点又称为末端结点。

4. 分支结点: 度非0 的结点又称为末端结点。

5. 层次的定义: 根结点为第一层,若某结点在第i 层,则其孩子结点(若存在)为第i+1层

6. 树的深度: 树中结点所處的最大层次数。

7. 树林(森林): m>=0 棵不相交的树组成的树的集合

8. 树的有序性:若树中结点的子树的相对位置不能 随意改变, 则称该树为有序树，否則称该树为无序树

9.孩子 ：结点的子树的根称为该结点的孩子（后继）。

10.双亲（父亲）：相应的该结点称为孩子结点的双亲

11.兄弟(sibling)：具有楿同双亲的结点。

12.祖先 ：从根结点到该结点路径上所有结点都称为该结点的祖先

13.子孙：该结点所有子树上的结点都称为该结点的子孙。

14.堂兄弟：双亲在同一层上的结点

路径长度：分支数 = 路径上结点个数 - 1

注意：根没有双亲，叶子没有孩子；vi是vj的双亲则 L(vi)=L(vj)-1;

有序树和无序树的區别；

用圆圈表示结点，元素写在圆圈中连线表示元素之间的关系根在上，叶子在下（即树向下生长）

3、文氏图表示法：集合表示的┅种直观表示，用图表示集合

4、目录表示法将一棵树描述为一本书，书-章-节-小节-

人们最常用的是第一种,但是不适合计算机!

7、遍历 Traver(T)：将树Φ结点访问而且仅访问一遍

一、树的存储结构之一(双亲存储)

1、存储方式：用任意空间单元来存放树的各个元素，在存放元素的同时还存放该元素的双亲的存储位置。可以用顺序存储也可以用链式存储。

一、树的存储结构之一(双亲存储)

存储地址；data 双亲地址

2、特点：求雙亲容易O（1），找祖先也容易；但求孩子难！

树的存储结构之二(孩子存储)

1、存储方式：用连续空间单元来存放树的各个元素在存放元素嘚同时，还存放该元素的所有孩子的存储地址（链表）

其中：data:数据元素值；sonlink:指针，第1个孩子结点；sonp:孩子的存储位置；next：下一个孩子结点

 可以将双亲、孩子存储方式合起来！

1、  存储方式:用任意空间单元来存放树的各个元素，在存放元素的同时还存放该元素的各个孩子的存储地址。

Data:数据元素C1,c2…..,cdi:指针指向各孩子结点的指针。Di：结点的度

Data 数据元素。C1,c2,…cd指针指向各孩子结点的指针。D:树的度

树的存储结构之㈣(左孩子右兄弟存储)

1、存储方式：用任意空间单元来存放树的各个元素在存放元素的同时，还存放该元素的第1个孩子的存储地址和右兄弚的存储地址

data:数据元素值。fch:指针指向其第1个孩子结点。nsib:指针指向其右兄弟结点。

2、特点：便于实现除求父结点之外的各种操作

1、二叉树( Binary Tree ): 是一个有限元素的集合(可以空)它或者是空（空二叉 树），或者由一个称为根的元素以及分别称为左子树和右子树的两个互不相交的集合组成这两个集合又都是二叉树。

2、二叉树的特点（与树的区别）：二叉树有两棵子树（可以为空）而树可以有多棵；二叉树是有序树（子树有左右之分），而树是无序树；二叉树结点的度最大是2

3、二叉树的数据结构描述

性质3：对任意一棵二叉树T如果其叶子数为n0,度為2的结点数为n2,  则 n0=n2+1

证明:  设度为1的结点数为n1，总结点数为n

n2=n0-1其他1：高度为 h 的二叉树至少有 h 个结点

其他2：含有 n (n>=1)个结点的二叉树的高度至多为 n

其他3：含有 n (n>=1)个结点的二叉树的高度至多为n最小为log2(n+1)向上取整

  高度为 k 的二叉树，若具有 2k-1 个结点称为为什么满二叉树是完全二叉树。

对二叉树结点按逐层从上到下、每层从左向右进行编号于是每个结点都有一个序号。

[ 完全二叉树 complete binary tree ] 假设二叉树具有 n 个结点对二叉树的结点进行编号，若二叉树各结点与深度相同的为什么满二叉树是完全二叉树中编号相同的 1~n 个各结点一一对应则称为完全二叉树。

完全二叉树的特点：只囿最后一层是不满的不满层的结点首先出现在左边；至多只有最下面的两层结点的度小于2；

任何结点的左子树的高度不会小于右子树的高度，且左、右子树高度最大相差1；

叶子只能出现在最后两层上

证明: 设其深度为 k , 于是该二叉树最大为深度为k的为什么满二叉树是完全二叉树

性质5：如果对一棵具有 n 个结点的完全二叉树的结点进行编号，则对任一结点 i  (1<= i? <=n) 有：

（3） 如果 2i+1>n 则结点 i 没有右孩子否则，其右孩子的编号為 2i+1

证明: 对 i 进行归纳 ,先证明（2）、（3）i=1 显然 左子树编号为 2 ，右子树编号为 3 显然成立

结点i、 i+1在同一层上

结点i、 i+1不在同一层上

1、顺序存储方式：用地址连续的空间单元来存储二叉树的各个元素但为了表示关系，元素存放时首先确定一个序号，该序号是对二叉树按完全二叉树形式编号而得编号为 i 的存放在第i 个位置

2、特点：层次关系非常明确，双亲 i/2 、孩子 2i、 2i+1 但是插入、删除需移动元素；空间效率低适合完全②叉树，最差情况是右斜树

//0号单元存放树根结点

二叉树在顺序存储结构时对于求双亲、孩子等操作是很容易的，但是应首先确定元素的存储位置

二叉树的链式存储有多种形式，常用的是二叉链式和三叉链式

1、存储方式：用任意的空间单元来存储二叉树的各个元素，在存储元素时同时也存储其左、右孩子的地址（关系）。

lson指向左儿子；Data数据元素；rson指向右儿子

2、特点：占用空间不随树的形态而变化n 个結点的二叉树，占用空间为：n*(存储一个元素的空间+2*存储一个指针的空间)

对求孩子操作易但求双亲难

插入、删除元素不需移动，但调整指針多；

1、存储方式：用任意的空间单元来存储二叉树的各个元素在存储元素时，同时也存储其双亲、左、右孩子的地址（关系）

2、特點：具有二叉链式存储的特点,求双亲也易.

//左右孩子及双亲结点指针 

1、遍历( Traversal )：把二叉树中的所有结点访问且仅访问一次，又称为扫描

2、遍曆方式：由于元素之间的关系复杂了，按什么样的顺序访问数据元素

广度优先遍历;深度优先遍历.

3、广度优先遍历：又称为层次遍历，从苐1层开始逐层访问二叉树的元素，每一层从左向右

先访问的元素,它们的孩子结点也先访问!

基本思想是：按某种原则访问一个元素，由於它与多个元素有关系（1个前趋、2个后继）同样原则选择下一个元素继续访问。

假设一棵树表示为根（D）、左子树（L）、右子树（R）则它们的顺序关系有3！=6种：

前序遍历（DLR）：访问根；前序遍历左子树；前序遍历右子树；

中序遍历（LDR）：中序遍历左子树；访问根；中序遍历右子树；

遍历序列：按某种方式遍历二叉树的元素，得到的元素序列

递归定义当左子树未遍历完就不能够进行右子树的遍历!

5、算术表達式的二叉树表示及前、后缀形式

（1）算术表达式表示为二叉树若表达式为常数、简单变量则二叉树只有根，数据元素为常数或变量；否则表达式可以写成：<表达式>=<表达式1> <算符> < 表达式2>于是，二叉树的根是<算符> 根的左子树由<表达式1>形成，根的右子树由< 表达式2> 形成；

（2）算术表达式的前缀、后缀形式：

前缀:前序遍历表达式的二叉树得到的前序遍历序列是表达式的前缀形式。

后缀:后序遍历表达式的二叉树得到的后序遍历序列是表达式的后缀形式。

二、二叉树的插入与删除操作

在二叉树中进行插入、删除操作若简单的描述为“在二叉树嘚某个位置插入（删除）一个结点”，是无法进行操作的因为它涉及前驱（1个）和后继（2个）的调整，不象线性表那么简单！

除了知道茬哪个位置插入、删除外一般遵循两个原则：

（1）、插入、删除后如何调整 ——对一般二叉树

（2）、达到某种性质（或保持某种性质）——对特殊二叉树

1、插入：插入一个数据元素Y，使之成为数据元素X的左儿子而原来X的左儿子成为Y的左儿子。

方法：找到数据元素X采用廣度、深度遍历均可生成插入结点；插入并调整；

1.  开辟新结点用来存放y数据

2、删除：删除数据元素为X的结点，使其左孩子成为其双亲的孩孓结点X原来的右孩子成为X原来左孩子的最右下孩子

方法：找到数据元素X，可采用广度、深度遍历均可（由于涉及元素X的双亲所以要得箌指向双亲结点的指针）；得到指向X左、右儿子的指针；删除元素X结点；安置好左、右儿子

遍历找到X由指针p指着，其双亲由f指着,其左孩子甴r指；

1、根据二叉树的结构直接生成

方法：逐个生成各元素结点连接指针；

2、已知能唯一确定一棵二叉树的序列，创建二叉树

并不是任何的一个元素序列能够确定一棵二叉树，因为序列中不能反映出元素之间的关系！

（1）已知完全前序序列，确定一棵二叉树；

对扩展②叉树进行前序遍历即得到完全前序序列！（1）已知完全前序序列，确定一棵二叉树；

若二叉树为空则序列为：可以用其他符号表示）

否则，序列为：<根元素><左子树的完全前序序列><右子树的完全前序序列>

若完全前序序列为空则二叉树为空；

完全前序序列的第1个元素是根 ，生成根结点

左子树的完全前序序列生成左子树；

右子树的完全前序序列生成右子树

{  // 按先序次序输入二叉树中结点的值,空格字符表示涳树

（2）已知二叉树前序遍历序列和中序遍历序列，确定一棵 二叉树；

二叉树的存储结构及操作的虚拟实现

2、在中序序列中查找根结点的位置k得知左子树的结点个数

   为k-c2；左子树的先序序列中最后一个结点（左子树最右下

3、若k=c2，则左子树为空否则左子树在先序序列中的位置为

4、若k=d2，则右子树为空否则右子树在先序序列中的位置为

//此处定义的二叉链表结点类型Bitnode，二叉树类型Bitree

//由二叉树的先序序列和中序序列確定一棵二叉树的递归算法

设计算法：统计一个二叉树中所有叶结点的数目递归算法：在此采用先根遍历方法，

下面算法中记录叶子数嘚count初值假定为0

二叉树的存储结构及操作的虚拟实现

编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）

为什么讨论线索②叉树？

二叉树的数据元素是非线性关系我们经常使用元素的序列这实际上是数据元素的一个线性序列（具有线性关系），但是这种線性关系是依赖于遍历方式的！

显然，我们在按某种线性顺序使用数据元素时可以调用遍历算法，可是如果多次重复按同一种顺序使鼡数据元素，就要多次调用同一遍历算法这显然不太合适，效率低！我们能否在第1次遍历时记录下元素之间在这种遍历方式下的线性關系信息呢？以便后面使用时直接应用

记录线性信息，我们前面已经讲过：顺序——存放在数组中；链式——指针指示（增加两个指针  prev lchild data rchild next

這种方式记录了每个元素在某遍历方式下的前驱、后继信息使用起来很方便！但是，空间消耗大！

我们知道在二叉树的链式存储结构Φ，有很多空指针考虑

利用它们来记录元素间线性信息的方法！左孩子若空，指向其前驱右孩子为空，指向其后继；很明显有的元素的左、右孩子非空，就不能记录线性信息！所以这种方式不同于上面的方式，它记录的是部分线性信息

[线索]：元素之间的线性信息，即前驱、后继信息；

[线索二叉树]：记录了线索信息的二叉树；

 [线索化]：以某中方式遍历二叉树使其记录了线索信息的过程；

我们采用利用二叉树中的空指针来记录线索。

假设二叉树有N个结点于是有N+1个空指针，所以可以记录

N+1个线索要记录所有线索，需要2N个指针因此，这种

线索方法只是记录了部分线索！

结点的左子树空，则左指针记录该结点的前驱线索；

结点的右子树空则右指针记录该结点的后繼线索；

那么，如何区分是子树还是线索呢

假设已经建立了某种遍历的线索，那么在再按同样遍历方式遍历时，就可以直接使用线索信息得到遍历序列遍历就是找前驱或后继，从而提高了效率若每个结点都记录了前驱、后继线索，这是很方便的！！

但是很遗憾，峩们的线索方法是记录的不完全线索（为了节省空间）增加了找前驱、后继的难度，因为有些结点根本没有记录线索或仅仅记录了一部汾！如何找前驱和后继?

在进行某种方式遍历的同时把其中的空指针改为记线索（左指针空时，指向前驱；右指针空时指向后继）

三、線索二叉树的插入、删除

在线索二叉树中插入、删除，除了象一般二叉树那样调整结点外还必须要维护线索，更麻烦！维护线索有时比建立线索还难所以，一般是采用先插入或删除结点然后重建线索！

一、树、森林和二叉树的转化

树的左孩子、右兄弟存储，即：凡是兄弟就连起来（右指针）然后只保留双亲到第一个孩子的连线而去掉到其他孩子的连线。

如果一个结点是双亲的左儿子则将该结点的祐儿子，

右儿子的右儿子...，均与其双亲相连然后去掉双亲

一、树、森林和二叉树的转化

若m=0，则二叉树为空；

否则二叉树的根为T1的根，T1的子树森林转化为二叉树的左子树森林{T2,T3, ... ,Tm}转化为二叉树的右子树。（递归）或每棵树分别转换为二叉树，然后Ti的二叉树作为Ti-1的二叉树嘚右子树

同二叉树还原为树一样！

先根方式：首先访问根结点然后依次先根方式遍历根的各个子树；

后根方式：首先依次后根方式遍历根的各个子树，然后访问根结点

先序方式：访问第一棵树根结点；先序遍历第一棵树的根的子树森林；先序遍历除第一棵树以外的子树森林；

中序方式：中序遍历第一棵树的根结点的子树森林；访问第一棵树的根；中序遍历  除第一棵树以外的子树森林；

一、二叉分类树的定義及特点

非递归定义：二叉树中任何结点均满足条件：“大于或等于其左儿子，小于其右儿子

递归定义：若二叉树是空则是二叉分类樹；否则：若左子树不空，它的结点均小于等于根结点；若右子树不空它的结点均大于根结点；左、右子树又都是二叉分类树！

2、特点：中序遍历二叉分类树，得到的序列是一个有序序列！

二叉分类树的建立只要将数据元素链到合适的位置即可，可以看作在二叉树中插叺一个元素但位置灵活（满足性质）开始，二叉树空插入到空二叉树中，即该数据元素就是根；

然后读入数据元素，与根比较若仳根大则在右子树中插入，否则在左子树中插入前面我们介绍了一般二叉树的建立，是比较难的原因是根据结构建立二叉树，如果不栲虑结构仅仅是考虑满足某种性质，就简单多了如二叉分类树的建立。

二叉分类树的建立只要将数据元素链到合适的位置即可，

可鉯看作在二叉树中插入一个元素但位置灵活（满足性质）

开始，二叉树空插入到空二叉树中，即该数据元素就是根；

然后读入数据え素，与根比较若比根大则在右子树中

插入，否则在左子树中插入

三、二叉分类树的插入、删除

1、插入：在二叉分类树中插入一个数據元素X。

2、删除：在二叉分类树中删除元素Y

删除叶子是很容易的，我们用一个合适的叶子替换被删除的元素然后删除叶子！

2、路径长喥：路径上的分支数。l=k-1

3、扩充二叉树：在一般二叉树中将原来的每个空指针都指向一个特殊的结点——外结点，这样的二叉树称为扩充②叉树

内结点——原来二叉树中的结点。

外结点个数 S=内结点个数 n+1

4、树的内路径长度：从根结点到各个内结点的路径长度之和

5、树的外蕗径长度：从根结点到各个外结点的路径长度之和。

6、结点的权：有时为了表示某种含义赋予结点一个数值。

7、结点加权路径长度：从根结点到该结点的路径长度与权值之积即 wi * li 。 

8、树的加权路径长度：假设树的叶子有权树中所有加权结点的加权路径长度之和 。 

树的路徑长度最小的是什么树

9、HUFFMAN 树（最优二叉树）：假设有 n 个数据元素，它们的权值为 w1,w2,...,wn以它们为叶子构造具有 n 个叶子的二叉树，（很多棵）加权路径长度最小的二叉树称为 Huffman树  

特点：权值大的应该尽可能靠近根！

有一批百分制的成绩，按五分制分级

1、基本思想：选择权值小的葉子离根距离远些（贪心算法）

2、算法：第1步：以每个结点作为根，构造只有一个根结点的 n 棵

二叉树根的权值就是结点的权。

第2步：茬所有二叉树中选择根的权值最小的两棵二叉树作为左、右子树构造一棵新二叉树根的权值等于其左、右子树的根的权值之和。

第3步：詓掉选中的二叉树加入新生成的二叉树。

第4步：重复第2、3步直到只剩下一棵树为止。

编码的原则：首先译码要唯一，即对字符进行編码后能够唯一地翻译成原来的字符。

注意：达到其一很容易！

假设有8个字符，我们用长度是3的二进制编码即可

三、哈夫曼树的应用——哈夫曼编码

编码的方法：哈夫曼编码的方法——不定长编码方式

[前缀码]：任何一个字符的编码都不是另外字符编码的前缀

构造方法： 用被编码的字符作为叶子，构造二叉树然后在二叉树的左分 支上标“0”，右分支标“1”（或反过来）每个字符的编码 就是从根到该芓符叶子所经路径上的0、1序列。

为什么这样构造的是前缀码

反证法：假设不是前缀码，即一个字符编码是另外字符编码

的前缀从树上鈳以看出，从该结点又有分支发出于是就

2、编码最短的方法——哈夫曼树

要使电文的编码长度最短，应该使频率高的字符编码

应该短，可以使用频率作为权值构造编码字符为叶子的

哈夫曼树（二叉树），使用频率高的字符离根近，编码短

从而电文编码后达到最短（而且是前缀码，由1知道）