讲解在线视频

本节，我们来学习二叉树及其性质

先来看二叉树的定义

树当中每一个结点至多有两个孩子

这时候的树就是二叉树

换句话说

二叉树当中不存在度为2的结点，结点的度

要么是0、1，或者2

比如这棵树

它就是一棵二叉树，树当中所有结点的孩子数最多只有2个

注意是最多

结点的孩子有左右之分

分别称为左孩子和右孩子

换句话说

这样一棵二叉树

它和这样一棵二叉树

是不等价的

因为，B和C作为A的孩子

是有左右之分的

二叉树有5种基本形态

第一种是空二叉树，结点数为0

我们用这样一种符号，来表示空二叉树；第二种

是仅仅包含一个根结点的二叉树

第三种，仅包含左子树的二叉树

第四种，仅包含右子树的二叉树

最后一种，同时包含左右子树的二叉树

需要注意，这里的L和R不一定是一个结点

它有可能是多个结点构成的

一般的二叉树

接下来，我们来看二叉树的性质

第i层最多有

2^(i-1)个结点

第一层，2^(1-1)，也就是1个结点(根结点)

第二层，2个孩子

最多有2个结点

第i层

我们可以很容易地证明，它有

2^(i-1)个结点，也就是每一层的结点数都达到最大

这时候，我们用数学归纳法，就可以证明出，第i层最多有2^(i-1)个结点

高度为k的二叉树，最多有2^k-1个结点

注意，这个减1

是在下面，并不是在指数的位置

如果每一层的结点数，都达到了2^(i-1)

那么，最后一累加，高度为k的

二叉树，最多就有2^k-1个结点

设树中度为i的结点数为ni，则有

n0=n2+1

我们知道，二叉树当中，所有结点的度要么是0

要么是1、要么是2，只有这三种结点

所以，二叉树中总的结点数，应该是这三种结点数之和

前面我们讲过树的性质

那么，二叉树作为一类特殊的树

它也应该满足树的特性

我们现在从下往上看，每一个结点

有且仅有一个父结点

换句话说

每一个结点都会向上引出一条边，除了根结点之外

那么

对于二叉树，边的数目

应该等于结点数减1

因为，根结点没有引出边

现在我们从下往上看

那些度为2的结点

会引出2条边，度为1的结点会引出1条边

比如，根结点A，它的度是2

那么，它会引出2条边

所以

从上往下看

整棵树，它的边的数目

应该是等于两倍的n2

加上一倍的n1

加上零倍的n0

我们综合这三个式子，就可以得出

n0=n2+1

这是二叉树的一个性质

这个推导

其实可以扩展到三叉树

一直到n叉树

比如三叉树

它里面有4种结点

也有一个与这个性质相类似的一个式子

这个

就留作大家课后的作业

自己来推导一下

现在，我们来看第三个概念

满二叉树，高度为k的二叉树

它就有2^k-1个结点

我们刚才讲的性质是最多有

现在就达到了最多

这时候的二叉树就是满二叉树

比如，这样一个高度为4的二叉树，结点数达到了2^4-1

一共15个

也就是，每一个结点都有两个孩子

当然，除了叶结点之外

现在，我们再来看完全二叉树

我们刚才讲的满二叉树

就是为了引出完全二叉树

完全二叉树是指高度为k，上k-1层是满二叉树

除了最下一层之外

上面的k-1层是满二叉树，第k层从右到左，连续缺少若干结点，注意，最下一层是从右到左

连续缺少若干结点

我们刚才讲的这棵满二叉树

它肯定是一棵完全二叉树

它的前3层是一棵满二叉树

最后一层，并没有缺少任何的结点

满二叉树一定是完全二叉树

现在，再来看第二棵树

高度为4，上3层是满的，最后一层缺少3个结点

分别是7的右孩子、左孩子、6的右孩子

那么，最后一层从右到左

连续缺少3个结点

这是可以的，满足完全二叉树的性质

再来看

第三棵树，第三棵树的

最后一层，它缺少了3的左孩子

3没有左孩子，却有右孩子

也就是说，最下一层

它并不是连续缺少，它是跳着

缺少的，不满足完全二叉树的定义

所以，它不是完全二叉树

对于完全二叉树来说

叶结点只可能出现在最下两层

比如第二棵树

红色的几个结点都是叶结点

那么，8、9、10...12

这些叶结点出现在最下层

但是，有一个叶结点7

它出现在了倒数第二层

这是可以的

叶结点可能出现在倒数第二层的最右边几个结点

我们后面会再看到一些完全二叉树

现在，我们来看完全二叉树的性质

如果我们从上到下

从左到右，依次对树当中每一个结点进行编号

比如这棵树

现在，我们来看它的第一个性质，n个结点的完全二叉树的高度

是log2(n)向下取整加1

假设，我们认为这棵二叉树的高度是k，根据完全二叉树的定义

它的上k-1层是一棵满二叉树

也就是说，树的总结点数应该是大于

2^(k-1)-1的

2^(k-1)-1就是高度为k-1的满二叉树

它的结点个数，注意，这地方不能取等号

因为，最后一层，也就是第k层

它至少要有一个结点

那它最多有多少个结点呢

也就是一个高度为k的满二叉树

它的结点数应该是2^k-1

这里

是可以取到等号的

现在为了方便计算

我们想办法把左右两边的减1都消掉

很简单

我们只需要在这里加一个等号，就行了

因为，n是整数

n要大于一个数减1

就相当于大于等于这个数

这里的等于号

可以删掉

基于相同的原理

现在，我们左右两边取对数

那就是k-1小于等于log2(n)

然后小于k

通过分析这个式子

其实很容易得到，k的取值

只能是log2(n)

向下取整加1，注意log2(n)

它有可能是一个小数

第二个性质，若i>1，则i的父结点为i/2向下取整

i>1，也就是从2开始，每一个结点

它的父结点的编号是i/2

比如，2的父结点，2/2是1；7的父结点，7/2，向下取整，是3

如果i小于等于1，只可能是i等于1

也就是根结点

根结点是没有父结点的

第三个性质

如果i小于等于n/2

对于这棵树来说

n是等于12的，那n/2就是6，i小于等于6

也就是6结点以及前面的结点

都是有左孩子的

并且，左孩子的编号就是2*i

比如，6的左孩子

2*6，是12；5的左孩子，5*2

是10

2的左孩子，2*2，是4

如果i超过了6

也就是从7开始，结点是没有左孩子的

没有左孩子，根据完全二叉树的定义

它肯定没有右孩子

所以，这时候的结点应该是叶结点

也就是图当中的红色结点

当i小于等于(n-1)/2的时候

i的右孩子是2*i+1

n的值是12

(n-1)/2应该是5.5

由于i只能取到整数

也就是说

到5结束，前面的结点都有右孩子

比如，5的右孩子

2*5+1，是11

2的右孩子，2*2+1，是5

那么，从第6个结点开始

一直到后面的结点，是没有右孩子的

后面的三个性质，我们在课后的讨论当中，会给出详细的推导过程

大家也可以在课下，自己来证明一下