数据结构 | 二叉树的定义与存储结构
定义:
1. 节点的类型:
- 在非空二叉树中，第i层的结点总数最大为$2^{i}-1,i\ge1$（满树情况）
- 深度为h的二叉树最多有 $2^h-1, h\ge1$ 个结点，最少有$h$个结点
- 对于任意一棵二叉树，设其总结点数为$N$，如果其叶结点(度为0的结点）数为$N_0$，而度数为2的结点总数为$N_2$，则$N_0=N_2+1$，度为1的结点数$N_1=N-N_0-N_2$
- 具有n个结点的完全二叉树的深度为$\log(N+1)$，底数为2
- 有$N$个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
- 若$I$为结点编号则 如果$I\gt1$，则其父结点的编号为I/2
- 如果$2×I \le N$，则其左儿子（即左子树的根结点）的编号为$2×I$
- 若$2×I \gt N$，则无左儿子
- 如果$2×I+1 \le N$，则其右儿子的结点编号为 $2×I+1$
- 若$2×I+1 \gt N$，则无右儿子
- 给定N个结点，能构成h(N)种不同的二叉树。 h(N)为卡特兰数的第N项。$h(n)=C(2*n, n)/(n+1)$
- 设有i个分支点，I为所有分支点的道路长度总和，J为叶的道路长度总和$J=I+2i$
2. 分类:
完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1-h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布
满二叉树:除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树
平衡二叉树(AVL)：二叉排序树，空，或左子树和右子树都是平衡二叉树，且深度差<=1
存储结构：
二叉树是非线性结构，其存储结构可以分为两种，即顺序存储结构和链式存储结构。
1. 顺序存储结构
二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。 即用一维数组存储二叉树中的结点。因此，必须把二叉树的所有结点安排成一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系。用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号。
依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。
一棵完全二叉树（满二叉树）如下图所示：
将这棵二叉树存入到数组中，相应的下标对应其同样的位置，如下图所示：
但是对于一般的非完全二叉树来说，如果仍然按照从上到下、从左到右的次序存储在一维数组中，则数组下标之间不能准确反映树中结点间的逻辑关系，可以在非完全二叉树中添加一些并不存在的空结点使之变成完全二叉树，（把不存在的结点设置为“^”）不过这样做有可能会造成空间的浪费，如下图所示，然后再用一维数组顺序存储二叉树。
其存储结构为:
缺点是：有可能对存储空间造成极大的浪费，在最坏的情况下，一棵深度为k的右斜树，它只有k个结点，却需要$2^k-1$个结点存储空间。这显然是对存储空间的严重浪费，所以顺序存储结构一般只用于完全二叉树或满二叉树。
2.链式存储结构
二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
二叉树的每个结点最多有两个孩子，因此，每个结点除了存储自身的数据外，还应设置两个指针分别指向左、右孩子结点。
结点结构如下图所示：
