1、简介

先来看下几个树形结构

树形图一.png

树形图二.png

上面两张图都是树形结构，图一为二叉树，图二为多叉树。
本文主要来看下二叉树相关的一些概念。

2、树相关的基本概念

1、节点、根节点、父节点、子节点、兄弟节点。

树只能有一个根节点，图二中的节点1即为根节点。同时也是节点2、3、4 、5、6的父节点。节点2、3、4 、5、6也是根节点1的子节点，由于它们的父节点都为节点1，所以它们是兄弟节点。而节点21和节点31不是兄弟节点，因为它们的父节点不同，分别为节点2和节点3。

2、一棵树可以没有任何节点，称为空树。
3、一棵树可以有一个节点，也就是只有根节点。
4、子树、左子树、右子树

image.png

图中红色圈中都是节点1的子树，其中绿色圈为节点5的子树，而左边的子树是节点5的左子树，右边的子树为节点5的右子树。
5、节点的度：节点的子树的个数
6、树的度：所有节点度中的最大值。
7、叶子节点：度为0的节点。
8、非叶子节点：度不为0的节点。
9、层数：根节点在第1层，根节点的子节点在第2层，以此类推，（也有的教程是从0开始的）
10、节点的深度：从根节点到当前节点的唯一路径上的节点总数。
11、节点的高度：从当前节点到最远叶子节点的路径上的节点总数。
12、树的深度：所有节点深度的最大值。
13、树的高度：所有节点高度的最大值。
14、树的深度等于树的高度。
15、有序树：树中任意节点的子节点之间有顺序关系。
16、无序树：树中任意节点的子节点之间没有顺序关系。

3、二叉树

3.1、二叉树的特点

1、二叉树中每个节点的度最大为2，每个节点最多有2个子树。
2、二叉树是有序树，左子树和右子树是有顺序的。
3、即使某节点只有一棵子树，也是要区分左右子树的。
4、二叉树也可以没有任何节点，即空树也是二叉树。
下图中的树都是二叉树
image.png

3.2、二叉树的性质

1、非空二叉树的第i层，最多有2^(n-1)个节点（i>=1）。
2、在高度为h的二叉树上最多有（2^0 + 2^1 +....+2^(h-1)）= 2^h-1个节点（h>=1）。
3、对于任何一个非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2，则由n0=n2+1。

推导如下：
1、二叉树中度为1的节点的个数为n1，则节点总数n=n0+n1+n2;
2、二叉树的边数：一个节点的度为多少，就代表该节点有多少边，则二叉树的边数T=n1+n2 * 2。
3、而每一个节点的头部都有一个边（根节点除外），所以二叉树的边数T=n-1。
4、综上可知：n1+n2 * 2=n-1=n0+n1+n2-1，则n0=n2+1。

image.png

3.3、真二叉树

真二叉树：所有节点的度要么是0，要么是2。
如下图：

真二叉树.png
下图就不是真二叉树

非真二叉树.png

3.4、满二叉树

满二叉树：最后一层的节点的度0，其他节点的度为2。
如下图：

满二叉树.png

1、假设满二叉树的高度为h(h>=1)，那么
- 1、第i层的节点数量为2^（i-1）。
- 2、叶子节点的数量为：2^(h-1)
- 3、总节点的个数=2^0+ 2^1 + 2^2+...+2(h-1)=2^h-1。
2、在同样高度的二叉树中，满二叉树的叶子节点最多，总节点数最多。
3、满二叉树一定是真二叉树，真二叉树不一定是满二叉树。

3.5、完全二叉树

完全二叉树：对节点从上至下，从左到右开始编号，其所有编号能与相同高度的满二叉树中的编号对应。

image.png

完全二叉树的特点

1、叶子节点只会出现在最后两层，最后一层的叶子节点靠左对齐。
2、完全二叉树从根节点到倒数第二层是一个满二叉树。
3、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

完全二叉树的性质

1、度为1的节点只有左子树。
2、度为1的节点要么有1个，要么有0个。
3、同样节点的数量，完全二叉树高度最小。
4、假设完全二叉树的高度为h(h>=1)，则
- 1、则至少有2^{（h-1）个节点（2}0 + 2^1 + ... + 2^(h-2)+1）。
- 2、最多有2^h - 1 个节点（2^0 + 2^1 + ... + 2^(h-1)）。此时为满二叉树。
- 3、总节点数为n
则 2^（h-1）<= n < 2^h
则h - 1 <= log₂n <= h
则h = floor( log₂n) + 1
floor是向下取整，只取前面的整数。比如floor(4.9)=4。
ceil是向上取整，如果小数部分部位0，则取前面的整数然后加1，否则只取前面的整数，例如ceil(4.0)=4，ceil(4.2)=5。
round()，是四舍五入的，其原理是参数上加0.5然后进行下取整。例如：round(4.0)=4、round(4.3)=4、round(4.5)=5、round(4.6)=5。
4、一棵树有n（n>0）个节点，从上到下、从左到右进行对节点从1进行编号，对任意第i个节点：
- 如果i=1，它是根节点
- 如果i>1，它的父节点编号为floor(i/2)
- 如果2i<=n，它的左子节点编号为2i
- 如果2i>n，它无左子节点
- 如果2i+1<=n，它的右子节点为2i+1
- 如果2i+1>n，它没有右子节点
  
  image.png
5、一棵树有n（n>0）个节点，从上到下，从左到右进行节点从0进行编号，对任意第i个节点：
- 如果i=0，它是根节点
- 如果i>0，它的父节点编号为floor((n-1)/2)
- 如果2i+1<=n-1，它的左字节点编号为2i+1
- 如果2i+1>n-1,它无左子节点
- 如果2i+2<=n-1,它的右子节点编号2i+2
- 如果2i+2>n-1,它无右子节点。
  
  image.png

4、面试题

4.1、如果一棵完全二叉树有768个节点，求叶子节点的个数。

1、假设叶子节点的个数为n0，度为1的节点个数为n1，度为2的节点个数为n2。
2、总节点个数n=n0+n1+n2，而且n0=n2+1。
3、则n=n0+n1+n0-1，即n=2 * n0 - 1+n1。
4、由于完全二叉树的度为1的节点，要么为0个要么为1个。
- 1、当n1=1时，n=2*n0。则节点总数为偶数。叶子节点n0=n/2。
- 2、当n1=0时，n=2*n0-1。则节点总数为奇数。叶子节点n0=(n+1)/2
- 3、在编码时需要对节点总数进行判断，然后根据奇偶去使用不同的公式，能不能使用通用的公式呢？
  比如将n0=(n+1)/2作为通用公式，将其拆解为n0=n/2+1/2，如果对其向下取整n0=floor(n/2+1/2)当n为偶数则符合n0=n/2，当n为奇数也是符合n0=(n+1)/2，上面是数学角度的分析，在编码时则可以直接使用