↓跳到主要内容

二叉树

·5193 字·11 分钟
DS
目录

二叉树

二叉树是对通用树的限制得来，主要是限制树中每个节点的度最大值为2，也就是一个节点最多有两个子节点。类比一个顺序栈相比较于普通的顺序表来说，底层数据结构是相同的，都是一块连续的内存空间，但是因为操作受限，被限制只能在栈顶进行删除和插入。在通用树中，一颗树的度等于树中度最大的节点的度，那么，在二叉树中一个节点最多有两个子节点，它的度最大为2，也就是说一颗二叉树的度的最大值就是2。其实，也可以被限制为一个节点最多拥有三个子节点呀，那就是三叉树，也可以是四叉树。但是，二叉树已经成为行业学习的标准了，自然也就是规范了。学习即可，利用二叉树可以很好的锻炼递归和算法思维。

还是从最核心的概念说起：那么，什么是二叉树？

所谓二叉树，就是一棵树，其中每个节点最多可以有两个子节点。

Binary Tree，从Binary来看，它是二进制，代表着什么？二。有0和1，所以你可以理解为一颗每个节点最多只能有两个子节点的树。最多两个，意味着每个节点可以有0个、一个或者两个子节点，但不能超过两个子节点。

04.svg

上图中的最后一个树就不是二叉树，因为顶层的G节点有三个子节点。其余的都是二叉树，要么一个节点中无子节点，要么是1个子节点，要么是2个子节点。

在内存中表示，在通用树中介绍过，实际也是类似链表，保存子节点地址的方式使得它们链接在一起。

假设一个节点的类型是：

1
2
3
4
5

struct node {
  elem_t data;
  node* left;
  node* right;
};

假设一颗二叉树的逻辑结构表示如下图：

one
one

对应的物理结构如下：每个节点的地址在内存中是不连续的。这只是画的有些像逻辑结构，但实际不是，它们在内存中是散落存储在内存中。

03.svg

当一个子节点有两个子节点的时候，那么它的左右两边地址域保存的就是左右子节点的地址；

如果只有左边或者右边有子节点，那么另外一边的地址域就是nullptr；

若无子节点，两边的地址域就都是nullptr。

这就是二叉树的魅力吧，两个地址域看上去就好看很多，哈哈哈。如果是通用树的话，若一个通用树中有一个子节点有7个子节点，那么你就需要定义一个包含7个地址域的节点，所有节点都要使用这个节点类型，那要多浪费内存，还有就是很不好看。

二叉树的性质

层数与节点个数的关系

看下面一个二叉树的图示：

two
two

从上往下看：最上面的是第0层，中间是第1层，最后是第2层。

  • 看第一层：那么现在，假设我取第一层，最多可能有多少个节点呢？答案是最多有两个节点，这里不可以有第三个节点，因为一个节点被限制只能最多有两个子节点。

  • 看第0层：最大的节点数只有1个。

  • 看第二层：虽然图中的节点数只有一个，但这不是最多的个数，第一层最多有两个子节点，那么到了第二层，第二层的最多节点数就是4个，绝对不是5个或者6个。

如果再增加一层呢？第三层的最多节点数为8个，这个可以通过第二层的最多节点数推算出来。所以，从第0层到第三层的最多节点数分别为0、2、4、8个，图画的不太好，不改了不改了。

three
three

所以，现在得出一个性质：二叉树在第i层的最大节点数是：

$2^{i}$

高度与节点个数的关系

保持与算法教材一致，只有根节点的二叉树的高度为0，因为它没有最深叶子节点，只有它自己，边数为0

最大节点数

在一个高度为h的二叉树中，可能存在的最大节点总数为多少呢？若求一颗固定高度为h的二叉树的最大节点数，那么这颗二叉树的节点排列必须是紧凑排列的，也就是图three。

