6.2 二叉树和二叉树的性质在线视频

同学们大家好

我是云南大学信息学院的教师孔兵

这节课我们讨论二叉树和二叉树的性质

二叉树顾名思义，就是说树中结点最多只有两个分支

和普通的多分支的树比起来

树据元素之间的关系要简单一些

那么需要描述的关系也就少些

自然二叉树的存储相对来说容易实现

基于这样一个相对简单的存储结构

二叉树的操作实现起来

也比较容易

总结一下就是说，二叉树虽然也是非线性结构

比起普通的树来说，相对简单一些

所以，它的存储容易实现

实现算法也比较容易

二叉树在树结构的应用当中

起着非常重要的作用

为什么这么说呢？

难道现实当中很多问题都可以用二叉树来表示吗？

大家想一想，可能很难举出

需要用二叉树建模的例子

不能说没有，但是也确实不多

为什么我们还要重点讨论二叉树呢？

最核心的原因是：普通的树和森林

可以以某种方式转化为二叉的样子

就是说可以把树和森林转化为二叉树的样子

这样重点讨论二叉树的原因就清楚了

我们只需要把二叉树的存储和操作的问题解决了

那么普通的树和森林，都可以转换为二叉树

在二叉结构上实现普通的树和森林的存储及基本操作

有效控制了树和森林的存储结构及其运算中存在的复杂性

下面看一下二叉树的定义

每个结点至多只有两棵子树

并且，二叉树的子树有左右之分

其次序不能任意颠倒

二叉树的子树有左右之分，这个概念非常重要

下面我们通过一个例子来看一下

三个结点的二叉树的形态

在不考虑每个结点内容的情况下

我们只关注它的形态

如图所示的，因为二叉树的子树有左右之分

三个结点的二叉树有5种形态

再看三个结点的树的形态，只有2种

对比一下可以看到，二叉树中

下面有红色横线标识的这4棵树

在不考虑左右之分的情况下

本质上是一样的。所以在三个结点的树中

二叉树中这4种形态就只是红色横线标识的一种形态

因为二叉树每个结点最多有两个分支

所以二叉树有一些特殊的性质

下面呢我们一起来看一下

性质1，在二叉树的第i层

至多有2i-1个结点

从二叉树的定义可以看出

根是第1层，至多有一个结点

就是2的1减1次方=2的0次方

就是一个节点

根据二叉树的性质

第2层，至多2个

是在上一层结点个数的基础上乘2

就是2的2减1次方等于2的一次方

性质1用归纳法很容易证明

性质2，深度为k的二叉树至多有2k-1个结点

可以在性质1的基础上推导出来

深度为k的二叉树要结点最多

肯定每一层都必须是具有最多结点数

示例是一个4层的二叉树

每一层都有最多的结点数

那么k层的，就是把1到k层

每层的最大结点数相加即可

2的0次方+2的1次方+.....+2的k-1次方

结果就是2的k次方减1

性质3，对任何一棵二叉树T

如果其终端结点数为n0，度为2的结点数为n2

则n0 = n2+1

就是说二叉树中

0度结点个数和2度结点个数之间有这样一个关系

n0=n2+1.我们证明一下

设n1为二叉树中度1的结点个数

因二叉树中只有度为0，1，2的结点

设二叉树中结点总数为n

那么就可以给出公式6-1：n=n0+n1+n2

设B为分支数，图例中把一棵二叉树的分支表示为红色

在树当中，除了根结点外

每个结点都有一个唯一的前驱

从每个结点向上看

都有一个描述双亲（前驱）到自己关系分支

那么，如果图中有n个结点的话

这样的分支应该有n-1个，根没有

示例中结点个数是9，分支个数是8

分支数B=n-1

那么，n=B+1

所有的分支都是由一度和二度结点射出的

一度结点射出一个分支，二度结点射出两个分支

那么分支的总数B=n1+2n2

可以得到公式6-2：n=n1+2n2+1

公式6-1和6-2的左边都是n

可以把6-1代入6-2，就可以得到性质3，n0 = n2+1

下面看两种特殊形态的二叉树

满二叉树和完全二叉树

满二叉树是一棵深度为k

有2的k次方减1个结点的二叉树

回忆一下前面的性质2

可以注意到

