递归树项搜索

Question

我有嵌套父子项的QTreeWidget：

Tree:
    parent1:
           childA1
           childA2
           childA3:
                  childB1
                  childB2:
                         childC1

使用：

    allItems=[]
    for i in range(Tree.topLevelItemCount()):
        item=Tree.topLevelItem(i)
        allItems.add(item)

我访问第一级项目“A”：childA1、childA2和childA3。

现在，我迭代每个第一级“A”项来访问他们的孩子——第二级项目“B”：

    for i in range(Tree.topLevelItemCount()):
        item=Tree.topLevelItem(i)

        for m in range(item.childCount()):
            childItem=item.child(m)
            allItems.add(childItem)

在第二个层次，我不知道下面是否有任何第三个层次的项目“C”。如何确保函数向下推进，因为下面有嵌套的项目，将项目添加到allItem列表中，直到它到达末尾？

Answer 1

下面的代码使用嵌套项创建QTreeWidget。

Tree的getItemsRecurely（）方法扫描Tree，直到它到达底部项，返回Tree中所有项的列表。

from PyQt4 import QtCore, QtGui
app = QtGui.QApplication([])

class Tree(QtGui.QTreeWidget):
    def __init__(self, *args, **kwargs):
        super(Tree, self).__init__()
        for name in ['Item_A0', 'Item_A1', 'Item_A2']: 
            itemA=QtGui.QTreeWidgetItem([name])

            self.addTopLevelItem(itemA)
            if name=='Item_A1':
                item_B0=QtGui.QTreeWidgetItem(['Item_B0'])
                itemA.insertChild(0, item_B0)
                itemA.insertChild(1, QtGui.QTreeWidgetItem(['Item_B1']))

                item_C0=QtGui.QTreeWidgetItem(['Item_C0'])
                item_B0.insertChild(0, item_C0)
                item_B0.insertChild(0, QtGui.QTreeWidgetItem(['Item_C1']))

        self.resize(360,240)
        self.show()

    def getItemsRecursively(self):
        total=[]
        def serchChildItem(item=None):
            if not item: return
            for m in range(item.childCount()): 
                childItem=item.child(m)                
                if not childItem: continue
                total.append(childItem)   
                serchChildItem(childItem)

        for i in range(self.topLevelItemCount()):
            item=self.topLevelItem(i)
            if not item: continue
            total.append(item)
            serchChildItem(item)
        return total

tree=Tree()
total=tree.getItemsRecursively()
print 'Total number of Tree items: %s'%len(total)
sys.exit(app.exec_())

Answer 2

您最好使用递归实现，尤其是在您的情况下，对递归深度的要求似乎很低。

如果树的高度超过1000，请注意Python有一个默认的递归限制[可以通过sys.setrecursionlimit（limit）设置限制来覆盖该限制，尽管不鼓励这样做，因为CPython（Python的默认实现）不会优化深度递归，因此也不会优化默认限制]

对于这种递归实现，有很多指南。因此，这里的问题可以根据您的具体应用进行修改。

如果你想要一个非递归的实现，下面的方法可以适用于你的情况[请注意，我还没有测试过同样的方法]。这只是为了让你得到一个想法。

allItems=[]
buff = []

# Populating the buffer with all the top level items
for i in range(Tree.topLevelItemCount()):
    item=Tree.topLevelItem(i)
    buff.append(item)

while len(buff) > 0:
    # Take the first item out of the buffer by popping it
    current_item = buff.pop(buff[0])

    # Put all the childs of current_item in the buffer
    for child_no in range(current_item.childCount):
        buff.append(current_item.child(child_no))

    # Append the current_item to the allItems list
    allItems.append(current_item)