搜索 Python 中的任何树

Question

我需要在 Python 中编写一个函数，它接受一棵树和一个索引，并且 return 是该索引处的子树或叶。

我尝试使用循环和嵌套循环，直到我意识到必须运行测试的树总是相同的：

tree = (((1, 2), 3), (4, (5, 6)), 7, (8, 9, 10))

实际上是这样的：

Sample tree

所以我需要通过给定的测试是这样的：

def tree_ref(tree, index):
    if len(index) == 1:
        print tree[index[0]]
    elif len(index) == 2:
        print tree[index[0]][index[1]]
    elif len(index) == 3:
        print tree[index[0]][index[1]][index[2]]
    else:
        return False

例如，对于索引 = (1, 1, 0)，它应该 return 数字 5，它确实如此。

但是，我知道此代码不适用于其他树或包含 3 个以上元素的索引。我怎样才能让它适用于任何给定的树和索引？

Answer 1

看看这个：How can I implement a tree in Python? Are there any built in data structures in Python like in Java?

您应该考虑将您的节点实现为 class，如链接文章中所述。如果你使用列表，你很容易就会遇到你现在正在努力解决的问题。基于 class 的树不依赖于特定的形状或深度，并且更通用且更易于实现和搜索。

汉奴

Answer 2

你应该尝试使用递归。

如下所示：

def tree_ref(tree, index):
    if len(index) == 1:
        print tree[index[0]]
    else:
        tree_ref(tree[index[0]], index[1:])

Answer 3

在我看来 itertree 包（我是作者）为这个问题提供了一个很好的解决方案。

首先我们构建一棵表示给定元组结构的树：

>>>from itertree import *
>>>root=iTree('root')
>>># we must use some helper tags ("sub","sub2","sub3") to fill the tree
>>>root += iTree('sub')
>>>root += iTree('sub')
>>>root += iTree('sub',data=7)
>>>root += iTree('sub')
>>>root[0] += iTree('sub2')
>>>root[0][0] += iTree('sub3', data=1)
>>>root[0][0] += iTree('sub3', data=2)
>>>root[0] += iTree('sub2', data=3)
>>>
>>>root[1] += iTree('sub2', data=4)
>>>root[1] += iTree('sub2')
>>>root[1][0] += iTree('sub3', data=5)
>>>root[1][0] += iTree('sub3', data=6)
>>>
>>>root[3] += iTree('sub2', data=8)
>>>root[3] += iTree('sub2', data=9)
>>>root[3] += iTree('sub2', data=10)

树的内容是这样的：

>>>root.render()
iTree('root')
     └──iTree('sub')
         └──iTree('sub2')
             └──iTree('sub3', data=1)
             └──iTree('sub3', data=2)
         └──iTree('sub2', data=3)
     └──iTree('sub')
         └──iTree('sub2', data=4)
             └──iTree('sub3', data=5)
             └──iTree('sub3', data=6)
         └──iTree('sub2')
     └──iTree('sub', data=7)
     └──iTree('sub')
     └──iTree('sub2', data=8)
     └──iTree('sub2', data=9)
     └──iTree('sub2', data=10)

现在可以通过索引访问项目：

>>>print(root[0][0][0].d_get())
1
>>># or
>>>print(root.get_deep([1, 0, 1]).d_get())
6

项目本身也知道他的索引路径：

>>>print(root.get_deep([0,0,1]).idx_path)
[0, 0, 1]

也可以过滤访问数据内容：

>>>item_filter=Filter.iTFilterData(data_value=iTInterval(2,5))
>>>for i in root.iter_all(item_filter):
>>>    print(i)
iTree("'sub2'", data=3, subtree=[])
iTree("'sub2'", data=4, subtree=[iTree("'sub3'", data=5, subtree=[]), iTree("'sub3'", data=6, subtree=[])])

搜索 Python 中的任何树

Searching any tree in Python

python

tree

search

artificial-intelligence