第七章树和二叉树

1、树的应用树的应用w 某些数据库管理系统含有分层结构的数据库；复杂的程序，采用的基本数某些数据库管理系统含有分层结构的数据库；复杂的程序，采用的基本数据结构是树；据结构是树；w 在编译系统中，编译程序把高级语言的语句或表达式分解为树结构加以分在编译系统中，编译程序把高级语言的语句或表达式分解为树结构加以分析和处理，然后生成机器代码的目的码指令；析和处理，然后生成机器代码的目的码指令；w 操作系统的文件处理采用分级管理的办法，采用树结构，以提高文件的存操作系统的文件处理采用分级管理的办法，采用树结构，以提高文件的存取速度；取速度；w 某些操作系统把主存也按树结构划分，树中的每个结点包含数据或代码段

2、；某些操作系统把主存也按树结构划分，树中的每个结点包含数据或代码段；w 某些程序模块本身近似于树型结构；某些程序模块本身近似于树型结构；w 二叉排序树：特点是用非线性结构表示一个线性有序表；二叉排序树：特点是用非线性结构表示一个线性有序表；w 决策树：在企业的数据处理和系统分析等领域中出现的决策问题：即要求决策树：在企业的数据处理和系统分析等领域中出现的决策问题：即要求根据一些给定条件来确定应采取什么行动，如保险公司的业务决策；根据一些给定条件来确定应采取什么行动，如保险公司的业务决策；w 博弈树（博弈树（Game Tree）：人）：人机博弈；机博弈；w 堆（堆（heap）排序：实际上是一棵完

3、全二叉树结点的层次序列；）排序：实际上是一棵完全二叉树结点的层次序列；w Ldap： 轻量目录访问协议；轻量目录访问协议；w Huffman树：信息检索；树：信息检索；w 树例与特征树例与特征n社会的组织结构社会的组织结构n家族的族谱家族的族谱n计算机中的目录组织计算机中的目录组织w 描述层次结构，是一种描述层次结构，是一种一对多一对多的逻辑关系的逻辑关系是一种非线性结构是一种非线性结构树的形式化定义树的形式化定义 树：树：T=D,R。D是包含是包含n个节点的有穷集合（个节点的有穷集合（n0）。）。当当n=0时为空树，否则关系时为空树，否则关系R满足以下条件满足以下条件: l 有且仅有一个节点

4、有且仅有一个节点d0D，它对于关系，它对于关系R来说没来说没有前驱节点，节点有前驱节点，节点d0称作树的称作树的根节点根节点。l 除节点除节点d0外，外，D中的每个节点对于关系中的每个节点对于关系R来说都来说都有且有且仅有一个前驱节点仅有一个前驱节点。l D中每个节点对于关系中每个节点对于关系R来说可以有来说可以有零个或多个零个或多个后继节点后继节点。7.1 7.1 树的基本概念及其树的基本概念及其ADTADT定义定义 7.1.1 树的定义树的定义树的递归定义：树的递归定义： 树树是由是由n（n0）个节点组成的有限集合（记为）个节点组成的有限集合（记为T）。其中：）。其中： l 如果如果n=0

5、，它是一棵空树，这是树的特例；，它是一棵空树，这是树的特例；l 如果如果n0，这，这n个节点中存在（且仅存在）一个节点个节点中存在（且仅存在）一个节点作为树的根节点，简称为根节点（作为树的根节点，简称为根节点（root），其余节点），其余节点可分为可分为m （m0）个互不相交的有限集）个互不相交的有限集T1,T2,Tm,其其中每一棵子集本身又是一棵符合本定义的中每一棵子集本身又是一棵符合本定义的树树，称为，称为根根root的子树。的子树。rootT1T2Tm树定义树定义ACBGFEHIJDMKLAT1T2T3树的抽象数据类型树的抽象数据类型ADT Tree 数据对象数据对象 D：D是具有相同性

6、质的数据元素的集合。是具有相同性质的数据元素的集合。 数据关系数据关系R：若：若D为空集，则称为空树；若为空集，则称为空树；若D仅含有一个数据元仅含有一个数据元素，则素，则R为空集，否则为空集，否则R=H，H是如下二元关系：是如下二元关系： （1 1）在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root，它在关系，它在关系H下下无前驱；无前驱； （2）若）若D-root,则存在则存在D-root的一个划分的一个划分D1，D2Dm（m0）,对任意对任意 j k(1 j,k m)有有 Dj DK= ,且对任意的且对任意的 i(1 i m ),存在唯一的数据元素存在唯一的数据元素x

