在树的构建过程中，需要解决多种类型数据的存储问题。在此将使用一部字典来存储树的数据结构，该字典将包含以下4个元素。

• 待切分的特征。

• 待切分的特征值。

• 右子树。当不再需要切分的时候，也可以是单个值。

• 左子树。与右子树类似。

CART算法只做二元切分，所以这里可以固定树的数据结构。树包含左键和右键，可以存储另一棵子树或者单个值。字典还包含特征和特征值这两个键，它们给出切分算法所有的特征和特征值。当然，读者可以用面向对象的编程模式来建立这个数据结构。例如，可以用下面的Python代码来建立树节点：

class treeNode ():

     def __init__(self, feat, val, right, left):

           featureToSplitOn = feat

           valueofSplit = val

           rightBranch = right

           leftBranch = left

当使用C++这样不太灵活的编程语言时，你可能要用面向对象编程模式来实现树结构。Python具有足够的灵活性，可以直接使用字典来存储树结构而无须另外自定义一个类，从而有效地减少代码量。Python不是一种强类型编程语言，因此接下来会看到，树的每个分枝还可以再包含其他树、数值型数据甚至是向量。

在此将构建两种树：第一种是回归树（regression tree)，其每个叶节点包含单个值；第二种是模型树（model tree），其每个叶节点包含一个线性方程。创建这两种树时，我们将尽量使得代码之间可以重用。下面先给出两种树构建算法中的一些共用代码。

函数createTree()的伪代码大致如下：

找到最佳的待切分特征：

      如果该节点不能再分，将该节点存为叶节点

      执行二元切分

      在右子树调用createTree()方法

      在左子树调用createTree()方法

打开文本编辑器，创建文件regTrees.py并添加如下代码。