创建树的根节点（root node）是比较方便的，可以调用 get_split() 函数并传入整个数据集即可达到此目的。但向树中增加更多的节点则比较有趣。

建立树结构主要分为三个步骤：

1. 创建终端节点

2. 递归地分割

3. 建构整棵树

2.3.1 创建终端节点

我们需要决定何时停止树的「增长」。

我们可以用两个条件进行控制：树的深度和每个节点分割后的数据点个数。

最大树深度：这代表了树中从根结点算起节点数目的上限。一旦树中的节点树达到了这一上界，则算法将会停止分割数据、增加新的节点。更神的树会更为复杂，也更有可能过拟合训练集。

最小节点记录数：这是某节点分割数据后分个部分数据个数的最小值。一旦达到或低于该最小值，则算法将会停止分割数据、增加新的节点。将数据集分为只有很少数据点的两个部分的分割节点被认为太具针对性，并很有可能过拟合训练集。

这两个方法基于用户给定的参数，参与到树模型的构建过程中。

此外，还有一个情况。算法有可能选择一个分割点，分割数据后所有的数据都被分割到同一组内（也就是左叉、右叉只有一个分支上有数据，另一个分支没有）。在这样的情况下，因为在树的另一个分叉没有数据，我们不能继续我们的分割与添加节点的工作。

基于上述内容，我们已经有一些停止树「增长」的判别机制。当树在某一结点停止增长的时候，该节点被称为终端节点，并被用来进行最终预测。

预测的过程是通过选择组表征值进行的。当遍历树进入到最终节点分割后的数据组中，算法将会选择该组中最普遍出现的值作为预测值。

如下是一个名为 to_terminal() 的函数，对每一组收据它都能选择一个表征值。他能够返回一系列数据点中最普遍出现的值。

# Create a terminal node value

def to_terminal(group):

outcomes = [row[-1] for row in group]

return max(set(outcomes), key=outcomes.count)

2.3.2 递归分割

在了解了如何及何时创建终端节点后，我们现在可以开始建立树模型了。

建立树地模型，需要我们对给定的数据集反复调用如上定义的 get_split() 函数，不断创建树中的节点。

在已有节点下加入的新节点叫做子节点。对树中的任意节点而言，它可能没有子节点（则该节点为终端节点）、一个子节点（则该节点能够直接进行预测）或两个子节点。在程序中，在表示某节点的字典中，我们将一棵树的两子节点命名为 left 和 right。

一旦一个节点被创建，我们就可以递归地对在该节点被分割得到的两个子数据集上调用相同的函数，来分割子数据集并创建新的节点。

如下是一个实现该递归过程的函数。它的输入参数包括：某一节点（node）、最大树深度（max_depth）、最小节点记录数（min_size）及当前树深度（depth）。

显然，一开始运行该函数时，根节点将被传入，当前深度为 1。函数的功能分为如下几步：

1. 首先，该节点分割的两部分数据将被提取出来以便使用，同时数据将被在节点中删除（随着分割工作的逐步进行，之前的节点不需要再使用相应的数据）。

2. 然后，我们将会检查该节点的左叉及右叉的数据集是否为空。如果是，则其将会创建一个终端节点。

3. 同时，我们会检查是否到达了最大深度。如果是，则其将会创建一个终端节点。

4. 接着，我们将对左子节点进一步操作。若该组数据个数小于阈值，则会创建一个终端节点并停止进一步操作。否则它将会以一种深度优先的方式创建并添加节点，直到该分叉达到底部。

5. 对右子节点同样进行上述操作，不断增加节点直到达到终端节点。

2.3.3 建构整棵树

我们将所有的内容整合到一起。

创建一棵树包括创建根节点及递归地调用 split() 函数来不断地分割数据以构建整棵树。

如下是实现上述功能的 bulid_tree() 函数的简化版本。

# Build a decision tree

　　def build_tree(train,max_depth,min_size):

　　root=get_split(dataset)

　　split(root,max_depth,min_size,1)

　　returnroot

我们可以在如上所述的合成数据集上测试整个过程。如下是完整的案例。