数据结构-基于C++语言（微课版） 课件 1-3 二叉树的逻辑模型

满二叉树；完全二叉树；本节目录：本节内容：二叉树的基本性质树与二叉树的逻辑模型二叉树中结点个数与层次的关系；树与二叉树的逻辑模型二叉树性质:性质1：二叉树的第i层上至多有2i-1(i≥1)个结点。ABDDBACEBADCFC第2层个数：2、1、2第3层个数：1、2、3第1层个数：1、1、1深度为3的二叉树树与二叉树的逻辑模型二叉树性质:性质1：二叉树的第i层上至多有2i-1(i≥1)个结点。ACBEFFGDFFDFDFD11层次个数2

23

44

8第5层上最多几个结点？5

16树与二叉树的逻辑模型二叉树性质:性质1：二叉树的第i层上至多有2i-1(i≥1)个结点。ACBEFFGDFFDFDFDEBADGCF第4层8个结点树与二叉树的逻辑模型二叉树性质:性质2：二叉树的第i层上至多有2i-1(i≥1)个结点。证明：当i=1时：只有一个根结点2i-1

=20=1，命题成立。

假设对i>1时，处在第i-1层上至多有2(i-1)-1个结点。归纳知第i-1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i-1层上最大结点数的2倍。即2×2i-2＝2i-1

ACBEFFGDFFDFDFD树与二叉树的逻辑模型二叉树性质:性质2：深度为h的二叉树中至多含有2h-1个结点(h>=1)。ACBEFFGDFFDFDFD11深度总数2

33

74

15深度5，最多几个结点？5

31树与二叉树的逻辑模型二叉树性质:性质2：深度为h的二叉树中至多含有2h-1个结点(h>=1)。ACBEFFGDFFDFDFD证明：设第i层的结点数为xi，那么由性质1可以知道，第i层至少有一个结点，最多有2i-1结点，即1≤xi≤2i-1，深度为h的二叉树的结点数为M，则有：M=20+20+…+2i-1=2h-1树与二叉树的逻辑模型满二叉树：深度为h且含有2h-1个结点的二叉树。

结点编号是自上至下、自左至右。特点：每一层上的结点数都达到了最大值，叶子结点均在最底一层。152384796101112131415树与二叉树的逻辑模型完全二叉树：一棵有n个结点的二叉树，按与满二叉树相同的编号方式对结点进行编号，若树中n个结点和满二叉树1～n编号完全一致。152384796101112树与二叉树的逻辑模型非完全二叉树1523847961011小结：理解特殊二叉树特点；特殊二叉树判定条件；本节内容：二叉树的基本性质树与二叉树的逻辑模型根区分一般、特殊二叉树。152384796深度与个数的关系；不同度的结点间个数关系。本节目录：本节内容：二叉树的基本性质树与二叉树的逻辑模型树与二叉树的逻辑模型二叉树性质:性质3：n个结点的完全二叉树深度为：[㏒2n]+1。设完全二叉树的深度为h，则二叉树结点个数多有：？最少有：？树与二叉树的逻辑模型二叉树性质:性质3：n个结点的完全二叉树深度为：[㏒2n]+1。设完全二叉树的深度为h，则根据性质2及完全二叉树的定义有：2h-1≦n≦2h-1或2h-1≦n<2h

取对数得：h-1<㏒2n<h因为h是整数。∴h=㏒2n+115238479610树与二叉树的逻辑模型二叉树性质:性质4：在任意二叉树中，若有n0个叶子结点，n2个度为2的结点，则必有：n0=n2+1。DBACEBADCF树与二叉树的逻辑模型二叉树性质:性质4：在任意二叉树中，若有n0个叶子结点，n2个度为2的结点，则必有：n0=n2+1。DBACEBADCF证明：设n1为度为1的结点，则结点总数为：n=n0+n1+n2；又分支总数为：b=n1+2n2；

分支总数：b=n-1；所以:n0=n2+1。性质5：若对一棵有n个结点的完全二叉树(深度为

㏒2n

+1)的结点按层（从第1层到第

㏒2n

+1层)序自左至右进行编号,父