决策树-获得叶节点的数目和树的层数

现在我们要获取叶节点和深度，以便后面画图

对于叶节点，思路如下

{'no surfacing':{0:'no',1:{'flippers':{0:'no',1:'yes'}}}}

1. 对于这样的字典，我们先得到根节点
2. 然后得到根节点下面的字典
3. 这个字典可能是空的，对这个字典进行遍历，如果里面有字典则遍历，无字典则进行叶节点+1
4. 最后返回叶节点个数

def getNumLeafs(myTree):
    # 首先得到根节点
    # firstNode = myTree.keys()[0]
    # 不能直接对keys进行索引，需先转化成list
    firstNode = list(myTree.keys())[0]
    # print(firstNode)
    # 得到no surfacing
    # 获得根节点对应的字典
    secondDict = myTree[firstNode]
    # 对这个字典进行遍历，如果里面还有字典那就继续遍历
    numLeafs = 0
    for key in secondDict.keys():
        if type(secondDict[key]) == dict:
            numLeafs += getNumLeafs(secondDict[key])
        else:
            # 如果没有了那么叶节点数量 + 1
            numLeafs += 1
    return numLeafs

myTree = {'no surfacing':{0:'no',1:{'flippers':{0:'no',1:'yes'}}}}
print(getNumLeafs(myTree))

3

def getTreeDepth(myTree):
    # 首先得到根节点
    # firstNode = myTree.keys()[0]
    # 不能直接对keys进行索引，需先转化成list
    firstNode = list(myTree.keys())[0]
    # print(firstNode)
    # 得到no surfacing
    # 获得根节点对应的字典
    secondDict = myTree[firstNode]
    # 对这个字典进行遍历，如果里面还有字典那就继续遍历
    # 树的深度要去掉根节点
    maxDepth = 0
    for key in secondDict.keys():
        if type(secondDict[key]) == dict:
            tempDeth = 1 + getTreeDepth(secondDict[key])
        else:
            tempDeth = 1
        if tempDeth > maxDepth:
            maxDepth = tempDeth
    return maxDepth

myTree = {'no surfacing':{0:'no',1:{'flippers':{0:'no',1:'yes'}}}}
print(getTreeDepth(myTree))

2