叶子节点的特征是无左孩子也无右孩子，还要注意与树只有一个节点的情况区分。

一、程序计算

int leaf(bitree t)
{
  if(!t)       
   return 0;      //空树,无叶子 
  else if(!t->lch && !t->rch)
           return 1;
        else 
           return (leaf(t->lch) + leaf(t->rch));
}

二、手动计算公式

利用“树中所有结点的度数之和再加1等于结点数”



则叶子节点数，即 为：

决策树算法
决策树
树模型
决策树：从根节点开始一步步走到叶子节点（这一过程叫做决策的过程，叶子节点就是决策）。
所有的数据最终都会落到叶子节点，既可以做分类，也可以做回归。
例如下面的图示就是一个决策的过程。

根节点：第一个选择的节点。
非叶子节点与分支：中间的决策过程
叶子节点：最终的决策结果。
节点：没增加一个节点相当于在数据中切一刀，将数据分类。
决策树的训练于测试
训练阶段：从给定的训练集构造出一棵树（从根节点开始选择特征，一步一步往下分，但是如何选择出第一个第二个…的特征呢，也就是划分特征的选择，这个分类特征的选择后面会讲到，还会涉及到树的剪枝处理，包括：预剪枝和后剪枝，以及连续数据的处理，缺失值的处理。）
测试阶段：将数据放入模型根据构造的树模型从上到下流动。
如何选择切分特征呢？也就是如何选择节点？
​        跟节点的特征选择应该用那个特征呢？接下来的第二特征，第三特征呢？这些特征如何选择呢？在一批数据中的特征显然是多样的，但是我们不能随意地选取一个特征放到任意的一个节点上，这显然是不对的，根据排列组合原理，这样随意选择一个特征随意放到一个节点上，随后得到的模型是很多的，我们当然是要得到一个最优模型。
​	我们的目标应该是没一个节点能够最大限度的将数据分类，其中越往上的节点的分类效果越好。那么这个分类效果就是一个标准，通过建立这样一个标准，来计算不同特征进行分支选择后的分类情况，找出来最好的那个当成节点，然后在选择下面的节点的时候，继续在剩余的特征中计算每个特征进行分支选择后的分类情况，找出来分类最后的那个当成第二节点，一次类推。
那么这个衡量标准是什么呢？就是熵值
衡量标准：熵
熵：熵是表示随机变量不确定性的度量。简单说就是表示物体内部的混乱程度，例如：在一个手机批发大卖场例如华强北，那么这里面的手机种类肯定多呀，那么手机的种类就混乱呀，但是在华为专卖店里手机的种类就非常稳定了，只有华为，没有三星也没有苹果。
那么这个熵值既然是表示随机变量的不确定性的度量，那么它的计算公式如何呢？
$\begin{aligned}H(X) = -\sum P_ilogP_i,i = 1,2,3...\end{aligned}$，负号的原因是为了使得计算结果为正，因为$P_i$的取值范围为$[0,1]$,那么$logP_i$的取值范围就为$[-\infty,0]$，加上一个负号就会使得计算结果为正。



例如：集合A和集合B分别是
$A = [1,1,1,1,1,1,1,2,2],B = [1,2,3,4,5,6,7,8,9]$
显然，A,B两个集合都只有9个随机变量，但是A集合总共只有两种类别，而B集合有9种类别，所以A的熵值就会很小，B的熵值就会较大，A要相对稳定一些。
现在通过计算来看一下
选择$log$的底数为2的原因是在$sklearn$这个库中是用$log_2$来计算的，实际上，取对数计算的时候只是影响的值的大小，但是并不影响相对大小，也可以选用其他的底数，但是本质上是一样的，而且不同底数之间也可以通过换底公式计算。
$\begin{aligned}H_A(X)= -(\frac{7}{9}\times log_2\frac{7}{9}+\frac{2}{9}\times log_2\frac{2}{9})\approx 0.7642\end{aligned}$
$\begin{aligned}H_B(X) = -(9\times\frac{1}{9}\times log_2\frac{1}{9})\approx 3.1699\end{aligned}$
可以看到，A的熵值低于B的熵值，这也证明了集合A比集合B稳定的多。
熵：不确定性越大，也就是混乱程度越大，得到的熵值也就越大，当$P=0$或者$P=1$时，$H(P)=0$，此时随机变量完全没有不确定性，因为该事件为不可能事件或者必然事件。当$P=0.5$时候，$H(P)=1$，此时随机变量的不确定性最大。


那么如何决定第一个点的选择呢？
这就引出了信息增益这一概念
信息增益：表示特征X使得类Y的不确定性减少的程度，也就是分类后的专一性，希望分类后的结果是越多的同类在一起，那么这时的混乱程度就降低了也就是熵值降低了，这个降低的程度越大，那么信息增益的程度就越大。
举个栗子：下面是十四天的打球情况

