二叉树的概念：

  二叉树是一种树的度不大于2的树，也就是它的节点的度都是小于等于2的。二叉树的子树有左右之分，左右的次序不能颠倒，因此二叉树是一个有序树。任意的二叉树都由空树、只有根节点、只有左子树、只有右子树、左右子树均存在这几种情况复合而成。

特殊的二叉树：

  完全二叉树：完全二叉树是一种效率很高的数据结构，如果一个二叉树的深度为k，节点总数不小于2^k-1，同时不大于2^k-1，并且在最后一层时，每个节点从左到右保持连续，则它就是完全二叉树。
  满二叉树：每一层的节点数都达到了最大值即为满二叉树。如果说一个二叉树的深度为k，且节点总数是2^k-1，那它就是一个满二叉树，我们可以通过这个公式来判断一个二叉树是不是满二叉树。本质上来说，满二叉树是一种特殊的完全二叉树。
  需要注意的是，虽然满二叉树是一种特殊的完全二叉树，但是完全二叉树是由满二叉树引出来的。

二叉树的性质：

1. 一颗非空二叉树的第 i 层上最多有2^i-1个节点；
2. 深度为h的二叉树的最大节点数是2^h-1；
3. 对任何一棵二叉树，如果度为0其叶节点的个数为n₀，度为2的分子节点个数为n₂，则有n₀=n₂+1；
4. 假设具有n个节点的满二叉树的深度h，则有h=log₂(n+1)；
5. 对于具有n个节点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的节点有：
    ①若i>0，i位置节点的父节点序号：(i-1)/2（取商舍余）；
    ②若2i+1i+1，若2i+1>=n则无左孩子；
    ③若2i+2i+2，若2i+2>=n则无右孩子。
   

二叉树的存储结构：

  二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

1. 顺序存储
     顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间浪费。而实际开发中只有堆待会使用数组来存储，二叉树顺序存储物理上是一个数组，在逻辑上是一颗二叉树。
2. 链式存储
     二叉树的链式存储是指用链表来表示一棵二叉树，通常的方法是链表中每个节点由三个域组成，数据域和左右指针域，左右指针分别用来指向左右孩子的存储地址。链式结构分为二叉链和三叉链，一般情况下我们二叉树所用到的是二叉链，但是如红黑树这些使用的则是三叉链。

typedef int HPDataType;
//顺序存储
typedef struct Heap
{HPDataType* a;//指向数组int size;//有几个值int capacity;//容量
}Heap;typedef int BTDataType;
//二叉链
struct BinaryTreeNode
{struct BinTreeNode* pleft;//指向当前节点左孩子struct BinTreeNode* pright;//指向当前节点右孩子BTDataType data;//当前节点值
}//三叉链
struct BinaryTreeNode
{struct BinTreeNode* pparent;//指向当前节点的双亲struct BinTreeNode* pleft;//指向当前节点左孩子struct BinTreeNode* pright;//指向当前节点右孩子BTDataType data;//当前节点值