将matplotlib嵌入C图形化输出一棵B树

标题:

B树

绘制B树

获取叶节点数目与树的层数

annotations

主函数

绘制函数

与C混编

C的ide配置

编写调用

本次我们使用的Python版本依然是Python2.7版本。关于Python版本的问题，感兴趣的读者可以在我们的其他文章中，或者自行搜索资料了解。

我们前面有过一篇关于逻辑回归的机器学习实战文章，其中用到了一个matplotlib包用于可视化模型和数据样本，作为python科学计算常用的三大基础包（“Numpy”，“Pandas”，“Matplotlib”）之一，matplotlib的功能是非常强大的，它作为一个专门用于数学绘图的Python库，也不仅仅只是用于可视化机器学习的一些算法模型和数据样本的。这次我们就通过一个可视化B树的小demo来介绍一下matplotlib包。

1. B树

关于B树的详细内容相信读者会有更多更好地学习方式，我们这里只是简单提一下程序中和B树相关的内容，以便于读者轻松地理解我们的代码：

我们在C代码中，用t表示一个指向B树根节点的指针，它被设为BTree类型：

在Python中，我们借助Python提供的tuple类来表示一棵B树，当然，由于tuple不能够改变内容，所以如果是仅在Python中编写树形结构的话，dict和list会方便的多，但介于C和Python通信时仅能够传输tuple或者integer这类的不可变量，我们这里就采用tuple来作为B树在Python中的结构。具体的表现形式是，一个tuple表示一个结点，其中的Integer是这个结点上的关键字，这个tuple中嵌套的tuple则表示这个结点的子树，举个栗子：

上图中的树如果用tuple表示的话就是

(62,(24,41,(5),(27,34),(45,48)),(69,(64,67),(78,81)))

类似于广义表一样的表示方式。

2. 绘制B树

a. 获取叶节点数目与树的层数

在绘制之前，我们需要先写三个简单的小函数来获取叶节点数目与树的层数以及当前结点的孩子数量，因为在绘图时我们需要计算每个结点在画布上的横坐标与纵坐标，因此需要通过树的宽度和高度以及结点所在的高度和其宽度来判断结点在树中的位置。

计算当前节点下叶节点数目的函数如下：

计算当前节点下树的层数的函数：

获取孩子数量的函数：

这三个函数中的参数tree就是B树在Python中的tuple，函数的内容并不复杂，利用简单地递归就可以实现。

b. annotations

然后我们要用到一个matplotlib提供的用于编写注解的工具“annotations”，它可以在数据图形上添加文本注释，藉由它，我们可以绘制一个带有箭头指向的节点，如图所示：

藉由这个工具，我们可以将绘制一个结点的函数写为：

是由函数提供的一个类型为matplotlib画板的全局变量，这个函数我们将在后面编写。

先看到，这就是用于创建注解的函数，它与绘制散点图的或者绘制直方图的等绘图函数用的地方相同。

第一个参数接受节点的名字，这个名字会被放在上图中的”finalLoc”的位置，即箭头指向的位置。

参数接收一个tuple (x,y)作为箭头起点的坐标，则接收一个tuple作为箭头指向终点的坐标。

接受表示起点坐标的坐标系，表示（0，0）作为左下角，（1，1）作为右上角。同理，表示终点坐标的坐标系模式。这样设置后，画布上的坐标分布就会变成下图中的形式

结点“1”在画布上的坐标就是(0.5,1.0)

表示箭头终点节点在图上的形状的类型，我们这里设置了的类型是：

则表示箭头类型：

c. 主函数

绘制树的主要函数有两个，一个以递归形式调用绘制节点函数来绘制整个树，一个作为主函数整合绘制函数。绘制结点的函数为

其参数含义为：

我们先编写一个调用该绘制函数的主函数：

主函数提供了下面要编写的绘制函数用到的全局变量，包括决策树的宽（），高（），画板（）等等。清屏函数用来将画板上可能有的之前绘制的内容清除掉，如果是脚本形式编写这个函数用处不大，但如果是交互式编写那么就很有必要了。

d. 绘制函数

最后我们编写绘制函数：

是当前结点的横坐标，y是纵坐标，时表示当前要绘制的结点是根节点，因为B树由于其性质的原因，在图像上是大致对称的，因此我们可以将根节点绘制在画布最上方的最中心。

时表示接下来要绘制的这个结点是其兄弟结点中最靠左的结点，它的横坐标等于：

其中

是这个结点的所有兄弟结点之间的空隙大小，分子包含结点的叶节点数量，分母包含整棵树的叶节点数量，从而实现“结点所拥有叶节点数量越多，它与兄弟结点的空隙就越大”的效果，某个常数可以是除零和负数以外得任意常数，主要用于控制这个间隙的大小。因为这个结点是最左边的结点，因此startloc参数在绘制这个结点时其内容是这个结点的双亲结点的坐标。

当这个结点不是根节点时（），当前结点的横坐标就计算为

换句话说，就是上一个结点往右移一个“空隙”。

结点的纵坐标计算就没有那么麻烦，直接就是：

换言之，两个坐标的计算方式其实就是将和作为横坐标和纵坐标移动的单位。