7、i Di , H; （3）对应于）对应于D-root的划分，的划分，H-,有唯有唯一的一个划分一的一个划分H1, H2,Hm(m0),对任意对任意j k(1 j,k m)有有Hj Hk= ,且对任意且对任意i(1 i m )，Hi是是Di上的二元关系，上的二元关系， ( (Di，Hi）是一棵符合本定义的树，称为根）是一棵符合本定义的树，称为根root的子树。的子树。 注意：注意：“”是集合的补运是集合的补运算，算，“ ”是集合的交运算是集合的交运算基本操作：基本操作： TreeInit(T); TreeChild (T,x,i); Treebuild(T,F); TreeClear(T); T

8、raverse (T); TreeRoot(T); TreeParent(T,x); TreeRightBrother(T,x); TreeLeftBrother(T,x); TreeInsert(T,y,i,x);ADT Tree树的抽象数据类型树的抽象数据类型7.1.2 树的表示树的表示 （1）树形表示法。）树形表示法。这是树的最基本的表示，使用一棵倒这是树的最基本的表示，使用一棵倒置的树表示树结构，非常直观和形象。下图就是采用这种表置的树表示树结构，非常直观和形象。下图就是采用这种表示法。示法。ABCDEFGJHIKLM逻辑结构表示逻辑结构表示1 （2）文氏图表示法。）文氏图表示法。使用

9、集合以及集合的包含关系描述树结使用集合以及集合的包含关系描述树结构。下图就是树的文氏图表示法。构。下图就是树的文氏图表示法。ABCDEFGJHIKLM逻辑结构表示逻辑结构表示2AEFBCGJHDKLMI （3）凹入表示法。）凹入表示法。使用线段的伸缩描述树结构。下使用线段的伸缩描述树结构。下图是树的凹入表示法。图是树的凹入表示法。逻辑结构表示逻辑结构表示3ABCDEFGJHIKLM（4）括号表示法。）括号表示法。将树的根节点写在括号的左边，除将树的根节点写在括号的左边，除根节点之外的其余节点写在括号中并用逗号间隔来描述根节点之外的其余节点写在括号中并用逗号间隔来描述树结构。下图是树的括号表示法

10、。树结构。下图是树的括号表示法。 括号表示法括号表示法 A(B(E,F),C(G(J),D(H,I(K,L,M) ABCDEFGJHIKLM树的其它逻辑表示方式树的其它逻辑表示方式ACBGFEHIJDMKLAJIMHDGCFLKEB凹入表示法凹入表示法ABFEKLGCDHMIJ嵌套集合表示法嵌套集合表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)广义表表示法广义表表示法树型表示法树型表示法类似于书的编目类似于书的编目 7.1.3 树的基本术语树的基本术语 1. 节点的度与树的度：节点的度与树的度：树中某树中某个节点的子树的个数称为该节点的个节点的子树的个数称为该节点的度。树

11、中各节点的度的最大值称为度。树中各节点的度的最大值称为树的度，通常将度为树的度，通常将度为m的树称为的树称为m次树次树。 2. 分支节点与叶节点：分支节点与叶节点：度不为零的节点称为非终端节点度不为零的节点称为非终端节点,又叫分支节点。度为零的节点称为终端节点或叶节点。在分又叫分支节点。度为零的节点称为终端节点或叶节点。在分支节点中，每个节点的分支数就是该节点的度。如对于度为支节点中，每个节点的分支数就是该节点的度。如对于度为1的节点的节点,其分支数为其分支数为1，被称为单分支节点；对于度为，被称为单分支节点；对于度为2的节的节点，其分支数为点，其分支数为2，被称为双分支节点，其余类推。，被称

12、为双分支节点，其余类推。ABCDEFGJHIKLM度为度为3度为度为2ABCDEFGJHIKLM度为度为3度为度为2 3. 路径与路径长度：路径与路径长度：对于任意对于任意两个节点两个节点di和和dj，若树中存在一个节，若树中存在一个节点序列点序列di,di1,di2,din,dj，使得序列中，使得序列中除除di外的任一节点都是其在序列中的外的任一节点都是其在序列中的前一个节点的后继，则称该节点序前一个节点的后继，则称该节点序列为由列为由di到到dj的一条路径，用路径所的一条路径，用路径所通过的节点序列通过的节点序列(di,di1,di2,dj)表示表示这条路径这条路径。 路径长度路径长度等于

13、路径所通过的节点等于路径所通过的节点数目减数目减1（即路径上分支数目）。（即路径上分支数目）。ABCDEFGJHIKLMA到到K的路径为（的路径为（A,D,I,K）其长度为其长度为3 4. 孩子节点、双亲节点和兄弟节孩子节点、双亲节点和兄弟节点：点：在一棵树中，每个节点的后继，在一棵树中，每个节点的后继，被称作该节点的孩子节点（或子女节被称作该节点的孩子节点（或子女节点）。相应地，该节点被称作孩子节点）。相应地，该节点被称作孩子节点的点的双亲节点双亲节点（或父母节点）。（或父母节点）。 具有同一双亲的孩子节点互为兄弟具有同一双亲的孩子节点互为兄弟节点。进一步推广这些关系，可以把节点。进一步推广

14、这些关系，可以把每个节点的所有子树中的节点称为该每个节点的所有子树中的节点称为该节点的节点的子孙节点子孙节点。从树根节点到达该节点的路径上经从树根节点到达该节点的路径上经过的所有节点被称作该节点的过的所有节点被称作该节点的祖先节祖先节点点。ABCDEFGJHIKLM 5. 节点的层次和树的高度：节点的层次和树的高度：树树中的每个节点都处在一定的层次上。中的每个节点都处在一定的层次上。节点的层次从树根开始定义，根节节点的层次从树根开始定义，根节点为第点为第1层，它的孩子节点为第层，它的孩子节点为第2层层,以此类推以此类推,一个节点所在的层次为一个节点所在的层次为其双亲节点所在的层次加其双亲节点所

15、在的层次加1。树中。树中节点的最大层次称为树的节点的最大层次称为树的高度高度（或（或树的树的深度深度）。）。 6. 有序树和无序树：有序树和无序树：若树中各若树中各节点的子树是按照一定的次序从左节点的子树是按照一定的次序从左向右安排的，且相对次序是不能随向右安排的，且相对次序是不能随意变换的，则称为意变换的，则称为有序树，有序树，否则称否则称为为无序树无序树。ABCDEFGJHIKLM1234有的教材规定为第有的教材规定为第0层层一般讨论无序树一般讨论无序树树和其子树之间的次序树和其子树之间的次序w 有序树有序树和和无序树无序树之间的区别在于：之间的区别在于： 子树之间是否存在次序关系。子树之

16、间是否存在次序关系。ACBGFEHIJDMKL 如果讨论的是无序树，则这两棵树是等同如果讨论的是无序树，则这两棵树是等同的，否则是不等同的。的，否则是不等同的。 此书一般讨论无序树此书一般讨论无序树 7. 森林：森林：n（n0）个互不相交的树的集合称为森）个互不相交的树的集合称为森林。森林的概念与树的概念十分相近，因为只要把树的林。森林的概念与树的概念十分相近，因为只要把树的根节点删去就成了森林。反之，只要给根节点删去就成了森林。反之，只要给n棵独立的树加棵独立的树加上一个节点，并把这上一个节点，并把这n棵树作为该节点的子树，则森林棵树作为该节点的子树，则森林就变成了树。就变成了树。 任何一棵

17、非空树是一个二元组任何一棵非空树是一个二元组 Tree=(root,F) 其中：其中：root被称为根结点被称为根结点 F被称为子树森林被称为子树森林注意与自然界中的树和注意与自然界中的树和森林的概念不同。森林的概念不同。概念示例w 结点结点w 结点的度结点的度(Degree)(Degree)w 叶子（叶子（Leaf)Leaf)或终端结点或终端结点w 分支结点或非终端结点分支结点或非终端结点w 树的度树的度w 层次层次(Level)(Level)w 树的深度树的深度(Depth)(Depth)w 孩子（孩子（child)child)w 双亲（双亲（Parent)Parent)w 兄弟兄弟(Si

18、bling)(Sibling)w 祖先祖先w 子孙子孙ACBGFEHIJDMKL树的基本操作树的基本操作w分为分为三大类：三大类： 查找查找 插入插入 删除删除查找操作查找操作w 分为特定的查找和按关系的查找分为特定的查找和按关系的查找 特定的查找特定的查找 Root(T); Value(T,cur_e); 按关系的查找按关系的查找 Parent(T, cur_e); LeftChild(T, cur_e); RightSibling(T, cur_e); 某些特性的判别某些特性的判别 TreeEmpty(T); TreeDepth(T); 特殊的操作特殊的操作 TraverseTree(T,

19、Visit( ); 查找树中值为查找树中值为cur_e的某个结点的某个结点 查找树中值为查找树中值为cur_e的的结点的最左边的孩子结点的最左边的孩子插入操作插入操作w InitTree(&T ); CreatTree(&t,definition); Assign(&T,cur_e,valus); InsertChild(&T,&p,i,c); 根据定义生成树，如根据定义生成树，如给定树根和子树森林给定树根和子树森林可以生成树可以生成树 改变树上某改变树上某个结点的值个结点的值 插入一棵子树，如在树插入一棵子树，如在树T中指针中指针p所指的位置插入一棵以

20、所指的位置插入一棵以c为根的子为根的子树，并且作为第树，并且作为第i棵子树棵子树删除操作删除操作w ClearTree(&T) DestroyTree(&T); DeleteChild(&T,&p,i); 删除树删除树T中某个中某个结点的某个子树结点的某个子树w一般讨论的是一般讨论的是有向树（箭头略去不画）：有向树（箭头略去不画）： 1） 有确定的根；有确定的根； 2） 树根和子树根之间为有向关系树根和子树根之间为有向关系;树结构和线性结构的比较树结构和线性结构的比较 线性结构线性结构树结构树结构 第一个数据元素第一个数据元素 （无前驱）（无前驱）根结点根结点

21、（无前驱）（无前驱）最后一个数据元素最后一个数据元素 （无后继）（无后继）多个叶子结点多个叶子结点 （无后继）（无后继）其他数据元素其他数据元素 （一个前驱，（一个前驱， 一个后继）一个后继）树中其他结点树中其他结点 （一个前驱，（一个前驱， 多个后继）多个后继）一对一一对一一对多一对多7.2 二叉树二叉树w7.2.1 二叉树的概念二叉树的概念w 二叉树二叉树(Binary Tree)(Binary Tree)：或者是一棵空树，或者是一棵空树，或者是一棵由一个根结点和两棵或者是一棵由一个根结点和两棵互不相交互不相交的的左子树左子树和和右子树右子树所组成的非空树，左子所组成的非空树，左子树和右子

22、树又同样都是二叉树树和右子树又同样都是二叉树。w 特征特征：n每个结点最多只有两棵子树每个结点最多只有两棵子树n子树有左右之分，其次序不能任意颠倒子树有左右之分，其次序不能任意颠倒许多实际问题抽象出来的数据许多实际问题抽象出来的数据结构往往是二叉树的形式结构往往是二叉树的形式ABECDFGHK 根结点根结点A的左子树的左子树 根结点根结点A的右子树的右子树二叉树的二叉树的五种形态五种形态(a)(a)(b)(b)(c)(c)(d)(d)(e)(e)空树空树只有一个根结点的树只有一个根结点的树右子右子树为空树为空左子左子树为空树为空左右子树均非空左右子树均非空w 与有序树不同，即使只有一棵子树也要

23、区与有序树不同，即使只有一棵子树也要区分出是左子树还是右子树。分出是左子树还是右子树。有序树有序树右子树为空右子树为空左子树为空左子树为空 在一棵二叉树中在一棵二叉树中,如果如果所有分支节点都有左孩子节点和右孩所有分支节点都有左孩子节点和右孩子节点，子节点，并且并且叶节点都集中在二叉树的最下一层，这样的二叉叶节点都集中在二叉树的最下一层，这样的二叉树称为树称为满二叉树。满二叉树。下图所示就是一棵满二叉树。可以对满二叉树的节点进行下图所示就是一棵满二叉树。可以对满二叉树的节点进行连续编号，约定编号从树根为连续编号，约定编号从树根为1开始，按照层数从小到大、同开始，按照层数从小到大、同一层从左到右

24、的次序进行。图中每个节点外边的数字为对该节一层从左到右的次序进行。图中每个节点外边的数字为对该节点的编号。点的编号。 A B C D E H I J K F G L M N O 1 2 3 4 5 6 7 8 9 10 15 11 12 13 14 满二叉树满二叉树 若二叉树中最多若二叉树中最多只有最下面两层的节点的度数可以小于只有最下面两层的节点的度数可以小于2，并且并且最下面一层的叶节点都依次排列在该层最左边的位置上，最下面一层的叶节点都依次排列在该层最左边的位置上，则这样的二叉树称为则这样的二叉树称为完全二叉树。完全二叉树。 如下图所示为一棵完全二叉树。同样可以对完全二叉树中如下图所示为

25、一棵完全二叉树。同样可以对完全二叉树中每个节点进行连续编号，编号的方法同满二叉树相同。图中每每个节点进行连续编号，编号的方法同满二叉树相同。图中每个节点外边的数字为对该节点的编号。个节点外边的数字为对该节点的编号。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉树完全二叉树 189101112452673完全二完全二叉树叉树二叉树的抽象数据类型二叉树的抽象数据类型ADT BinTree 数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 数据关系数据关系R： 若若D= ，则，则R= ，称二叉树为空二叉树；

26、，称二叉树为空二叉树； 若若D，则，则R=H，H是如下二元关系：是如下二元关系： （1）在）在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root，它在关系，它在关系H下无前驱；下无前驱； （2）若）若D-root,则存在则存在D-root=D1,Dr,且且D1 Dr； （3）若）若D1，则，则D1中存在唯一的元素中存在唯一的元素x1, H,且存在且存在D1上的关系上的关系 H1 H；若；若Dr,则则Dr中存在唯一的元素中存在唯一的元素xr, H, 且存在且存在Dr上上的关系的关系Hr H；H=, H1, Hr; （4）（）（D1，H1）是一棵符合本定义的二叉树，称为根的左子树，

27、）是一棵符合本定义的二叉树，称为根的左子树， （Dr，Hr）是一棵符合本定义的二叉树，称为根的右子树。）是一棵符合本定义的二叉树，称为根的右子树。 二叉树的抽象数据类型二叉树的抽象数据类型 基本操作：基本操作： BinTreeInit (BT); BinTreeRoot(BT); BinTreeParent(BT,x); BinTreeLeftChild (BT,x); BinTreeRightChild (BT,x); BinTreeBulid(BT,LBT,RBT); BinTreeInsertLeft(BT,y,x); BinTreeInsertRight(BT,y,x); BinTre

28、eDeleteLeft(BT,x); BinTreeDeleteRight(BT,x); BinTreeClear(BT); BinTraverse(BT);ADT BinTree 主要操作也是主要操作也是三类：三类：查找查找插入插入删除删除7.2.2 二叉树的性质二叉树的性质1.1.一个非空二叉树的第一个非空二叉树的第i i层上至多有层上至多有2 2i-1i-1个结点个结点（i i 1 1） 证明证明(用数学归纳法用数学归纳法)： i = 1, 只有根结点，只有根结点， 2i-1 201，显然成立，显然成立 设设i = k时成立，最多有时成立，最多有2k-1 当当i= k+1时，最多的结点个

29、数：时，最多的结点个数： 2k-1 * 2 = 2k-1+1 = 2k = 2( k+1)-1因为每个结点的度最多因为每个结点的度最多为为2，所以乘以，所以乘以27.2.2 二叉树的性质二叉树的性质2.2.深度为深度为k k的二叉树至多有的二叉树至多有2 2k k-1-1个结点个结点(k(k 1)1) 证明：由性质证明：由性质1 可知，只有每层的结点数达到可知，只有每层的结点数达到最大时，其树的结点数为最多。最大时，其树的结点数为最多。 二叉树的结点个数最多为：二叉树的结点个数最多为： 20 +21 +22 +2k-1 =1 + 2 + + 2k-1= 2k-1等比级数前等比级数前n项的求和公

30、式项的求和公式二叉树的性质二叉树的性质3.3.对任意一棵非空二叉树对任意一棵非空二叉树BTBT，如果其终端结点数为，如果其终端结点数为n n0 0，度，度为为2 2的结点数的结点数为为n n2 2，则，则n n0 0 = n = n2 2 +1; +1; 证明：证明： 设设n1为为BT中度为中度为1的结点数，则总结点数：的结点数，则总结点数：n = n0 + n1 + n2 另：除根结点外，所有结点都有且仅有一个双亲结点，另：除根结点外，所有结点都有且仅有一个双亲结点，也就是仅有一个分支进入，若也就是仅有一个分支进入，若B为分支数，则为分支数，则 n=B+1 由于这些分支是由度为由于这些分支是

31、由度为1或或2的结点射出的，所以又有：的结点射出的，所以又有： B=n1+2*n2 即：即： B=n1+2*n2 n-1； n= n1+2*n2 +1； 由式子由式子 和和 得到：得到： n0 + n1 + n2 n1+2*n2 +1; n n0 0 = n = n2 2 +1 +1填空题填空题w 如某二叉树有如某二叉树有20个叶子结点，有个叶子结点，有30个结点个结点仅有一个孩子，则该二叉树的总结点数为仅有一个孩子，则该二叉树的总结点数为_。w 【南京理工大学【南京理工大学 2001 二、二、3（2分）分）】w答案为：答案为： 69 根据二叉树性质根据二叉树性质3满二叉树（特殊形态的二叉树）

32、满二叉树（特殊形态的二叉树）w 满二叉树（满二叉树（Full Binary Tree）：深深度为度为k且有且有2k-1个结个结点的二叉树。点的二叉树。w 考虑到有序性，任一考虑到有序性，任一结点在树中都有确切结点在树中都有确切的位置，因此可以对的位置，因此可以对满二叉树进行编号。满二叉树进行编号。编号方式为：从上到编号方式为：从上到下，从左到右下，从左到右。189101112131415452673满二叉树满二叉树其特点是每一层上的结其特点是每一层上的结点树都是最大结点数。点树都是最大结点数。不存在度为不存在度为1的结点的结点完全二叉树（特殊形态的二叉树）完全二叉树（特殊形态的二叉树）w 完全

33、二叉树完全二叉树(Completed Binary Tree)：深度为深度为k，有有n个结点的二叉树，当个结点的二叉树，当且仅当其每一个结点都与且仅当其每一个结点都与深度为深度为k的满二叉树编号的满二叉树编号从从1到到n的结点一一对应时，的结点一一对应时，称为完全二叉树。称为完全二叉树。w 特征：特征：n叶子结点只可能在层次叶子结点只可能在层次最大的两层上出现最大的两层上出现n任一结点，若其右分支任一结点，若其右分支下的子孙的最大层次为下的子孙的最大层次为l，则其左分支下的最大层则其左分支下的最大层次为次为l或或l+1.189101112452673完全二完全二叉树叉树满二叉树是完全二叉满二叉

34、树是完全二叉树的树的 一种特殊情况一种特殊情况完全二叉树的性质完全二叉树的性质1.1.具有具有n n个结点的完全二叉树的深度为：个结点的完全二叉树的深度为： k = k = loglog2 2(n+1)(n+1) （ x 表示不小于表示不小于x的最小整数，如的最小整数，如 6.1 =7，即向上取，即向上取整整 ） 证明：设树的深度为证明：设树的深度为k，则由完全二叉树的定义和性质，则由完全二叉树的定义和性质 2 可知：可知： 2k-1 1 n 2k 1 或：或： 2k-1 n+1 2k 取对数后：取对数后： k-1 log2(n+1) k 由于由于k是整数，是整数， k = log2(n+1)

35、 完全二叉树的性质完全二叉树的性质或有的教材：或有的教材：1.1.具有具有n n个结点的完全二叉树的深度为：个结点的完全二叉树的深度为： k = k = loglog2 2n n +1 +1（ x 表示不大于表示不大于x的最大整数，如的最大整数，如 6.9 =6，即向下取整，即向下取整 ） 证明：设树的深度为证明：设树的深度为k，则由完全二叉树的定义和性质，则由完全二叉树的定义和性质 2 可知：可知： 2k-1 1 n 2k 1 或：或： 2k-1 n 2k 取对数后：取对数后： k-1 log2n 0时与上页的描述等效，当时与上页的描述等效，当n=0时此定义就没有意义了。）时此定义就没有意义

36、了。）填空题填空题w 一个有一个有2001个结点的完全二叉树的高度为个结点的完全二叉树的高度为_。w 【南京理工大学【南京理工大学 1997 三、三、2（1分）分）】 答案为：答案为：11k = log2(n+1) log22002 11 或：或： k = log2n + 1= log22001 + 1=10+1=11完全二叉树的性质完全二叉树的性质2.2.如果将一棵有如果将一棵有n n个结点的完全二叉树自顶向下，个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号同一层自左向右连续给结点编号1 1、2 2、3 3n,n,则对任一结点则对任一结点i i（1 1 i i n n）有：）有：

37、（a）如果）如果i=1,此结点为根结点，无双亲；若此结点为根结点，无双亲；若i1,则则其双亲结点是其双亲结点是 i/2 。 （b）如果）如果2in,则结点则结点i无左孩子，无左孩子，i为叶子结为叶子结点点,否则否则其左孩子是结点其左孩子是结点2i。 （c）如果）如果2i+1n，则结点，则结点i无右孩子，否则无右孩子，否则其其右孩子是结点右孩子是结点2i+1。 完全二叉树示意图完全二叉树示意图2i2i2i+12i+1i i2i+22i+22i+32i+3i+1i+1 i/2i/2 j 层层j+1层层结点结点i i和和i i1 1在同一层上在同一层上完全二叉树示意图完全二叉树示意图2i+22i+2

38、2i+32i+3i+1i+12i2i2i+12i+1i i.2i2i2i+12i+1i i2i+22i+22i+32i+3i+1i+1LCHILD(i)LCHILD(i+1)RCHILD(i)RCHILD(i+1) i/2i/2 结点结点i i和和i+1i+1不在同一层上不在同一层上满二叉树是完全二叉树的一满二叉树是完全二叉树的一种特殊形式种特殊形式 性质性质4 对完全二叉树中编号为对完全二叉树中编号为i的节点（的节点（1in，n1，n为节点数）有：为节点数）有： （1）若）若i n/2 ，即即2in，则编号为，则编号为i的节点为分支节点，的节点为分支节点，否则为叶子节点。否则为叶子节点。 （

39、2）若）若n为奇数，则每个分支节点都既有左孩子节点，为奇数，则每个分支节点都既有左孩子节点，也有右孩子节点；若也有右孩子节点；若n为偶数，则编号最大的分支节点只有为偶数，则编号最大的分支节点只有左孩子节点，没有右孩子节点，其余分支节点都有左、右孩左孩子节点，没有右孩子节点，其余分支节点都有左、右孩子节点。子节点。i/2i2i2i+1教材教材P.163.与上述完全二叉树性质与上述完全二叉树性质2的的不同表述不同表述 （3）若编号为）若编号为i的节点有左孩子节点，则左孩子节点的编的节点有左孩子节点，则左孩子节点的编号为号为2i；若编号为；若编号为i的节点有右孩子节点，则右孩子节点的编的节点有右孩子

40、节点，则右孩子节点的编号为号为(2i+1)。 （4）除树根节点外）除树根节点外,若一个节点的编号为若一个节点的编号为i，则它的双亲，则它的双亲节点的编号为节点的编号为 i/2 ，也就是说，当，也就是说，当i为偶数时，其双亲节点的为偶数时，其双亲节点的编号为编号为i/2,它是双亲节点的左孩子节点，当它是双亲节点的左孩子节点，当i为奇数时，其双为奇数时，其双亲节点的编号为亲节点的编号为(i-1)/2，它是双亲节点的右孩子节点。，它是双亲节点的右孩子节点。练习题练习题w 在下述结论中，正确的是（在下述结论中，正确的是（ ）w 【南京理工大学【南京理工大学 1999 1999 一、一、4 4 （1 1

41、分）分）】w 只有一个结点的二叉树的度为只有一个结点的二叉树的度为0; 0; w 二叉树的度为二叉树的度为2 2； w 二叉树的左右子树可任意交换二叉树的左右子树可任意交换; ;w 深度为深度为K K的完全二叉树的结点个数小于或等于深度相的完全二叉树的结点个数小于或等于深度相同的满二叉树。同的满二叉树。 w A A w B B w C C w D Dw 答案为：答案为：w D练习题练习题w 若一棵二叉树具有若一棵二叉树具有1010个度为个度为2 2的结点，的结点，5 5个个度为度为1 1的结点，则度为的结点，则度为0 0的结点个数是（的结点个数是（ ）w A A9 9 w B B11 11 w

42、 C C15 15 w D D不确定不确定 w 【北京工商大学【北京工商大学20012001一一.7(3.7(3分分) )】w 答案为：答案为： B 二叉树性质二叉树性质 3练习题练习题w 具有具有1010个叶结点的二叉树中有（个叶结点的二叉树中有（ ）个度）个度为为2 2的结点，的结点，w 【北京航空航天大学【北京航空航天大学2000 2000 一、一、5 5（2 2分分) )】w A A8 8 w B B9 9 w C C10 10 w D Dllllw 答案为：答案为： B二叉树性质二叉树性质 3练习题练习题w 有关二叉树下列说法正确的是（有关二叉树下列说法正确的是（ ）w 【南京理工大

