1.递归构建决策树
从数据集中构建决策树的流程如下：得到原始的数据集，然后基于最好的特征划分数据集，由于特征可能有多个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据集将被向下传递到树分支的下一个节点，在这个节点上，可以再次划分数据。所以采用递归的原则处理数据集。
递归结束的条件：①程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。②如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时我们需要决定如何定义该叶子节点，在这种情况下，我们通常会采用多数表决的方法定义该叶子节点的分类。
2.多数表决法定义类标签不唯一的叶子节点的分类
#多数表决法定义叶子节点的分类
import operator
def majorityCnt(classList):
classCount={}
for vote in classList:
if vote not in ():
classCount[vote]=1
else:
classCount[vote]+=1
sortedClassCount=sorted((),key=(1),reverse=True)
return sortedClassCount[0][0]注：
这部分代码与用KNN算法进行分类的部分代码非常相似。该函数使用分类名称的列表，然后创建键值为classList中唯一值的数据字典，字典对象储存了classList中每个类标签出现的频率，然后利用operator操作键值排序字典，并返回出现次数最多的分类名称。
3.递归构建决策树代码
#递归构建决策树
def createTree(dataSet,labels):
classList=[example[-1] for example in dataSet]
#递归函数第一个停止的条件：所有类标签完全相同，直接返回该类标签
if (classList[0])==len(classList):
return classList[0]
#递归函数的第二个停止条件：使用完所有特征，仍不能将数据集划分成仅包含唯一类别的分组。使用多数表决法决定叶子节点的分类
if len(dataSet[0])==1:
return majorityCnt(classList)
#开始创建决策树
bestFeature=chooseBestFeatureToSplit(dataSet) #选择划分数据集最好的特征的索引
bestFeatureLabel=labels[bestFeature] #根据特征的索引提取索引的名称
decisionTree={bestFeatureLabel:{}} #将此特征作为树的根节点
del labels[bestFeature] #将已放进树中的特征从特征标签中删除
featrueValues=[example[bestFeature]for example in dataSet] #提取所有样本关于这个特征的取值
uniqueVals=set(featrueValues) #应用集合的互异性，提取这个特征的不同取值
for value in uniqueVals: #根据特征的不同取值，创建这个特征所对应结点的分支
subLabels=labels[:]
decisionTree[bestFeatureLabel][value]=createTree(splitDataSet(dataSet,bestFeature,value),subLabels)
return decisionTree测试代码部分：
dataSet=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']];
labels=['no surfacing','flippers']
tree=createTree(dataSet,labels)
print(tree)运行结果：
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}注：
循环的第一行subLabels=labels[:]，这行代码复制了类标签，并将其储存在新列表变量中。之所以这样做是因为在python中函数参数是列表类型时，参数是按照引用方式传递的。为了保证每次调用createTree时不改变原始列表的内容，使用新变量subLabels代替原始列表。
4.上述代码中涉及的其他函数：
(dataSet) ： 选择划分数据集最好的特征
(dataSet,feature,value)：按照给定的特征划分数据集