輸入：訓練資料集D，停止計算的條件；
輸出：CART決策樹
根據訓練資料集，從根結點開始，遞歸地對每個節點進行以下操作，建構二叉決策樹：
（1）設結點的訓練資料集為D，計算現有特征對該資料集的基尼指數。此時，對每一個特征A，對其可能取的每個值a，根據樣本點對a的測試為“是”或“否”将D分為D1和D2兩個部分，利用如下公式計算A=a時的基尼指數
Gini(D,a)=|D1|/|D|*Gini(D1)+|D2|/|D|*Gini(D2)
（2）在所有可能的特征A以及它們所有可能的切分點a中，選擇基尼指數最小的特征及其對應的切分點作為最優特征與最優切分點，依照最優特征和最優切分點，生成兩個子結點，将訓練資料集依特征配置設定到兩個子結點中去。
（3）對兩個子結點遞歸調用（1），（2）直至滿足停止條件。
（4）生成CART決策樹。
算法停止計算的條件是節點中的樣本個數小于預定門檻值，或樣本集的基尼指數小于預定門檻值（樣本基本屬于同一類），或者沒有更多特征。