继续思考:观察数据会发现好多image会有同样的base image,那么针对这些image,我们需要将他们归并到一条分支上。或者说要找出他们的祖先,将他们归并道对应的祖先分支上。那么思想和树很像了,决定用树形结构来处理。
简化抽象需求,画出简图如下:
使用python treelib模块构造多叉树:
将每一层的树节点的id,编为child1,child11...child2,child22...同一层后缀数字一样,个数不一样,不同层数字不一样,以此类推。这样的好处就是我能根据节点ID,就知道它属于第几层。
class node:def __init__(self, data):
self._data = data
self._children = []
def getdata(self):
return self._data
def getchildren(self):
return self._children
def add(self, node):
##if full
if len(self._children) == 4:
return False
else:
self._children.append(node)
def go(self, data):
for child in self._children:
if child.getdata() == data:
return child
return None
class tree:
def __init__(self):
self._head = node('header')
def linktohead(self, node):
self._head.add(node)
def insert(self, path, data):
cur = self._head
for step in path:
if cur.go(step) == None:
return False
else:
cur = cur.go(step)
cur.add(node(data))
return True
def search(self, path):
cur = self._head
for step in path:
if cur.go(step) == None:
return None
else:
cur = cur.go(step)
return cur
'''
define node
'''
a = node('A')
b = node('B')
c = node('C')
d = node('D')
e = node('E')
f = node('F')
g = node('G')
h = node('H')
i = node('I')
j = node('J')
k = node('K')
l = node('L')
m = node('M')
n = node('N')
o = node('O')
'''
adding node to build true
'''
a.add(b)
a.add(g)
a.add(h)
b.add(c)
b.add(e)
g.add(i)
g.add(j)
g.add(k)
g.add(l)
h.add(m)
h.add(n)
h.add(o)
c.add(d)
c.add(f)
i.add(node(29))
j.add(node(28))
k.add(node(27))
l.add(node(26))
m.add(node(25))
n.add(node(24))
o.add(node(23))
f.add(node(30))
tree = tree()
tree.linktohead(a)
#testcase
print 'Node',tree.search("ABE").getdata()
print 'Node',tree.search("ABC").getdata()
print 'Node',tree.search("AHM").getdata()
tree.insert("ABCD", 1)
for i in d.getchildren():
print 'value after', d.getdata(),' is ', i.getdata()