12.2构建FP 树

12.2 构建FP树

树的数据结构：

class treeNode:

def __init__(self, nameValue, numOccur, parentNode):

self.name = nameValue

self.count = numOccur

self.nodeLink = None #用于链接相似的元素项

self.parent = parentNode #指向父节点的指针

self.children = {}

def inc(self, numOccur):

    self.count += numOccur

def disp(self, ind=1): #将树以文本形式显示

    print " "*ind, self.name, " ",self.count

    for child in self.children.values():

    child.disp(ind+1)

构建树的图示过程：

#================FP树构建函数=============================

def updateTree(items, inTree, headerTable, count):
    if items[0] in inTree.children:                 #测试第一个元素项是否作为子节点存在
        inTree.children[items[0]].inc(count)
    else:
        inTree.children[items[0]] = treeNode(items[0], count, inTree)           #创建树的新节点
        if headerTable[items[0]][1] == None:
            headerTable[items[0]][1] = inTree.children[items[0]]                #树上的新的节点的值更新
        else:
            updateHeader(headerTable[items[0]][1], inTree.children[items[0]])   #如果节点已经有了，这两个进行链接下
    if len(items) > 1:
        updateTree(items[1::], inTree.children[items[0]], headerTable, count)   #添加了首节点，递归添加剩下的节点
 
def updateHeader(nodeToTest, targetNode):
    while (nodeToTest.nodeLink !=None):
        nodeToTest = nodeToTest.nodeLink
    nodeToTest.nodeLink = targetNode

数据辅助函数，讲列表转化为字典: