第一步：构造根结点
第二步：重复划分
令当前结点的深度为depth，计算：
feature = depth % n value = T[:, feature]的下中位数。
选择在第feature个特征上基于value将数据划分成2份。
第三步：结束
区域中没有实例时停止。
# 计算下中位数
def getDownMedian(data):
if data.shape[0] % 2 == 0:
data = np.hstack([data, np.inf])
return np.median(data)
def seperateNode(node, depth):
dataSet = node['data']
if dataSet.shape[0] == 0:
return None
feature = depth % dataSet.shape[1]
value = getDownMedian(dataSet[:, feature])
node['left'] = {'data':dataSet[dataSet[:,feature] < value, :], 'left':None, 'right':None}
node['right'] = {'data':dataSet[dataSet[:,feature] > value, :], 'left':None, 'right':None}
node['data'] = dataSet[dataSet[:,feature] == value, :]
seperateNode(node['left'], depth+1)
seperateNode(node['right'], depth+1)
return node
def createTree(dataSet):
root = {'data':dataSet, 'left':None, 'right':None}
seperateNode(root, 0)
return root
`