所谓满二叉树就是每一层都达到最多结点树的二叉树

图中给出一个深度为4的满二叉树

它总的结点数是15个

我们给这棵满二叉树做了一个编号

从1开始编号，根的编号是1

编号的原则是自上而下

同一层，自左到右。4层的满二叉树

编号完成以后，样子如图中所示

完全二叉树，深度为k的

有n个结点的二叉树

当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时

我们称它为完全二叉树

怎么理解所谓编号一一对应呢？

我们看两个示例

图1中，二叉树有10个结点

结点个数n=10

前面我们看到过4层的满二叉树结点编号的情况

图1中，编号1~10的结点

和满二叉树中编号1~10的结点是一一对应

所以图1中的二叉树是一棵有10个结点的完全二叉树

图2总共有12个结点

我们注意到，图中编号1~11的结点

和满二叉树的编号1~11的结点是一一对应的

但是它的12号结点

对应的是满二叉树中编号为13的结点

并没有一一对应，所以图2不是一颗完全二叉树

如果把结点m删除

它就变为有11个结点的完全二叉树了

当然，满二叉树肯定是完全二叉树

完全二叉树是一种非常重要的二叉树

在很多问题当中都有应用

从形态来看，K层的完全二叉树

除了第k层，1到k-1都是满的，是k-1层的满二叉树

完全二叉树有以下两个特点

第1，叶子结点只可能出现在层次最大的两层上

第2，对任意结点。若其右分支下的子孙的最大层次为l

则其左分支下的子孙的最大层次为l或l+1

性质4，这是完全二叉树才有的性质

具有n个结点的完全二叉树的深度为log2n向下取整+1

我们做一下证明

设n个结点的完全二叉树深度为k

以4层的完全二叉树为例

最少结点个数是图1的8个

比3层的满二叉树多1个

最多是15个结点的满二叉树

那么，深度为k的完全二叉树

其结点个数一定大于k-1层满二叉树的结点个数

有2的k-1次方减1小于n

并且其结点个数一定一定小于等于K层的满二叉树

有n ≤2k-1

于是获得不等式

2的k-1次方减1小于 n

小于等于2的k次方减1

把减1去掉

得2的k减1次方小于等于 n 小于2的k次方

以2为底取对数

得k减小于等于 log2n 小于k

因为k是整数

log2n向下取整等于k减1

所以有k等于log2n向下取整+1

性质5，如果对一颗有n个结点的完全二叉树的结点编号

编号的方式我们前面已经说过

自上而下，自左至右

则对任意结点i, i指的是编号

有以下三条性质。

1. 如果i=1，则结点i是二叉树的根

没有双亲。如果i>1

则其双亲结点是编号为i除2向下取整的结点

2如果2i>n，则结点i无左孩子

否则，其左孩子是编号为2i的结点

3. 如果2i+1>n，则结点i无右孩子

否则，其右孩子是编号为2i+1的结点

我们看图总结一下性质3

对于编号为i的结点，其双亲如果存在

则双亲的编号是i/2。其左孩子如果存在

则左孩子是编号为2i。其右孩子如果存在

则右孩子是编号为2i+1

只需要证明2，3两条就可以了

因为第1条是被2，3两条所蕴含的

也就是说2，3成立，1一定成立。

下面看一下性质5，2,3两条性质的证明

采用的是归纳法。

i=1时，是根结点

左右孩子的编号是2,3

两条性质是成立的。

假设i=k时成立，i左孩子编号是2k

右孩子是2k+1。

那么i=k+1时就有两种情况

1. k是某层最后一个结点

那么，编号k+1的结点是下层的第1个结点

证明如图所示

设下一层为第j层，根据完全二叉树编号的情况

第j层第1个结点的编号是2的j减1次方

第j+1层的第1个结点的编号

是2的j次方

按从左到右编号的原则

第j+1层第2个结点的编号为2的j 次方加1

从二叉树的形态我们知道

第j+1层第1，2个结点是第j层第1个结点的左右孩子

从图中可以看出，两条性质是成立的

2. k+1是k同层的下一个结点

基于归纳假设，k+1的左孩子编号是2k+2=2（k+1）

右孩子编号是2k+3=2(k+1)+1，两条性质成立

好，同学们，这节课就讲到这

下节课再见。