第10讲 树和二叉树的定义

主讲人：陈红丽第6章树和二叉树1本章内容本章是重点章，二叉树又是本章的重点内容，我们要熟悉树的定义和相关术语，熟悉二叉树的定义、性质、存储结构、遍历，树的存储结构、遍历，树、森林与二叉树的转换，根据遍历序列画二叉树，哈夫曼树及哈夫曼编码等内容。算法的重点是二叉树的遍历及其有关应用。2第10讲树和二叉树的定义

主讲人：陈红丽3对比线性结构和树型结构的结构特点~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素

(无前驱)

根结点

(无前驱)最后一个数据元素

(无后继)多个叶子结点

(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱（双亲）多个后继（孩子）)4树的定义树是n（n≥0）个结点的有限集合，在任一棵非空树中：

(1)有且仅有一个称为根(root)的结点。

(2)其余结点可分为m个互不相交的集

合，而且其中的每一个集合本身又是

一棵树，称为根的子树。ABCDEFGHIJMKL注意：树的定义具有

递归性，即树

的定义中还有

树。5树的抽象数据类型的定义（自己看！）ADTTree{

数据对象：D是具有相同特性的数据元素的集合。

数据关系：

若D为空集，则称为空树；

若D中仅含一个数据元素，则关系R为空集；

否则R={H}，

(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；

(2)当n>1时，其余数据元素可分为m(m>0)个互不相交的(非空)有限集T1,T2,…,Tm,其中每一个子集本身又是一棵符合本定义的树，称为根root的子树，每一棵子树的根xi都是根root的后继，即<root,xi>∈H,i=1,2,…,m。

基本操作：}ADTTree6结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支拥有子树的个数树中所有结点的度的最大值度为0的结点度大于零的结点DHIJM树的基本术语7(从根到结点的)路径：孩子结点、双亲结点兄弟结点、堂兄弟结点祖先结点、子孙结点结点的层次:树的深度：由从根到该结点所经分支和结点元素构成ABCDEFGHIJMKL规定根结点为第1层，其它所有结点的层都是其父结点的层号加1树中叶子结点所在的最大层次空树深度为0非空树深度等于子树深度的最大值加1。8任何一棵非空树是一个二元组

Tree=（root，F）其中：root被称为根结点

F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合。m=0：空集；m=1：树

ArootBCDEFGHIJMKLF有序树、无序树：左右结点是否等价9ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先10树的逻辑结构

(特点)：一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。树的存储结构

讨论1：树是非线性结构，该怎样存储？

——仍然有顺序存储、链式存储等方式。

可规定为：从上至下、从左至右将树的结点依次存入内存重大缺陷：复原困难（不能唯一复原就没有实用价值）。讨论2：树的顺序存储方案应该怎样制定？11讨论3：树的链式存储方案应该怎样制定？可用多重链表：一个前驱指针，n个后继指针。细节问题：树中结点的结构类型样式该如何设计？

即应该设计成“等长”还是“不等长”？缺点：等长结构太浪费（每个结点的度不一定相同）不等长结构太复杂（要定义好多种结构类型）解决思路：先研究最简单、最有规律的树状结构，然后设法把一般的树转化为简单树。二叉树12二叉树定义或为空树，或是由一个根结点和两棵互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。特性二叉树中每个结点最多有两棵子树，即二叉树每个结点的度小于等于2子树有左右之分，不能颠倒——有序树二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念二叉树与度为2的树相同吗？为什么？？ABCDEFGHK根结点左子树右子树13ADTBinaryTree{

数据对象：D是具有相同特性的数据元素的集合。数据关系：

若D=Φ，则R=Φ；若D≠Φ，则R={H}；存在二元关系：①root唯一//关于根的说明②Dl∩Dr=Φ//关于子树不相交的说明③……//关于二元关系的说明

④……

//关于左子树和右子树的说明

基本操作：}ADTBinaryTree

二叉树的抽象数据类型的定义（自己看）14二叉树的基本形态根左子树根根右子树根右子树左子树(a)空二叉树

(b)只有根结点的二叉树

(c)左右子树都非空的二叉树

(e)左子树为空的二叉树

(d)右子树为空的二叉树15问：具有3个结点的二叉树可能有几种不同形态？并画出不同形态的二叉树。

答：有5种16二叉树的性质（3+2）讨论1：第i层的结点数至多是多少？

（利用二叉树的特性可轻松求出）

性质1:

在二叉树的第i层上至多有2i-1个结点（i>0）。性质2:

深度为k的二叉树至多有2k-1个结点（k>0）。2i-1个问题：第i层上至少有

个结点？1讨论2：深度为k的二叉树，至多有多少个结点？

（利用二叉树的特性可轻松求出）2k-1问题：深度为k时至少有

个结点？k17讨论3：二叉树的叶子数n0和度为2的结点数n2之间有

关系吗？性质3:

对于任何一棵二叉树，若2度的结点数有n2个，

则叶子数（n0）必定为n2＋1（即n0=n2+1）证明：∵二叉树中全部结点数n＝n0+n1+n2(叶子数＋1度结点数＋2度结点数)又∵二叉树中全部结点数n＝B+1

(总分支数＋根结点)

（除根结点外，每个结点必有且仅有一个直接前趋，即一个分支进入）而总分支数B=n1+2n2(1度结点必有1个直接后继，2度结点必有2个)三式联立可得：

n0+n1+n2=

n1+2n2+1,即n0=n2+1实际意义：叶子数＝2度结点数＋1ABCGEIDHFJ18在一棵度为3的树中，若有2个度为3的结点，有1个度为2的结点，则有

个度为0的结点。

A．4B．5

C．6

D．7C19两类特殊的二叉树满二叉树完全二叉树深度为k且有2k-1个结点（特点：每层都“充满”了结点）深度为k，前k-1层是满二叉树，第k层的结点从左至右依次排列。123114589121367101415123114589126710结点层序编号：从根结点起自上而下逐层（层内自左至右）对二叉树的结点进行连续编号。20性质4：具有n个结点的完全二叉树的深度为()。假设该完全二叉树的深度为k，则根据完全二叉树的定义和性质2有：

2k-1≤n＜2k

所以有：k－1≤log2n＜k

又因为k是整数，所以，k＝log2n＋1log2n＋1深度为K的完全二叉树结点数是（）2k-1-1<n≤

2k-121性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点

i(1≤i≤n)，有：1、如果i=1，则结点

i是二叉树的根，无双亲；如果

i>1，则其双亲是（）结点2、如果

2i>n，则结点

i无左孩子，为叶结点；否则其左孩子是结点（）。3、如果

2i+1>n，则结点

i无右孩子；否则其右孩子是结点（）。i/22i2i+122习题：设一棵完全二叉树具有1000个结点，则它有

个叶子结点，有

个度为2的结点，有

个结点只有非空左子树，有

个结点只有非空右子树。10解：1）由于完全二叉树中最多只能出现右孩子为空的1个结点，所以度为1的结点有0个或1个2）由于二叉树中