一棵树的高度等于根节点的高度(这里差点记错了，以为是最远叶子节点的深度)，那么根节点的高度如何算呢？根节点的高度等于根节点到最远叶子节点的路径(也可以说是等于根节点到叶子节点的最远路径)。在上图中，最远叶子节点为第三层的所有节点，根节点到此叶子节点的路径就是经过的边数，就是3。所以此图中的二叉树的高度就是3，那么从第0层都3层的总节点数就是：0 + 2 + 4 + 8 = 14，需要计算的是从2的0次方到2的1次方到2的2次方到2的3次方一直加到2的h次方，这是一个等比数列，它的求和公式等于为：

$2^{h+1} - 1$

最小节点数

在一个高度为h的二叉树中，它的最小节点数是多少呢？其实很好算，既然高度为h，那么所拥有的每一层中的最少节点数为1，否则构不成一个层级，两个节点才能凑成一条边，最小节点数就是：

$h + 1$

对应的题目是已知高度为h的二叉树，求其节点数的范围：

  • 结点最多的时候，应该是这颗二叉树的每一层都放满了结点

  • 结点最少的时候，应该是这颗二叉树的每一层只有一个结点

所以，节点数的范围就是：

$h + 1 \leq n\leq 2^{h+1} - 1$

当二叉树退化为单链时，节点数最少，为：

  • 最小节点数：

    $h + 1$

当二叉树为满二叉树时，节点数最多，为：

  • 最大节点数：

    $2^{h + 1} - 1$

已知节点数，求最大高度和最小高度

若是已知二叉树实际有n个节点，它的高度的最小值和最大值是多少？

上述计算的是已知高度求出节点数的范围，那么已知节点数去求二叉树的高度，就需要考虑使用哪个公式来去计算，毕竟有一个最大节点数和一个最小节点数的公式。

求最小高度

想象一下，为了让二叉树的高度达到最小，二叉树中的节点排列就必须要紧凑一些，不是退化成单链表那种，越是紧凑，树的高度越小，因为有可能一层就可以放下剩下所有节点了，比如有3个节点，节点紧凑的放的话，两层足够，但是若是一层一个的话，就需要三层了。

所以，若是节点排列的非常紧凑的话，那么就可能会有一颗二叉树的最大节点数的情况，毕竟每一层都放满了。计算最小高度的公式可以使用已知二叉树高度计算最大节点数的公式：

$2^{ h + 1} - 1$

计算过程就是：

若一棵二叉树具有 n 个结点，那么要让高度尽可能小，必须满足：

$ n \leq 2^{h+1} - 1 $

移项可得：

$ n + 1 \leq 2^{h+1}$

两边取以2为底的对数：

$ \log_2(n+1) \leq h+1 $

因此：

$h \geq \log_2(n+1)-1$

由于二叉树的高度必须是整数，所以最小高度为：

其中，

$\lceil x\rceil$

表示对 x 进行向上取整

对于正整数n，该公式也可以等价地写成：

$ \boxed{ h_{\min} = \left\lfloor \log_2 n \right\rfloor } $

其中，

$\lfloor x\rfloor$

表示对 x 进行向下取整

  • 举个例子：

    当 n=5 时：

    $h_{\min} = \left\lceil \log_2(5+1) \right\rceil - 1 = \left\lceil \log_2 6 \right\rceil - 1 = 3-1=2 $

    所以，当节点数为5的时候，最小高度为2。这是因为

    $\log_{2}{6}$

    的值为(2,3)之间，那么减去1的话就为(1,2)之间，但是高度必须是整数，若向下取整的话，高度就为1，但是高度为1的二叉树最多只包含3个节点，这个可以通过已知高度求最大节点数公式可以计算出：

    $2^{1+1}-1=3 $

    向上取整的话，那么高度就是2，通过最大节点数公式计算得出：

    $2^{2+1}-1=7 $

    这是可以容纳5个节点的，所以，最小高度为2，因此，已知节点数，计算最小高度的公式就是：

    $h_{\min} = \left\lceil \log_2(n+1) \right\rceil - 1 $

    结点的紧凑排列就是(必须按照二叉树的特点来进行排列)：

    1
2
3
4
5

            ●
      /   \
     ●     ●
    / \   
   ●  ●

求最大高度

