二叉树的基本性质和特点（二叉树的定义与特点）
二叉树的基本性质和特点（二叉树的定义与特点）斜树的结点个数与其深度相同。在斜树中，每一层只有一个结点；如上图所示，二叉树主要有以下几种基本形态：除了上面所讲的基本形态，二叉树还有几种特殊形态，如下所示斜树的结构如下图所示：
前言本章我们主要讲解二叉树的基本定义，以及二叉树的几种基本形态，特殊形态（斜树，满二叉树，完全二叉树）；还有一些二叉树的特点性质。
二叉树的定义二叉树是N(N≥0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的分别称为根结点的左子树和右子树的二叉树组成。
二叉树与一般树型结构的主要区别：
- 二叉树中每个非空结点最多只有两个子女，而一般的树型结构中每个非空结点可以有0到多个子女；
- 二叉树中结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出是左子树还是右子树。
二叉树的基本形态：
如上图所示，二叉树主要有以下几种基本形态：
- (a)空二叉树
- (b)仅有根结点的二叉树
- (c)右子树为空的二叉树
- (d)左子树为空的二叉树
- (e)左右子树不为空的二叉树
除了上面所讲的基本形态，二叉树还有几种特殊形态，如下所示
- 斜树：所有结点都只有左子树的二叉树称为左斜树；所有结点都只有右子树的二叉树称为右斜树；左斜树和右斜树统称为斜树。
- 满二叉树：如果一棵二叉树中所有终端结点均位于同一层次，而其它非终端结点的度数均为2
- 完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树
斜树的结构如下图所示：
在斜树中，每一层只有一个结点；
斜树的结点个数与其深度相同。
满二叉树的结构如下图所示：
叶子只能出现在最下一层；
只有度为0和度为2的结点。
完全二叉树的结构如下所示：
- 在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。
- 叶子结点只能出现在最下两层且最下层的叶子结点都集中在二叉树的左面。
- 完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。
- 深度为k的完全二叉树在k-1层上一定是满二叉树。
- 在同样结点个数的二叉树中，完全二叉树的深度最小。
性质1：一棵非空二叉树的第i层上至多有2^(i-1)个结点（i≥1）。
性质2：深度为h的二叉树中至多含有2^h-1个节点 。
性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2 1
性质4：具有n个节点的完全二叉树深为log2^x 1（其中x表示不大于n的最大整数）。
性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点有如下特性
- 当i=1时，该节点为根，它无双亲节点 。
- 当i>1时，该节点的双亲节点的编号为i/2 。
- 若2i≤n，则有编号为2i的左节点，否则没有左节点 。
- 若2i 1≤n，则有编号为2i 1的右节点，否则没有右节点 。
性质1证明：
当i=1时，只有根结点，此时2^(1-1)=2^0=1，显然结论成立；假定i=k（1≤k＜i）时结论成立，即第k层上至多有2^(k-1)个结点。则 i=k 1时，因为第k 1层上的结点是第k层上结点的孩子，而二叉树中每个结点最多有2个孩子，故在第k 1层上最大结点个数为第k层上的最大结点个数的2倍，即2×2k-1＝2k。结论成立。
性质2证明：
根据性质1，深度为h的二叉树最多具有的结点的个数为：
2^0 2^1 2^2 … 2^(h-1)=2^h - 1。
性质3证明：
设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有：
n＝n0＋n1＋n2 （式1）
在二叉树中，除了根结点外，其余结点都有唯一的一个双亲进入，所以有（n=分支数 1）。一个度为1的结点射出1个孩子分支，一个度为2的结点射出2个孩子支：
因此 ，分支数=n1＋2n2 所以， n＝n1＋2n2＋1 （式2）
因此可以得到：n0＝n2＋1 。
因为在满二叉树中没有度为1的结点，只有度为0的叶子结点
和度为2的分支结点，所以，
n＝ n0 n2
n0＝n2 1
即叶子结点n0＝（n 1）/2
性质4证明：
假设具有n个结点的完全二叉树的深度为h，根据完全二
叉树的定义和性质2，有下式成立2^(h-1) ≤ n ＜ 2^h
对不等式取对数，有：h-1≤log2^n＜h
即：log2^n＜h≤log2^n 1
由于h是整数，故必有h＝ log2^n 1。