数据：14天的打球情况
特征：4种环境变化Outlook，Temperature，Humidity，Windy，Play
目标：构造决策树
划分的方式有四种如下

基于天气的划分


#查看每种天气对应的天数
weathers = ['sunny','overcast','rainy']
days_by_weather = {}
for this_weather in weathers:
    num = np.count_nonzero(data['Outlook'] == this_weather)
    days_by_weather[this_weather] = num
days_by_weather

{'sunny': 5, 'overcast': 4, 'rainy': 5}


基于温度的划分


Temperatures = ['hot','cool','mild']
days_by_temperature = {}
for this_Temperature in Temperatures:
    num = np.count_nonzero(data['Temperature'] == this_Temperature)
    days_by_temperature[this_Temperature] = num
days_by_temperature

{'hot': 4, 'cool': 4, 'mild': 6}


基于湿度的划分


humidities = {'high','normal'}
days_by_humidity = {}
for this_humidity in humidities:
    num = np.count_nonzero(data['Humidity'] == this_humidity)
    days_by_humidity[this_humidity] = num
days_by_humidity

{'high': 7, 'normal': 7}


基于有风的划分


windies = ['NO','YES']
days_by_windies = {}
for this_windy in windies:
    num = np.count_nonzero(data['Windy'] == this_windy)
    days_by_windies[this_windy] = num
days_by_windies

{'NO': 8, 'YES': 6}

在历史数据中查看打球与不打球的天数
plays = ['NO','YES']
days_by_play = {}
for this_play in plays:
    num = np.count_nonzero(data['Play'] == this_play)
    days_by_play[this_play] = num
days_by_play

{'NO': 5, 'YES': 9}

那么此时的熵值为
$\begin{aligned}-\frac{9}{14}log_2\frac{9}{14}-\frac{5}{14}log_2\frac{5}{14} = 0.940\end{aligned}$
然后将上述4个特征注意分析，先从Outlook开始
Outlook = sunny时，计算熵值为$\begin{aligned}-\frac{3}{5}log_2\frac{3}{5}-\frac{2}{5}log_2\frac{2}{5}\end{aligned} = 0.971$
Outlook=overcast时，熵值为0
Outlook = rainy时，熵值为0.971
其余特征分类后的每个子类的熵值计算也是类似
根据统计Outlook取值分别为sunny,overcast,rainy的概率分别为$\begin{aligned}\frac{5}{14},\frac{4}{14},\frac{5}{14}\end{aligned}$
那么整体分类后的熵值为，就是分类后的加权熵值为
$\begin{aligned}\frac{5}{14}\times0.971+\frac{4}{14}\times0+\frac{5}{14}\end{aligned} = 0.693$
信息增益：系统的熵值从0.940下降到了0.693，增益为0.247
然后此时来计算信息熵值下降，根据天气、温度、适度，是否有风分类获得的信息增益分别为$0.247,0.029,0.152,0.693$
显然这样的计算得到是第一特征，也就是根节点为天气的时候信息增益最大。
计算信息增益时候的算法叫做ID3算法。但是ID3算法存在一定的问题。今天时间不早了先更新到这里。

