递归查找树节点

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"。我该怎么做才能确保这个函数能一直往下走，直到没有更多的子项目为止，并把所有的项目都添加到 allItems 列表里呢？

Answer 1

在你的情况下，使用递归的方法可能会更好，因为你对递归的深度要求似乎不高。

如果你的树的高度超过1000，要注意Python默认的递归限制。你可以通过设置 sys.setrecursionlimit(limit) 来改变这个限制，但不建议这样做，因为CPython（Python的默认实现）对深层递归并没有优化，所以保持默认限制更好。

关于递归实现，有很多指南可以参考。这个StackOverflow的问题可以根据你的具体需求进行修改。

如果你想要一个非递归的实现，下面的代码可能适合你的情况【注意，我没有测试过这个代码】。这只是为了让你有个大概念。

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)

Answer 2

下面的代码创建了一个带有嵌套项目的 QTreeWidget。

这个树的 getItemsRecursively() 方法会一直扫描树，直到找到最底层的项目，并返回树中所有项目的列表。

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_())