想象一下，什么情况下这棵树的高度最大，若是节点紧凑的排列在一起，那么只会使得这颗树高度变得更小。所以，必须使这些节点分散的排列，为了使得这颗二叉树的告诉尽量大，应当让二叉树尽可能的退化，每一层只保持一个节点，那么当高度为h时，至少需要

$h + 1$

个节点，若实际有n个节点，那么

$n \geq h + 1$

计算简单，h的最大值就是

$h\leq n - 1$

还是那个例子，当节点的个数n = 5 时，最大高度h为4，结点可以这样排列

1
2
3
4
5
6
7
8
9

●            高度 0
 \
  ●          高度 1
   \
    ●        高度 2
     \
      ●      高度 3
       \
        ●    高度 4

综合来看，当已知节点数为5的时候，它的高度范围为：

$2\leq h\leq 4$

  • 所谓的使用最大节点数求最小高度，指的就是使用固定高度下的最大节点数公式，反推出具有n个节点的二叉树所需的最小高度

  • 所谓的使用最小节点数求最大高度，指的就是使用固定高度下的最小节点数公式，反推出具有n个节点的二叉树所需的最大高度

在求两个极值时，应该分别选用哪一个边界公式。

二叉树的类型

二叉树的种类包括：满二叉树(full binary tree)，也可以称为真二叉树(proper binary tree)或严格二叉树(strict binary tree)，完全二叉树(complete binary tree)、完美二叉树(perfcet binary tree)、退化树(degenerate tree)以及平衡树(balanced tree)。

满二叉树(真二叉树、严格二叉树)

什么是满二叉树呢？它本质是一种二叉树，且每个节点要么有0个子节点，要么有2个子节点。换一种简单的说法，它首先是一颗二叉树，此外还需要满足一个条件，每个节点要么有0个子节点，要么有2个子节点，换句话说，除了叶子节点以外的节点，都恰好有2个子节点，不会出现1个子节点的节点。

binary_tree_03.drawio.svg

上图中的第一个二叉树就不是满二叉树，因为在层级为1的右边节点有一个子节点，这不符合满二叉树的特征。而第二个二叉树中除了0子节点的节点还有2个子节点的节点，没有1个子节点的节点，符合特征，因此它是满二叉树。

满二叉树的性质

满二叉树的一些性质，当判断一颗二叉树为满二叉树的时候，利用这些性质可以多一些解决问题的方法

  • 叶子节点与内部节点个数的关系

    若一颗二叉树是满二叉树的话，那么它的叶子节点的个数就等于内部节点的个数加1。在上图中，叶子节点的个数为3，那么内部节点的个数就是3 - 1 = 2，也确实是2。

  • 固定高度h的满二叉树的最大节点数

    最大节点数与普通二叉树是一样的，固定高度为h的二叉树的最大节点数的公式就是

    $2^{h + 1} - 1$

  • 固定高度h的满二叉树的最小节点数

    可以循序渐进的计算一下

    • 当高度为0时，只有一个根节点的时候，节点数为1，最少节点总数为1。

    • 当高度为1的时候，可以有多少节点，一个可以吗，看下图

      1
2
3

             ●
      /   
     ●

      高度为1的时候，只有一个节点是绝对不可以的，因为这不符合满二叉树中节点只有0个子节点或2个子节点的特征，不可以有1个子节点。

      1
2
3

             ●
      /  \
     ●    ●

      所以，高度为1的时候，必须是2个节点，所以当高度为1的时候，最少节点总数为3。

    • 当高度为2的时候，可以有多少节点，1个可以吗，与上述同理也是不可以的，为了满足满二叉树的特征，必须也至少有2个节点。为何，不能有0个节点，因为那样的话就不会多有一个层级，高度也就不会是2了。而层级为1的右边的节点在层级为2中没有子节点，因为我们要的是最少子节点，满足最小要求即可。

      1