昨晚中兴笔试题，第一题是给定二叉树，每个节点的数据结构是 value,left,right，比较根节点到各个叶子节点路径和的大小，输出路径和的最小值。(补充：用ArrayList可以存储)
以前没做过关于树的题，所以没想到如何处理各个节点的左右子节点，即不会遍历二叉树，在这里做一个总结
1.递归实现遍历
//递归实现遍历，各种不同的遍历实际上是输出的位置不同，但是都是递归
//先序遍历，传入 t = root1
public void preOrder(Node t){
if(t == null)
return;
System.out.println(t.getValue());
pre(t.getLeft());
pre(t.getRight());
}
//中序遍历，传入 t = root1
public void inOder(Node t){
if(t == null)
return;
inOrder(t.getLeft());
System.out.println(t.getValue());
inOrder(t.getRight());
}
//后序遍历，传入 t = root1
public void postOder(Node t){
if(t == null)
return;
postOrder(t.getLeft());
postOrder(t.getRight());
System.out.println(t.getValue());
2.非递归实现遍历
非递归实现遍历，用到栈来存储路径，输出路径
//先序遍历1，传入t =root1
public void iteratorPre(Node t){
Stack stack = new Stack();
stack.push(t);
//每次取出节点的顺序总是根，左，右
while(!stack.Empty()){
t = stack.pop();
System.out.println(t.getValue());
//先压入右节点，再压入左节点，因为栈是先进后出的
if(t.getRight() != null)
stack.push(t.getRight());
if(t.getLeft() != null)
stack.push(t.getLeft());
}
}
//先序遍历2
protected static void iterativePreorder2(Node p) {
Stack stack = new Stack();
Node node = p;
while (node != null || stack.size() > 0) {
while (node != null) {//压入所有的左节点，压入前访问它
visit(node);
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {//
node = stack.pop();
node = node.getRight();
}
}
}
//中序遍历，传入 t = root1
protected static void iterativeInorder(Node p) {
Stack stack = new Stack();
Node node = p;
while (node != null || stack.size() > 0) {
//压入根节点和左节点
while (node != null) {
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {
node = stack.pop();
visit(node);
node = node.getRight();
}
}
}
//后序遍历，单栈
protected static void iterativePostorder3(Node p) {
Stack stack = new Stack();
Node node = p, prev = p;
while (node != null || stack.size() > 0) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {
Node temp = stack.peek().getRight();
if (temp == null || temp == prev) {
node = stack.pop();
visit(node);
prev = node;
node = null;
} else {
node = temp;
}
}
}
}
3.计算所有路径中的最小值
import java.util.;
public class Main{
/来源：
* 中兴机试题：计算二叉树根节点到叶子节点的最短路径
* 注意：为了记录路径，用栈，找到叶子节点后计算，然后pop()出去，再找下一个
* */
static List list = new ArrayList();
public static void main(String[] args){
Node root1 = new Node();
Node node1 = new Node();
Node node2 = new Node();
Node node3 = new Node();
Node node4 = new Node();
Node node5 = new Node();
Node node6 = new Node();
root1.setLeft(node1);
root1.setRight(node2);
node1.setLeft(node3);
node1.setRight(node4);
node4.setLeft(node5);
node4.setRight(node6);
root1.setValue(8);
node1.setValue(8);
node2.setValue(7);
node3.setValue(9);
node4.setValue(2);
node5.setValue(4);
node6.setValue(7);
//先序遍历
//pre(root1);
//用栈记录路径
Stack n = new Stack();
findMin(root1,n);
//list中是各条路径的和
for(int i = 0;i < list.size();i++){
System.out.println(list.get(i));
}
}
//递归实现，每当发现叶子节点，就计算一次
public static void findMin(Node t,Stack n){
if(t == null)
return;
n.push(t);
//t是叶子节点,此时计算路径和
if(t.getLeft() == null && t.getRight() == null){
int sum =0;
//clone()方法，避免修改原来的栈
Stack s1= (Stack)n.clone();
for(int j =0;j < n.size();j++){
sum += s1.pop().getValue();
}
list.add(sum);
//去除叶子节点
n.pop();
}else{
//递归寻找
findMin(t.getLeft(),n);
findMin(t.getRight(),n);
//经过该节点的路径已找完，删除该节点
n.pop();
}
}
public static void pre(Node t){
if(t == null)
return;
System.out.println(t.getValue());
pre(t.getLeft());
pre(t.getRight());
}
}
//节点结构
class Node{
private int value;
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
private Node left;
private Node right;
}

我们使用MySQL数据库的时候，绝大部分的情况下在使用InnoDB存储引擎，偶尔会使用MyISAM存储引擎，至于其他存储引擎，我相信大家都很少接触到，甚至可能都没有听说过。所以本文只讲解InnoDB和MyISAM两个存储引擎的索引，以及如何计算这两个存储引擎的索引结构B+Tree的高度。

InnoDB

InnoDB主键索引示意图如下，非叶子节点上没有实际的数据，只有叶子节点上才有实际的数据，并且叶子节点之间有指针串联指向下一个叶子节点，这样能够提升范围查询的效率：

InnoDB B+Tree主键索引示意图

InnoDB使用了聚簇索引（Clustered），即所有二级索引聚集在主键索引上，对InnoDB存储引擎表的任何访问，最终一定要搜索主键索引树，二级索引的示意图如下：

 



 

InnoDB B+Tree二级索引示意图

在InnoDB中，二级索引（所有不是主键索引的索引）上没有实际的数据，取而代之的是主键索引的值。这样的话，如果是基于二级索引的查询，会先在二级索引上搜索得到主键索引的值，然后再去主键索引树上搜索，得到最终的行数据。

这就意味着，至少有一次索引查找，可能会有两次索引查找，其中一定有一次主键索引查找。

所以，在InnoDB中，主键要设计的尽量小，主键越小，二级索引也会越小。满足需求的情况下，SMALLINT优先于INT，INT优先于BITINT，INTEGER类型优先于VARCHAR类型。如果主键用更大的数据类型，由于二级索引上有主键索引的值，那么不只是主键索引树变的更大更高，其他的二级索引树也会更大更高，这绝对是一个糟糕的做法。

MyISAM

MyISAM没有使用聚簇索引，所以主键就是一个普通的唯一索引，并且基于索引查询只会搜索当前索引，不会和其他索引有任何关系，任意两个索引之间互不影响。如下图所示，是MyISAM的主键索引示意图，我们可以看到，索引树的叶子节点上只有表中行数据的地址，而不是和InnoDB一样，有实际的数据：



 

MyISAM的主键索引示意图

如下图所示，是MyISAM的二级索引示意图，我们可以看到，其结构几乎和主键索引示意图一样，叶子结点上也有表中行数据的地址：



 

MyISAM的二级索引示意图

B+TREE高度

了解B+Tree索引的大概结构后，我们接下来讲解一下如何计算索引树的高度。

我们先做如下假设：

表的记录数是N；

每个BTREE节点平均有B个索引KEY（即1,2,3,4,5… …）；

很明显，这时候B+TREE索引树的高度就是logBN（等价于logB/logN）。需要说明的是，这里的对数以及接下来有对数的地方应该是下图中的对数，笔者不知道如何将word中的对数复制过来，所以请将就一下下（尴尬￣□￣）：

对数

另外我们知道，由于索引树每个节点大小固定，所以索引KEY越小，B值就越大，即每个BTREE节点上可以保存更多的索引KEY。并且索引树的高度是logBN，那么B值越大，索引树的高度越小，那么基于索引查询的性能就越高。所以我们可以得到结论：相同表记录数的情况下，索引KEY越小，索引树高度就越小。

现在，我们假设表有1600w条记录（因为2^24≈1600w，便于接下来的计算），如果每个节点保存64个索引KEY，那么索引高度就是 (log10^7)/log64 ≈ 24/6 = 4。

所以，由上面的演算可知，我们要计算一张表的索引树的高度，还只需要知道一个节点有多大，从而就能知道每个节点能存储多少个索引KEY。现代数据库经过不断的探索和优化，并结合磁盘的预读特点，每个索引节点一般都是操作系统页的整数倍，操作系统页可通过命令得到该值得大小，且一般是4094，即4k。而InnoDB的pageSize可以通过命令得到，默认值是16k。

关于预读：在索引树上查到某个KEY（例如id=3），需要先找到这个KEY所在的叶子节点（因为B+Tree索引只有叶子节点上有具体的数据），这个查找过程从根节点到叶子节点，需要经过整个树。当找到叶子节点后，会根据预读原理将整个节点数据全部加载到内存中，然后基于二分法找到最终的KEY。

OK，到这里，我们距离真正计算一个拥有1600w数据的表的索引树的高度，只差每个索引KEY所占空间了。

以BIGINT为例，存储大小为8个字节。INT存储大小为4个字节（32位）。索引树上每个节点除了存储KEY，还需要存储指针。所以每个节点保存的KEY的数量为pagesize/(keysize+pointsize)（如果是B-TREE索引结构，则是pagesize/(keysize+datasize+pointsize)）。

假设平均指针大小是4个字节，那么索引树的每个节点可以存储16k/((8+4)*8)≈171。那么：一个拥有1600w数据，且主键是BIGINT类型的表的主键索引树的高度就是(log10^7)/log171 ≈ 24/7.4 ≈ 3.2。

假设平均指针大小是6个字节，那么索引树的每个节点可以存储16k/((8+6)*8)≈146。那么：一个拥有1600w数据，且主键是BIGINT类型的表的主键索引树的高度就是(log10^7)/log146 ≈ 24/7.2 ≈ 3.3。

假设平均指针大小是8个字节，那么索引树的每个节点可以存储16k/((8+8)*8)≈128。那么：一个拥有1600w数据，且主键是BIGINT类型的表的主键索引树的高度就是(log10^7)/log128 ≈ 24/7 ≈ 3.4。

由上面的计算可知：一个千万量级，且存储引擎是MyISAM或者InnoDB的表，其索引树的高度在3~5之间。

说明：这一段对索引树高度的计算，都是基于B+Tree，即InnoDB和MyISAM存储引擎的索引用到的数据结构。而B-TREE索引节点上不仅保存了索引和指针，还保存了具体的行数据，索引树的高度算法略有不同。

 

 

总结

索引树的高度是一个非常重要的东西，因为当查找的条件能用到索引时，就不用全表扫描，而是只需要在索引上搜索，从索引的根节点到叶子节点。并且很明显的是：索引树越高，性能就会越差。我们假设在最糟糕的情况下，索引一点没有被加载到内存中，而是全部持久化在磁盘上。那么索引树有多高，就表示查询至少需要多少次IO操作。即使实际情况中，由于表的数据更多，索引也会很大，不大可能全部被保存在缓存中。而且如果是二级索引搜索，IO次数还要翻倍（二级索引搜索+主键索引搜索），这对性能是一个很大的影响。

这也是MySQL数据库使用B+Tree作为索引结构的原因：尽可能降低索引树的高度。而红黑树等其他数据结构，树的高度要深的多的多。