大家好，今天继续学习树的数据结构。在上一章，我们讲树的孩子兄弟表示法时，提到了二叉树。今天，我们就来学习二叉树的相关性质。
一、二叉树定义：
二叉树(Binary Tree):n(n≥0)个结点的有限集合，该集合或者为空集(为空时，称为空树)，或者由一个根结点、两棵互不相交、称为根结点的左子树、右子树的二叉树组成。(Note:大家注意了，我们在给出二叉树定义时，我们利用了递归概念。就是先给出二叉树概念，再用二叉树概念去解释二叉树。递归是一种很重要的方法，在数据结构中是很重要的，我们会在后面章节中提到。)
我们看图来理解一下二叉树:
二、二叉树的特点:
1、二叉树中的结点度数，一定小于等于2。(根据二叉树定义，由一个根结点、两棵互不相交的称为根结点左子树、右子树的二叉树组成。note:度数不是只能是2，是至多是2)
2、左子树与右子树是有顺序的，次序不能颠倒。
3、即使树中只有一个子树，也要区分左子树、右子树。
三、二叉树具有的5种基本形态:
1.空二叉树
2.只有根结点
3.只有左子树的二叉树
4.只有右子树的二叉树
5.既有左子树又有右子树
四、特殊二叉树:
1.斜二叉树:
既然是斜二叉树，就一定要有斜度。
上面这两个图，就是斜二叉树。(note:看着是不是挺像线性表。其实，线性表就是二叉树的特殊表现形式)
2.满二叉树:
顾名思义，既然是满二叉树，就是每个结点都具备两个子树。如图:
如果二叉树中，每个结点都具备左子树、右子树，并且所有叶子结点都在同一层中，这样的二叉树称为满二叉树。
满二叉树的特点:
a.叶子结点只能出现在最后一层，如果不是，就不能达到满二叉树。
b.非叶子结点的度数只能为2，如果不是，就会出现“缺胳膊少腿”的现象。
c.在相同深度的二叉树中，满二叉树的结点最多，叶子结点最多。
3.完全二叉树:
对一棵具有n个结点的二叉树，按着层序编号，如编号为i(1≤i≤n)的结点位置，与同等深度的满二叉树中编号为i结点位置相同，则称这样的二叉树为完全二叉树。 完全二叉树不好理解，我们看一下图:
上面左图，是一棵完全二叉树，右图是一棵满二叉树。我们在心里给右图满二叉树按层序编号。通过左图与右图的对比，我们发现，左图中的任一结点，在右图中都有与之相对应的结点。
下面再给出几张不是完全二叉树的图:
完全二叉树特点:
a.如果结点度数为1，那么只能是左子树。(不存在只有右子树结点)
b.叶子结点只能出现在最下两层。
c.最下层的叶子结点，一定集中在左部连续位置。
d.倒数两层，如果有叶子结点，一定集中在右部连续位置。
e.同样结点数的树，完全二叉树的深度最小。
五、二叉树性质:
接下来，我们来学习一下二叉树的性质。在实际应用中，都是通过二叉树的性质来操作的。二叉树的性质，是非常重要的概念。
a.在二叉树中，第i层的结点总数最多2^(i-1)个
第一层: 1=2^(1-1)=2^0=1
第二层:2=2^(2-1)=2^1=2
第三层:4=2^(3-1)=2^2=4
……
……
b.深度为k的二叉树，结点总数等于2^k-1
深度为1:1=2^1-1=1
深度为2:3=2^2-1=3
深度为3:7=2^3-1=7
……
……
c.如果n0是叶子结点，n2是度数为2的结点。则n0=n2+1.
二叉树中，除了叶子结点就是度数为1、度数为2的结点。我们假设度数为1的结点为n1、度数为2的结点为n2、叶子结点为n0.则树中结点总数为n=n0+n1+n2.我们观察上图，研究一下节点之间的连接线。因为根结点只有出去的线，没有进入的线。所以总线+1就是结点总数，n1+2n2+1=n0+n1+n2 n0=n2+1
d.具有n个结点数的完全二叉树的深度为[log2N]+1([x]表示不大于x的最大整数)。
e.如果对一棵有n个结点的完全二叉树(其深度为[log2N])的结点按层序编号(从第一层到[log2N]+1层，每层从左到右)，对任一结点i(1≤i≤n)有:
1.如果i=1，则结点i是二叉树的根，无双亲；如果i>1,则双亲为[i/2].
2.如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i.
3.如果2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1
我们将在下一章讲解二叉树的存储结构