文章目录
一、二叉树的性质
1.二叉树的第i层上最多有i个节点
节点最多的情况就是：完美二叉树。
2.深度为k的二叉树最少有k个节点，最多有 2 k − 1 2^k-1 2k−1个节点
最少：斜二叉树，已经退化为线性结构。
最多：完美二叉树，每一层都塞满了
2
0
+
2
1
+
⋯
+
2
k
−
1
=
2
k
−
1
2^0+2^1+\dots +2^{k-1}=2^k-1
20+21+⋯+2k−1=2k−1个。
3.对于任意一颗非空的二叉树，若其度为0的节点数为 n 0 n_0 n0，度为2的节点数为 n 2 n_2 n2，那么 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1
我们给出证明：
计度为1的节点数为
n
1
n_1
n1，总节点数为
n
n
n,，易得出
n
=
n
0
+
n
1
+
n
2
n=n_0+n_1+n_2
n=n0+n1+n2。再看二叉树中边数，一方面除了根节点每一个节点都有唯一前驱，另一方面边数由
n
2
,
n
1
n_2,n_1
n2,n1贡献，因此有
n
−
1
=
2
n
2
+
n
1
=
n
0
+
n
1
+
n
2
−
1
n-1=2n_2+n_1=n_0+n_1+n_2-1
n−1=2n2+n1=n0+n1+n2−1，解出
n
0
=
n
2
+
1
n_0=n_2+1
n0=n2+1。
我们也给出这种关系的解释：
结点为0的数即为叶子节点的数目。而要想产生叶子几点，每一个度为2的节点才能产生一个叶子节点。
4. n n n个节点组成的完全二叉树的深度为 d e p t h = ⌊ l o g 2 n ⌋ + 1 depth=\lfloor log_2n\rfloor +1 depth=⌊log2n⌋+1
从性质2显然可得
二、二叉树的存储
二叉树的存储方式主要有两种，分别是顺序存储和链式存储。顺序存储适用于二叉树的形态和大小不发生剧烈变化的情况。顺序存储可以使用一维数组进行实现，通过数组元素的下标作为索引，随机存取二叉树的节点。链式存储则是构造链表，每一个节点中都包含着其他节点的地址信息，只能通过迭代以此访问元素。
1.顺序存储
完全二叉树的顺序存储
首先按照完全二叉树的层序顺序依次将数据存入一维数组。那么对于一个节点
(
i
n
d
e
x
=
k
)
(index=k)
(index=k)来说，他的父亲节点为
⌊
f
r
a
c
k
2
⌋
\lfloor frac{k}{2} \rfloor
⌊frack2⌋，他的左儿子为
2
k
2k
2k，右儿子为
2
k
+
1
2k+1
2k+1，如果发生越界则没有左儿子（右儿子）。
一般二叉树的顺序存储
将缺失的节点补上虚节点，将一般二叉树补齐为完全二叉树，然后按照上述的方法进行存储。
但是这种存储方法十分低效。尤其是当二叉树退化为线性结构时，会浪费很多的内存空间。
2.链式存储
二叉链表
每个节点有一个数据域和两个指针域。指针域分别指向它的左儿子和右儿子。如果没有该节点没有左儿子（右儿子），就将相应的指针域赋值为NULL。
typedef struct node {
int data;
struct node* lchild;
struct node* rchild;
}Node;
三叉链表
在二叉链表的基础上又增加了一个父亲节点。这样的好处是，相当于在程序内增加了一个记忆回退的stack，方便从该节点退回到父亲。同样的，记得所有没有被赋值的指针域都要被置空。
typedef struct node {
int data;
struct node* lchild;
struct node* rchild;
struct node* parent;
}Node;