数据结构（12）二叉树
目录
一、树
1、树的概念与结构
2、树的相关术语
3、树的表示
二、二叉树
1、概念与结构
2、满二叉树
3、完全二叉树
4、二叉树的存储结构
4.1 顺序结构
4.2 链式结构
一、树
1、树的概念与结构
树是一种非线性的数据结构，由n个有限结点组成一个具有层次关系的集合。有一个特殊的结点称为根结点，根结点没有前驱结点。除根结点外，其余结点被分为m个互不相交的集合，其中每一个集合又是一棵结构与树类似的子树。因此，树是递归定义的。
注意：树形结构中，子树之间不能有交集，否则就不是树形结构！下图都是非树形结构：
树有以下三个性质 ：
（1）子树是不相交的（如果存在相交就是图）
（2）除了根结点之外，每个结点有且仅有一个父结点
（3）一棵N个结点的树有N-1条边
2、树的相关术语
（1）结点的度：一个结点有几个孩子，它的度就是多少
（2）树的度：一棵树中最大结点的度称为树的度
（3）结点的层次：从根开始定义起，根是第一层，根的子结点是第二层，以此类推
（4）树的高度/深度：树中结点的最大层次
3、树的表示
树有很多种表示方式，这里就简单了解最常用的孩子兄弟表示法。
struct TreeNode
{struct TreeNode* child; //左边开始的第一个孩子结点struct TreeNode* brother;//指向其右边的下一个兄弟结点int data; //结点中的数据域
}; 
二、二叉树
1、概念与结构
一棵二叉树是结点的一个有限集合，该集合由一个根结点加上两棵称为左子树和右子树的二叉树组成或者为空。
从上图中可以看出二叉树具备以下特点:
（1）二叉树不存在度大于2的结点
（2）二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
2、满二叉树
如果二叉树的每一层结点数都达到最大值，那么这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数为2^K - 1，它就是满二叉树。
3、完全二叉树
完全二叉树是效率很高的数据结构，由满二叉树引出来。因此，满二叉树是一种特殊的二叉树。完全二叉树有以下三点性质：
（1）除了最后一层，每层结点个数达到最大
（2）最后一层的结点个数不一定达到最大
（3）结点从左往右依次排列
二叉树的性质
根据满二叉树的特点可知：
（1）若规定根结点层数为1，则一棵非空二叉树的第i层上最多有2^(i - 1)个结点
（2）若规定根结点层数为1，则深度为h的二叉树的最大结点数是2^h - 1
（3）若规定根结点层数为1，具有n个结点的满二叉树的深度h = log2（n + 1）
（log以2为底，n + 1为对数）
4、二叉树的存储结构
二叉树一般可以用两种结构存储，一种是顺序结构，一种是链式结构。
4.1 顺序结构
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。
现实中我们通常把堆（一种二叉树）使用顺序结构的数组来存储。需要注意的是，这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一种是数据结构，一个是操作系统中管理内存的一块区域分段。
4.2 链式结构
二叉树的链式存储结构是指用链表来表示一棵二叉树。通常的方法是链表中每个结点由三个域组成：数据域和左右指针域。左右指针分别用来给出该结点左右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链。当前学习中一般都使用二叉链，后续高阶数据结构如红黑树等就会使用到三叉链。