代码完成后我们可以用一个简单的tuple来测试一下代码的效果：

3. 与C混编

尽管已经完成了绘图脚本，但由于我们的B树结构是用C语言编写的，因此，我们还要将Python嵌入到C让C来调用Python脚本。

Python与C混编的方式主要有两种，一种是Python调用C，一种是C调用Python，前者比较常用，因为事实上Python中的很多主流模块都是先用C编写，然后再链接到Python供Python调用的（甚至Python本身，也是用C编写出来的）。但这一次我们使用后者的方式，因为若是用Python调用C，我们还需要在Python中编写调用C中B树的各个接口，这样就会加入太多不相干的内容了，因此，为了方便起见，我们就先使用将Python嵌入C的方式来完成我们的小demo。

a. C的ide配置

C要调用Python首先需要进行一些简单的配置，这里以Windows系统下的Codeblocks为例，来介绍一下怎么样配置一个可以嵌入Python的C语言编译器。

首先新建一个工程，在Codeblocks界面中的菜单栏中找到Settings（设置）一项然后选择该项下拉列表中Compiler（编译器）项

在弹出窗口中Global compiler Settings（就是第一项“全局编译器设置”）中Search directories选项卡下Compiler选项卡中将Python目录下的include文件夹路径添加进去

然后再切到Linker选项卡将libs文件夹路径添加进去

再切到Linker setting选项卡中，将libs文件夹下的python27.libs的路径添加进去

这样子就完成了C对Python的链接，在C语言文件中添加下面这一行头文件声明

然后编译一次，如果没有报错，就说明成功了。

但是要注意的是，C的编译环境如果是32位，那么链接的Python也必须是32位，同样64位也只能链接64位的Python，如果不这么做，尽管也可以添加Python.h头文件，但在后续调用Python函数的时候会出现“函数未定义”（Undefined）的错误。

实际上，在学习过程中的话，我们最好将Python的各个版本都安装在电脑上，因为Python作为一个比较新的语言，在使用一些第三方模块的时候不同版本之间很容易出现一些奇怪的问题，像是Python的一个轻量级爬虫框架PySpider就不能在Windows中64位的Python2.x版本中运行（据说是因为作者本人不用Windows，因此不太熟悉如何兼容64位Windows），但可以在32位中的Python运行。笔者本人就安装了Python2.7的32位和64位，Python3.6的32位和64位统共4个Python在电脑上...（但事实上切换它们并不困难，有的ide例如Pycharm就提供了转换Python路径的功能，如果没有，也可以简单的修改环境变量来实现转换）

b. 编写调用

接下来就用C语言编写调用Python的代码，不过在这之前我们需要先在main函数中提前写好初始化Python编译器的代码，因为在C程序的一次运行中，Python编译器初始化后如果再关闭就没有办法再启动了，想要反复执行调用Python的函数，我们就要在程序运行的最开始初始化，然后再在程序运行的最后再关闭它。假设我们要运行的主体部分用一个Run函数囊括，那么main函数的内容就是：

BTree.h头文件中调用了Python.h，这点不要忘记了。Run函数中是程序运行的主体，里面包含了对B树的操作，当然也包含了我们图形化输出B树的操作。

然后我们编写C中嵌入Python脚本的代码，关于嵌入Python的详细知识可以参考我在文章末尾提供的资料参考来源，我这里依然只讲解我用到的部分：

首先是将B树转换成Python中tuple的函数：

类型用于声明所有属于Python的类型，Python中的Integer也好，float也好，tuple也好，在C语言中都用声明。函数接受一个整型，返回一个包含了未定义的等同于该整型大小的数量的元素的tuple，例如，就会返回一个含有两个未定义的元素的tuple，这两个元素的内容用来设定，参数中的tuple接收一个tuple表示要设置的tuple，location接收一个整型表示设置的元素的位置，就像数组一样，第一个元素的位置是0，value接收一个，就是要放进元素的“值”。

函数中我们先创建tuple然后遍历一个B树的结点，对于关键字就用创建一个Python对象，它会在执行成功后返回这个对象，这里第一个参数用“i”表示创建为整型，第二个参数表示这个整型的值；对于子结点就加入递归，创建为另一个tuple。

然后我们编写嵌入Python的主函数：

执行对模块的导入，这里导入的模块就是我们在之前编写的Python脚本，我给它命名为“BTreeDrawer.py”，当然在这里导入不用加“.py”，调用这个模块的方法，就是我们之前写的，再用执行该方法。需要注意的是的第二个参数接收的是传入调用方法的参数，并且只能够是tuple，在这里，我们传入的就是被一个tuple包裹着的B树的tuple。

至此，我们就可以编译运行C程序看一看我们用matplotlib绘制的B树效果：

资料参考来源：

人民邮电出版社 Peter Harrington《机器学习实战》第三章

Python之美[从菜鸟到高手]--一步一步动手给Python写扩展嵌入python的c++程序发布（一）最简单的方法

(http://blog.csdn.net/you_lan_hai/article/details/7917608)

嵌入python的c++程序发布（二）最小化抽取需要的模块

(http://blog.csdn.net/you_lan_hai/article/details/7930866)

AI遇见机器学习

mltoai