2
3
4
5

             ●
      /  \
     ●    ● 
    / \
   ●   ●

      所以，高度为2的时候，最少节点总数为5。

    那么以此类推，计算最小节点总数的公式为：

    $2h + 1$

  • 已知满二叉树的节点数为n，求最小高度h

    与之前的思路相同，当节点数紧凑排列的时候，高度最小，也就是每一层都放满了节点，使用已知高度，计算最多节点数的公式与普通二叉树的计算相同

    $h_{\min} = \left\lceil \log_2(n+1) \right\rceil - 1 $

  • 已知满二叉树的节点数为n，求最大高度h

    与之前的思路相同，当节点数分散排列的时候，高度最大，也就是使用已知高度，计算最小节点数的公式。这个公式与普通二叉树的计算公式不同，因为满二叉树的限制，每一层不能全都是1个节点了。要利用下面这个公式计算最大高度：

    $h_{\max} = \frac{n - 1}{2}$

完全二叉树

什么是完全二叉树呢？根据完全二叉树的定义：一颗二叉树，若是所有层级都被完全填满，或者说除了最后一层外都被完全填满，但是对最后一层节点的排列还有要求：最后一层的节点必须尽可能的靠左排列。简单的来说，就是在填充最后一层时，是从左到右依次填充的。

  • 要么所有层都被填满

  • 最后一层可不被填满，但节点必须是从左到右依次排列，不可有空余的位置

binary_tree_04.drawio.svg

第三个并不是一个完全二叉树，因为最后一层的节点不是从左到右排列，因为中间空了一个位置。

它不要求最后一层一定是两个节点，也可以是一个节点，但必须是从左到右依次排列，也就是说必须先填充左子节点，再是右边。

完全二叉树的性质

  • 固定高度h的完全二叉树的最大节点数：

    在是完全二叉树之前，它先是一颗二叉树，所以，最大节点数是相同的，计算公式为：

    $2^{h + 1} - 1$

  • 固定高度h的完全二叉树的最小节点数：

    来简单的推导一下

    • 当高度为0时，0层的节点数为1，最小节点数也是1

    • 当高度为1时，0层的节点数为1，1层的节点数也可以为1，1层此时是最后一层，它的节点数可以是1，但必须是在最左边，最小节点数为2

    • 当高度为2时，0层的节点数为1，1层的节点数不可以为1了，此时它不是最后一层了，必须填满，因此节点数为2，2层的节点数可以是1，因为它是最后一层，那么最少节点数为4。

    根据规律，当高度为h的时候，完全二叉树的最小节点数为：

    $2^{h}$

  • 已知节点数求最大高度

    计算的思维是一样的，最大高度使用计算最小节点数的公式来求

    $h_{\max} = \log_{2}{n}$

    举个例子，假设节点数为5，那么按照公式计算的话得到的h的范围是(2,3)，若是向下取整的话，得到的数字为2，那么高度为2的完全二叉树的最大节点数就是

    $n = 2^{2 + 1} - 1 = 7$

    是可以容纳5个节点的，因此，已知节点数，计算此完全二叉树的最大高度为：

    $h_{\max} = \left\lfloor \log_2(n) \right\rfloor$

  • 已知节点数，求最小高度

    计算的思维也是和普通二叉树是一样的，最小高度使用计算最大节点数的公式来求，要向上取整

    $h_{\min} = \lceil\log_{2}{n + 1}\rceil - 1$

    若是向下取整的话，当节点数为5的时候，得到的最小高度为2 - 1 = 1，当高度为1时，最大的节点数为

    $2^{1 + 1} - 1 = 3$

    是容纳不了5个节点的，所以，必须是向上取整。当节点数为5的时候，得到的最小高度为3 - 1 = 2，当高度为2时，最大的节点数为

    $2^{2 + 1} - 1 = 7$

    是可以容纳5个节点的。

根据以上计算的情况，高度的范围是

$\lceil\log_{2}{n + 1}\rceil - 1\leq h\leq \left\lfloor \log_2(n) \right\rfloor$

对于正整数n，左右两边实际上是相等的，因此

$h = \left\lfloor \log_2(n) \right\rfloor = \lceil\log_{2}{n + 1}\rceil - 1$