在樹的構(gòu)建過程中，需要解決多種類型數(shù)據(jù)的存儲問題。在此將使用一部字典來存儲樹的數(shù)據(jù)結(jié)構(gòu)，該字典將包含以下4個元素。

? 待切分的特征。

? 待切分的特征值。

? 右子樹。當(dāng)不再需要切分的時候，也可以是單個值。

? 左子樹。與右子樹類似。

CART算法只做二元切分，所以這里可以固定樹的數(shù)據(jù)結(jié)構(gòu)。樹包含左鍵和右鍵，可以存儲另一棵子樹或者單個值。字典還包含特征和特征值這兩個鍵，它們給出切分算法所有的特征和特征值。當(dāng)然，讀者可以用面向?qū)ο蟮木幊棠Ｊ絹斫⑦@個數(shù)據(jù)結(jié)構(gòu)。例如，可以用下面的Python代碼來建立樹節(jié)點：

class treeNode ():

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

           featureToSplitOn = feat

           valueofSplit = val

           rightBranch = right

           leftBranch = left

當(dāng)使用C++這樣不太靈活的編程語言時，你可能要用面向?qū)ο缶幊棠Ｊ絹韺崿F(xiàn)樹結(jié)構(gòu)。Python具有足夠的靈活性，可以直接使用字典來存儲樹結(jié)構(gòu)而無須另外自定義一個類，從而有效地減少代碼量。Python不是一種強類型編程語言，因此接下來會看到，樹的每個分枝還可以再包含其他樹、數(shù)值型數(shù)據(jù)甚至是向量。

在此將構(gòu)建兩種樹：第一種是回歸樹（regression tree)，其每個葉節(jié)點包含單個值；第二種是模型樹（model tree），其每個葉節(jié)點包含一個線性方程。創(chuàng)建這兩種樹時，我們將盡量使得代碼之間可以重用。下面先給出兩種樹構(gòu)建算法中的一些共用代碼。

函數(shù)createTree()的偽代碼大致如下：

找到最佳的待切分特征：

      如果該節(jié)點不能再分，將該節(jié)點存為葉節(jié)點

      執(zhí)行二元切分

      在右子樹調(diào)用createTree()方法

      在左子樹調(diào)用createTree()方法

打開文本編輯器，創(chuàng)建文件regTrees.py并添加如下代碼。