二叉树#

一、开车！#

二叉树的定义就是每个节点最多有两个孩子。

对于只有一个孩子或者叶子节点，我们在代码里的处理方法就是将地址设为NULL。

满二叉树(完美二叉树）：每一层都排满了，没有空缺，如下图，每个非叶子节点都有两个孩子。

严格二叉树：满足每个节点都是2个孩子或者0个孩子。就是下面的样子。

完全二叉树：除了最后一层，上面的所有层都排满了，最后一层节点靠左对齐，右边可以缺，但是中间不能空。如下图就不是完全二叉树，得把底下右边的搬到最左边才行。完美（满）二叉树也是一种完全二叉树。

二、属性#

1.同一深度的节点可以被称为同一级节点，树根的深度是0，所以层级为0。

上面就是分的多个层级啦！

上面图片里的树的最大深度等于树的高度。

2.如果我们对层级编号，像是这里的L-1一样的话，那么在第i层的最大节点数就为2的i次幂。

3.对于完美（满）二叉树，树的高度等于最大深度。

4.对于一颗高度为h的满二叉树树，最大的节点数量等于2**0+2**1+······2**h，结果就是2**(h+1)-1，这里的两个星号是立方的意思。也可以理解成2**（树的层级数目）-1，上图的层级数目是4！不是3！3是最大层级数。

5.假设n是一颗满二叉树的节点数量，那么树的高度h就等于log2(n+1)-1注意是以2为底！！！👌比如下图的n为15，那么可以用这个公式算出高度h为3

6.树的高度求解，可以简化为log2n向下取整数，还是以2为底哦！

三、时间开销#

很多操作花费的时间正比于树的高度，所以我们尽量避免高度过高。

对于n个节点来说，最小的高度是log2n（以2为底）的向下取整部分。

比如我们有这么一颗稀疏树，他的高度就是n-1。时间复杂度为O（n）！

由于时间开销与高度强相关，所以我们可以认为时间复杂度是O（h）。

那么对于一个满二叉树或者完全二叉树来说，时间复杂度会是O（log2n）依旧以2为底

当n非常大时，log2n远小于n，你可以在同一个坐标系里面画出这两个函数的图像，我想你一定能画出来🥰

所以我们尽量使高度小一点，或者说使二叉树尽量保持平衡。

这里提出了平衡二叉树：指的是对于每一个节点来说，左子树和右子树的高度不大于k，大多数时候k是1。换句话说就是左子树和右子树的高度差不应该超过1。

四、谈谈高度#

先回顾一下高度的概念

• 高度：可以被定义为该节点到一个叶子节点的最长路径上的边数。

对于只有一个节点的树（节点本身就是叶子）他的高度将为0.

我们可以定义一个空树，他的高度为-1。

对于一个节点来说，左树和右树的差异可以用左树和右树的高度差的绝对值来计算diff=|hleft-hright|。

一颗子树的高度也可以为-1。比如下图右下角，左子树和右子树都是空的，可以说左子树和右子树的高度为-1。

那么他们的差异就是|-1—1|=0

对于一颗满二叉树来说，所有节点的差异都是0。

我在图上标出了所有节点的差异。可以看到右边有一个diff为1的。

改成这样，就不再是平衡二叉树了！左边那个diff为2的节点，他的左子树高度为1，右子树为空也就是-1。

五、内存中保存二叉树#

下面是几个实现方法

• 动态创建节点（使用指针或者链表链接起来）

  1
  struct Node{
  2
    int data;
  3
    Node* left;
  4
    Node* right;
  5
  }

• 数组，常被用于完全二叉树。

  

  如何建立节点之间 的链接呢？对于索引为i的位置的节点，左孩的索引位置将会是2*i+1，右孩子的索引位置将会是2*i+2。ps：这点仅仅适用于完全二叉树！！！

卧槽，概念是真的多！！！💢

十点了，我的二次元纸片人老婆教我陪她了😎