43、学【南京理工大学 2000 2000 一、一、11 11 （1.51.5分）分）】w A A二叉树的度为二叉树的度为2 2 w B B一棵二叉树的度可以小于一棵二叉树的度可以小于2 2 w C C二叉树中至少有一个结点的度为二叉树中至少有一个结点的度为2 2w D D二叉树中任何一个结点的度都为二叉树中任何一个结点的度都为2 2w答案为：答案为： B练习题练习题w 二叉树的第二叉树的第I层上最多含有结点数为（层上最多含有结点数为（ ）w 【中山大学【中山大学1998二、二、7 （2分）分）】w 【北京理工大学【北京理工大学 2001 六、六、5（2分）分）】w A 2I w B 2I-1-1

44、w C 2I-1 w D 2I -1w 答案为：答案为： C 二叉树性质二叉树性质1练习题练习题w 一个具有一个具有1025个结点的二叉树的高个结点的二叉树的高h为（为（ ）w 【南京理工大学【南京理工大学 1999 一、一、19 （2分）分）】w A11 w B10 w C11至至1025之间之间 w D10至至1024之间之间w答案为：答案为： C 注意可能是单支树注意可能是单支树练习题练习题w 将有关二叉树的概念推广到三叉树，则一棵有将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（）个结点的完全三叉树的高度（）w A4 w B5 w C6 w D7 w 答案为：答

