文章目录

• • 一、二叉树的性质
  • • • 1.二叉树的第i层上最多有i个节点
      • 2.深度为k的二叉树最少有k个节点，最多有 2 k − 1 2^k-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
      • 4. n n n个节点组成的完全二叉树的深度为 d e p t h = ⌊ l o g 2 n ⌋ + 1 depth=\lfloor log_2n\rfloor +1 depth=⌊log2​n⌋+1
  • 二、二叉树的存储
  • • 1.顺序存储
    • • 完全二叉树的顺序存储
      • 一般二叉树的顺序存储
    • 2.链式存储
    • • 二叉链表
      • 三叉链表

一、二叉树的性质

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=⌊log2​n⌋+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;