在树的构建过程中，需要解决多种类型数据的存储问题。与第3章类似，这里将使用一部字典来存储树的数据结构，该字典将包含以下4个元素。
- 待切分的特征。
- 待切分的特征值。
- 右子树。当不再需要切分的时候，也可以是单个值。
- 左子树。与右子树类似。
这与第3章的树结构有一点不同。第3章用一部字典来存储每个切分，但该字典可以包含两个或两个以上的值。而CART算法只做二元切分，所以这里可以固定树的数据结构。树包含左键和右键，可以存储另一棵子树或者单个值。字典还包含特征和特征值这两个键，它们给出切分算法所有的特征和特征值。当然，读者可以用面向对象的编程模式来建立这个数据结构。例如，可以用下面的Python代码来建立树节点：
class treeNode: def __init__(self, feat, val, right, left): featureToSplitOn = feat valueOfSplit = val rightBranch = right leftBranch = left 当使用C++这样不太灵活的编程语言时，你可能要用面向对象编程模式来实现树结构。Python具有足够的灵活性，可以直接使用字典来存储树结构而无须另外自定义一个类，从而有效地减少代码量。Python不是一种强类型编程语言 ，因此接下来会看到，树的每个分枝还可以再包含其他树、数值型数据甚至是向量。
本章将构建两种树：第一种是9.4节的回归树（regression tree），其每个叶节点包含单个值；第二种是9.5节的模型树（model tree），其每个叶节点包含一个线性方程。创建这两种树时，我们将尽量使得代码之间可以重用。下面先给出两种树构建算法中的一些共用代码。
函数createTree的伪代码大致如下：
找到最佳的待切分特征: 如果该节点不能再分，将该节点存为叶节点 执行二元切分 在右子树调用createTree方法 在左子树调用createTree方法
打开文本编辑器，创建文件regTrees.py并添加如下代码。
程序清单9-1 CART算法的实现代码
from numpy import *def loadDataSet(fileName): dataMat = fr = open(fileName) for line in fr.readlines: curLine = line.strip.split(/'t/') #❶ 将每行映射成浮点数 fltLine = map(float,curLine) dataMat.append(fltLine) return dataMatdef binSplitDataSet(dataSet, feature, value): mat0 = dataSet[nonzero(dataSet[:,feature] > value)[0],:][0] mat1 = dataSet[nonzero(dataSet[:,feature] <= value)[0],:][0] return mat0,mat1def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)): feat, val = chooseBestSplit(dataSet, leafType, errType, ops) #❷ 满足停止条件时返回叶节点值 if feat == None: return val retTree = {} retTree[/'spInd/'] = feat retTree[/'spVal/'] = val lSet, rSet = binSplitDataSet(dataSet, feat, val) retTree[/'left/'] = createTree(lSet, leafType, errType, ops) retTree[/'right/'] = createTree(rSet, leafType, errType, ops) return retTree 上述程序清单包含3个函数：第一个函数是loadDataSet ，该函数与其他章节中同名函数功能类似。在前面的章节中，目标变量会单独存放其自己的列表中，但这里的数据会存放在一起。该函数读取一个以tab键为分隔符的文件，然后将每行的内容保存成一组浮点数❶。
第二个函数是binSplitDataSet，该函数有3个参数：数据集合、待切分的特征和该特征的某个值。在给定特征和特征值的情况下，该函数通过数组过滤方式将上述数据集合切分得到两个子集并返回。
最后一个函数是树构建函数createTree，它有4个参数：数据集和其他3个可选参数。这些可选参数决定了树的类型：leafType给出建立叶节点的函数；errType代表误差计算函数；而ops是一个包含树构建所需其他参数的元组。
函数createTree是一个递归函数。该函数首先尝试将数据集分成两个部分，切分由函数chooseBestSplit完成（这里未给出该函数的实现）。如果满足停止条件，chooseBestSplit将返回None和某类模型的值❷。如果构建的是回归树，该模型是一个常数。如果是模型树，其模型是一个线性方程。后面会看到停止条件的作用方式。如果不满足停止条件，chooseBestSplit将创建一个新的Python字典并将数据集分成两份，在这两份数据集上将分别继续递归调用createTree函数。
程序清单9-1的代码很容易理解，但其中的方法 chooseBestSplit现在暂时尚未实现，所以函数还不能看到createTree的实际效果。但是下面可以先测试其他两个函数的效果。将程序清单9-1的代码保存在文件regTrees.py中并在Python提示符下输入如下命令：
>>> import regTrees>>> testMat=mat(eye(4))>>> testMatmatrix([[ 1., 0., 0., 0.], [ 0., 1., 0., 0.], [ 0., 0., 1., 0.], [ 0., 0., 0., 1.]]) 这样就创建了一个简单的矩阵，现在按指定列的某个值来切分该矩阵。
>>> mat0,mat1=regTrees.binSplitDataSet(testMat,1,0.5)>>> mat0matrix([[ 0., 1., 0., 0.]])>>> mat1matrix([[ 1., 0., 0., 0.], [ 0., 0., 1., 0.], [ 0., 0., 0., 1.]]) 很有趣吧。下面给出回归树的chooseBestSplit函数，还会看到更有趣的结果。下一节将针对回归树构建，在chooseBestSplit函数里加入具体代码，之后就可以使用程序清单9-1的CART算法来构建回归树。