<p>下面是深度优先和广度优先搜索的实现,不限于字符串。搜索一个列表或元组需要一些修改。在</p>
<pre><code>>>> l = [['Root', ['span 1 6'], ['Nucleus', ['span 1 3'], ['Nucleus', ['span 1 2'], ['Nucleus', ['leaf 1'], ['text', "Specific knowledge "]], ['Satellite', ['leaf 2'], ['rel2par Elaboration'], ['text', 'required !_']]], ['Satellite', ['leaf 3'], ['rel2par Elaboration'], ['text', 'The tester is ']]], ['Satellite', ['span 4 6'], ['rel2par Elaboration'], ['Satellite', ['leaf 4'], ['rel2par Attribution'], ['text', 'For instance , the tester is aware!_']], ['Nucleus', ['span 5 6'], ['Nucleus', ['leaf 5'], ['rel2par Contrast'], ['text', 'that a!_']], ['Nucleus', ['leaf 6'], ['rel2par Contrast'], ['text', 'but ']]]]]]
>>> def depth_first(term,data):
... for i, item in enumerate(data):
... if isinstance(item,Sequence) and not isinstance(item,basestring):
... r = depth_first(term,item)
... if not r is None:
... return [i] + r
... else:
... if item == term:
... return [i]
...
>>> def breadth_first(term,data):
... later = []
... for i, item in enumerate(data):
... if isinstance(item,Sequence) and not isinstance(item,basestring):
... later.append((i,item))
... else:
... if item == term:
... return [i]
... for i, item in later:
... r = breadth_first(term,item)
... if not r is None:
... return [i] + r
>>> depth_first('span 1 2',l)
[0, 2, 2, 1, 0]
>>> breadth_first('span 1 2',l)
[0, 2, 2, 1, 0]
</code></pre>