一 、二叉树的基本概念
1 . 了解树形结构
- 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
- 它具有以下的特点：
有一个特殊的结点，称为根结点，根结点没有前驱结点，除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合 Ti (1 <= i<= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继树是递归定义的
判断是否是树的必要条件：
- 树的子树是不相交的
- 除了根节点之外，每个节点有且只有一个父亲节点
- 一棵包含n 个节点的树有 n -1条边
比如下图的树型结构中 包含了11个节点，有10条边，每个节点都只有一个父亲节点
2.相关概念
以下图当中的树型结构为例：
主要概念
结点的度：一个结点含有子树的个数称为该结点的度；
- A的度为6，J的度为2，F的度为3
树的度：一棵树中，所有结点度的最大值称为树的度；
- 树的度为6，即A的度为所有节点当中度的最大值
叶子结点或终端结点：度为0的结点称为叶结点；
- B、C、H、I，P，Q，K，L，M，N等节点为叶结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；
- A是B的父结点 ，同时也是 C,D,E,F,G等节点的父亲节点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点
- B是A的孩子结点，与父亲节点相反
- 根结点：一棵树中，没有双亲结点的结点；如上图：A
- 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
- 树的高度：树中结点的最大层次； 如上图：树的高度为4
次要概念
- 非终端结点或分支结点：度不为0的结点； 如上图：D、E、F、G...等节点为分支结点
- 兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点
- 堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点
- 结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先
- 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
- 森林：由m（m>=0）棵互不相交的树组成的集合称为森林
- 二叉树基本概念
一棵二叉树是结点的一个有限集合，该集合：
- 或者为空
- 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成
两种特殊的二叉树
- 完全二叉树
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一 一对应时称之为完全二叉树。
完全二叉树的节点个数为
偶数个时：表示此完全二叉树的组成为：一个度为1的叶子节点+度为0的节点+度为2的节点
奇数个时：度为0的节点个数 + 度为 2 的节点个数
- 满二叉树
满二叉树是一种特殊的完全二叉树，它的每层节点都达到了最大值，即每个父亲节点都包含了两个孩子节点，也就是说如果一棵二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
4.二叉树的性质
若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2的i-1次方 (i>0)个结点
- 节点最多时即满二叉树的情况，则第层的节点个数为 2 的i-1次方
若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 (k>=0)
- 最大节点数需要保证每层的节点数最多，即 2的0次方累加到2的i-1次方，等比数列求和可知最大节点数为 2的k次方-1
对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2则有n0＝n2＋1
- 假设一个二叉树当中 度为 0 的节点有 n0 个，度为1 的节点有 n1个，则总结点数N= n0 + n1 + n2;
- N个节点的二叉树包含N - 1 条边 即 N-1 = n1 + 2n2;
- 两式合并得到 n0 = n2 + n1;
具有n个结点的完全二叉树的深度k为 log2(n +1) 向上取整
- 性质二反推可知
- 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
若2i+1<n，左孩子序号：2i+1，否则无左孩子
若2i+2<n，右孩子序号：2i+2，否则无右孩子
5 . 二叉树性质的应用
- 二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199
根据性质二， 二叉树共有399 个节点，度为2 的节点为199 个，则叶子节点为 度为2 的节点 +1 = 200个
- 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2
完全二叉树当中，具有奇数个节点说明二叉树包含了一个度为 1 的节点，设度为0 的节点有 x 个，故 可知 2n - 1 = x + x - 1 故 2n = 2x , n = x ,说明度为0 的节点为 n 个，即叶子节点的个数为n 个，即A
- 一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386
完全二叉树的叶子节点的个数为奇数个，则不存在度为1 的节点， 则x + x -1 = 767 , 故结果为384，B
- 一棵完全二叉树的节点数为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12
二叉树的节点为 531个， 则由 2 的9次方 = 512 ， 2 的10 次方为 1024，对532 对2取对数并向上取整，即结果为 10 ，这棵树的高度为10 ，B
