二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树
特殊二叉树1.满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。. 也就是说，如果一个二叉树的层数为K，且结点总数是 (2^k) -1 ，则它就是满二叉树。如下图：
2.完全二叉树：满足以下要求：. 所有叶子节点都出现在 k 或者 k-1 层，而且从 1 到 k-1 层必须达到最大节点数；. 第 k 层可以不是满的，但是第 k 层的所有节点必须集中在最左边。注意：满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。
二叉树的性质 性质1：二叉树第i层上的结点数目最多为 2 {i-1} (i≥1)。性质2：深度为k的二叉树至多有 2{k}-1个结点(k≥1)。
性质3：包含n个结点的二叉树的高度至少为 log2 (n+1)。 证明：根据"性质2"可知，高度为h的二叉树最多有2{h}–1个结点。反之，对于包含n个节点的二叉树的高度至少为log2(n+1)。
性质4：在任意一棵二叉树中，若叶子结点的个数为 n0，度为2的结点数为 n2，则 n0=n2+1。
性质5：对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对 于序号为i的结点有：
1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1
二叉树的存储结构 二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。 1. 顺序存储 顺序结构存储就是使用 数组来存储 ，一般使用数组 只适合表示完全二叉树 ，因为不是完全二叉树会有空 间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺 序存储在物理上是一个数组，在逻辑上是一颗二叉树。
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}
2.
链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是 链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所 在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程 学到高阶数据结构如红黑树等会用到三叉链。
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pParent; // 指向当前节点的双亲
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}；
题目 1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ） A 不存在这样的二叉树 B 200 C 198 D 199 2. 下列数据结构中，不适合采用顺序存储结构的是（ ） A 非完全二叉树 B 堆 C 队列 D 栈 3. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ） A n B n+1 C n-1 D n/2 4. 一棵完全二叉树的节点数位为 531 个，那么这棵树的高度为（ ） A 11 B 10 C 8 D 12 5. 一个具有 767 个节点的完全二叉树，其叶子节点个数为（） A 383 B 384 C 385 D 386 答案： 1.B 2.A 3.A 4.B 5.B