45、案为：w C w 根据完全二叉树性质根据完全二叉树性质1: k = log3245 6w 或或根据完全二叉树性质根据完全二叉树性质1: k = log3244 +1=5+1=6【南京理工大学【南京理工大学2000一、一、5 1.5分）分）】判断题判断题w 完全二叉树一定存在度为完全二叉树一定存在度为1的结点。的结点。w 【青岛大学【青岛大学 2002 一、一、4 （1分）分）】 w答案为：答案为： 错错判断题判断题w 深度为深度为K的二叉树中结点总数的二叉树中结点总数2k-1。w 【南京航空航天大学【南京航空航天大学 1995 五、五、1 （1分）分）】 w答案为：答案为： 对对判断题判断题w

46、 完全二叉树中，若一个结点没有左孩子，完全二叉树中，若一个结点没有左孩子，则它必是树叶。则它必是树叶。w 【东南大学【东南大学 2001一、一、1-8（1分）分）】w 【中科院软件所【中科院软件所1997一、一、2（1分）分）】w 【山东大学【山东大学2001一、一、4 (1分分)】w答案为：答案为： 对对判断题判断题w 下面二叉树的定义只有一个是正确的，请在正确的地方画下面二叉树的定义只有一个是正确的，请在正确的地方画“”。w （1）它是由一个根和两株互不相交的、称为左子树和右子树的）它是由一个根和两株互不相交的、称为左子树和右子树的二叉树组成。二叉树组成。w （2）（）（a）在一株二叉树的

47、级）在一株二叉树的级i上，最大结点数是上，最大结点数是2i-1（i1） （b）在一棵深度为）在一棵深度为k的二叉树中，最大结点数是的二叉树中，最大结点数是2k-1+1 （k1）。）。w （3）二叉树是结点的集合，满足如下条件：）二叉树是结点的集合，满足如下条件： （a）它或者是空集；）它或者是空集； （b）或者是由一个根和两个互不相交的、称为左子树和右）或者是由一个根和两个互不相交的、称为左子树和右子树的二叉树组成。子树的二叉树组成。w 【中科院自动化所【中科院自动化所1995一、一、2（6分）分）】w 答案为：答案为： （3）填空题填空题w 深度为深度为k的完全二叉树至少有的完全二叉树至少有

48、_(1)_个个结点，至多有结点，至多有_(2)_个结点。个结点。w 【厦门大学【厦门大学 2001 一、一、4 （5分）分）】w 【南京理工大学【南京理工大学 1999 二、二、5 （4分）分）】w答案为：答案为： （1） 2k-1 （2） 2k-1填空题填空题w 深度为深度为H 的完全二叉树至少有的完全二叉树至少有_(1)_个结点；个结点；至多有至多有_(2)_个结点；个结点；H和结点总数和结点总数N之间之间的关系是的关系是 (3)_。w 【中科院计算所【中科院计算所1998 一、一、3（3分）分）1999 二、二、4（3分）分）】w 【中国科技大学【中国科技大学 1998 一、一、3(4分

49、）分）】答案为：答案为： （1）2H-1 （2）2H-1 （3） H = log2(N+1) 或或H = log2N +1填空题填空题w 含含4个度为个度为2的结点和的结点和5个叶子结点的二叉个叶子结点的二叉树，可有树，可有_个度为个度为1的结点。的结点。w 【北京工业大学【北京工业大学 2001 一、一、6 (2分分)】w答案为：答案为： 0 至多个。至多个。 任意二叉树，度为任意二叉树，度为1的结点个数的结点个数没有限制。只有完全二叉树，度为没有限制。只有完全二叉树，度为1的结点个数才至多为的结点个数才至多为1选择题选择题w 一棵完全二叉树上有一棵完全二叉树上有1001个结点，其中叶子结点

50、的个数个结点，其中叶子结点的个数是（是（ ）w 【西安交通大学【西安交通大学 1996 三、三、2 (3分分)】w A 250 w B 500 w C254 w D505 w E以上答案都不对以上答案都不对w 答案为：答案为： Ew 由二叉树的结点公式：由二叉树的结点公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1,因为因为n1001，所以，所以10022n0n1，在完全二叉树中，在完全二叉树中，n1只能只能取取1或或0，在本题中只能取，在本题中只能取0（否则就是小数了），所以（否则就是小数了），所以n0501补充作业补充作业w 7.1 设树设树T的度为的度为4，其中度为

51、，其中度为1，2，3和和4的结点个数的结点个数分别为分别为4，2，1，1，求树，求树T中的叶子数。中的叶子数。w 7.2 一棵完全二叉树上有一棵完全二叉树上有1001个结点，求叶子结点的个结点，求叶子结点的个数个数 。w 7.3 一棵一棵124个叶结点的完全二叉树，最多有多少个个叶结点的完全二叉树，最多有多少个结点。结点。w 7.4 一棵完全二叉树有一棵完全二叉树有500个结点，请问该完全二叉个结点，请问该完全二叉树有多少个叶子结点？有多少个度为树有多少个叶子结点？有多少个度为1的结点？有多的结点？有多少个度为少个度为2的结点？如果完全二叉树有的结点？如果完全二叉树有501个结点，个结点，结果

52、如何？请写出推导过程。结果如何？请写出推导过程。 补充作业补充作业w 7.5 某二叉树有某二叉树有20个叶子结点，有个叶子结点，有30个结点仅个结点仅有一个孩子，则该二叉树的总结点数是多少。有一个孩子，则该二叉树的总结点数是多少。 w 7.6 一棵二叉树高度为一棵二叉树高度为h，所有结点的度或为，所有结点的度或为0，或为或为2，则这棵二叉树最少有多少结点。，则这棵二叉树最少有多少结点。 w 7.7 将有关二叉树的概念推广到三叉树，则一将有关二叉树的概念推广到三叉树，则一棵有棵有244个结点的完全三叉树的高度是多少。个结点的完全三叉树的高度是多少。 7.2.3 二叉树的存二叉树的存储储结构结构w

53、顺序存储结构顺序存储结构w链式存储结构链式存储结构二叉树的顺序存储结构二叉树的顺序存储结构 二叉树的顺序存储结构中节点的存放次序是：对该二叉树的顺序存储结构中节点的存放次序是：对该树中每个节点进行编号，其编号从小到大的顺序就是节点树中每个节点进行编号，其编号从小到大的顺序就是节点存放在连续存储单元的先后次序。存放在连续存储单元的先后次序。 若把二叉树存储到一维数组中若把二叉树存储到一维数组中,则该编号就是下标值则该编号就是下标值加加1（注意（注意C/C+语言中数组的起始下标为语言中数组的起始下标为0）。）。树中各节树中各节点的编号与等高度的完全二叉树中对应位置上节点的编号点的编号与等高度的完全

54、二叉树中对应位置上节点的编号相同。相同。 利用二叉树的性质利用二叉树的性质4。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉树完全二叉树 ABCDEFGHIJK123456789101112131415顺序存储结构（不用下标为顺序存储结构（不用下标为0的元素）的元素）ABCDEF A B D # C # E # # # # # # F 1 2 3 4 5 6 7 8 9 10 11 12 13 142511437一般的二叉树先用空节点一般的二叉树先用空节点补全成为完全二叉树，然补全成为完全二叉树，然后对节点编号后对节点编号typedef

55、ElemType SqBTreeMaxSize;SqBTree bt=ABD#C#E#F;顺序存储结构举例123456789101 18 89 910104 45 52 26 67 73 3完全二完全二叉树叉树顺序存储结构举例ABC非完全二非完全二叉树叉树XABCA B C 仅适用于完全二叉树仅适用于完全二叉树二叉树的链式存储结构二叉树的链式存储结构1. 二叉链表二叉链表 3. 双亲链表双亲链表2. 三叉链表三叉链表 4. 线索链表线索链表二叉树的链式存储结构二叉树的链式存储结构w 二叉链表二叉链表w 三叉链表三叉链表lchilddatarchilddatalchild rchildlchil

56、ddatarchildparentdatalchild rchildparent二叉树及其链式存储结构：二叉链表二叉树及其链式存储结构：二叉链表 ABCDEGFABDGCEFb链式存储结构示例ACFEDB二叉链表二叉链表三叉链表三叉链表ADBCEFbtABCDEFbtlchilddatarchildlchilddatarchildparent二叉链表的二叉链表的C表示表示 二叉树的二叉链表存储表示二叉树的二叉链表存储表示typedef struct BinNode ElemType data; struct BinNode * *lchild, * *rchild; 左右孩子指针左右孩子指针

57、BinTNode,*BinTree;二叉树的链式存储结构二叉树的链式存储结构 在二叉树的链接存储中，节点的结构如下在二叉树的链接存储中，节点的结构如下: typedef struct node ElemType data; struct node *lchild,*rchild; BTNode; 其中其中,data表示值域表示值域,用于存储对应的数据元素，用于存储对应的数据元素，lchild和和rchild分别表示左指针域和右指针域，用于分别存储左孩子节分别表示左指针域和右指针域，用于分别存储左孩子节点和右孩子节点（即左、右子树的根节点）的存储位置。点和右孩子节点（即左、右子树的根节点）的存储

58、位置。教材教材P.168.三叉链表的三叉链表的C表示表示 二叉树的三叉链表存储表示二叉树的三叉链表存储表示typedef struct TriNode ElemType data; struct TriNode * *lchild, * *rchild; 左右孩子指针左右孩子指针 struct TriNode * *parent；/双亲指针双亲指针 TriTNode,*TriTree;二叉树的双亲链表表示二叉树的双亲链表表示Typedef struct BPTNode TElemType data； int *parent; /指向双亲的指针指向双亲的指针 char LRflag；/左、右孩子

59、标志左、右孩子标志 BPTNodeTypedef struct BPTree BPTNode nodesMAX_TREE_SIZE; int num_node; /结点数目结点数目 int root; /根结点的位置根结点的位置 BPTree;ABDC A-1L或或R B 0L C 1R D 0R 0 1 2 3root=0num_node=47.2.4 7.2.4 二叉树的二叉树的遍历遍历 二叉树的遍历是指按照一定次序二叉树的遍历是指按照一定次序访问访问树中所树中所有节点，并且每个节点仅被访问一次的过程。有节点，并且每个节点仅被访问一次的过程。它是最基本的运算它是最基本的运算,是二叉树中所有

60、其他运是二叉树中所有其他运算的基础。算的基础。 “访问访问”的含义可以很广，如：输出结点的含义可以很广，如：输出结点的信息等。的信息等。 “ “遍历遍历”是任何类型都有的操是任何类型都有的操作。对线性结构而言，只有一条搜作。对线性结构而言，只有一条搜索路径（因为每个结点均只有一个索路径（因为每个结点均只有一个后继），故不需要另加讨论。而二后继），故不需要另加讨论。而二叉树是非线性结构，每个结点有两叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。样的搜索路径遍历的问题。对对“二叉树二叉树”而言，可以有而言，可以有三条三条搜索路搜索路径：径：1. 先上后下的按层次遍历；先上后下的按层次遍历；2.