递归查找 ID 的子项及其基础子项

Question

我创建了一个包含两列的 table，"TOP" 和 "UNDER"。 TOP 是具有唯一 ID 的父列，UNDER 包含基础 ID，由“,”分隔。 UNDER 中的项目也可以是 "TOP" 列中列出的父项。

TOP     UNDER
----    --------
A       B
B       C,D
C       E,F
D       X,Y,Z
Z       J,K,L
E       V,M
F       G

我正在尝试创建一个函数，它将 return TOP 的所有 UNDER 字符。即：foo("C") = [E, V, M, F, G]。 E 有 V，M. F 有 G。我不知道如何实现递归部分。每次我尝试实现它时，我都会陷入无限循环。

import sqlite3  
conn = sqlite3.connect("myTable.db") #Conn is a connection object that reps the db
conn.row_factory = sqlite3.Row #access columns of a query by name instead of index 
cursor = conn.cursor()   
id="C"    
cursor.execute("select * from myTable where id='%s'" %id)

def get_underlying(under_list, result_list=[]):
    if len(under_list) == 0:
        return result_list

    print("Query results for: select * from myTable where id='%s'" %(id))
    cursor.execute("select * from myTable where id='%s'" %id)
    r = cursor.fetchall()

    if r == []:
        return result_list

    under_list = r[0]['UNDER'].split(",") 
    for c in under_list:
        result_list.append(c)

    #???? lost on what to write
    if len(r) == 0:
        return
    elif len(r) == 1:
        return
    else
        return

print get_underlying("C")

Under_list 将包含当前的 UNDER 值。即 foo("D"), under_list = [X, Y, Z]。然后我将每个元素附加到 result_list.

我接近 problem/implementing 它的方式不对吗？我能得到一些帮助吗？我已经用谷歌搜索了几个小时，但我似乎无法准确地表达我的搜索以找到指南或解决方案。

Answer 1

编辑

已修改以处理图中的循环。（"TOP" 和 "UNDER" 让我认为这是一棵树，但也许这不是保证。）

from __future__ import print_function
import sqlite3

conn = sqlite3.connect('myTable.db')
conn.row_factory = sqlite3.Row
c = conn.cursor()

def initialize():
    c.execute('create table myTable (ID text, UNDER text)')

    data = [
        ['A', 'B'],
        ['B', 'C,D'],
        ['C', 'E,F'],
        ['D', 'X,Y,Z'],
        ['Z', 'J,K,L'],
        ['E', 'V,M'],
        ['F', 'G,C'], # note the cycle!
    ]

    for top, under in data:
        c.execute('insert into myTable values (?, ?)', (top, under))

    conn.commit()

def get_all_reachable(node_id, found=None):
    if found is None:
        found = set()

    c.execute('select * from myTable where id=?', (node_id,))
    rows = c.fetchall()

    if len(rows) == 0:
        return []

    for child in rows[0]['UNDER'].split(','):
        if child not in found:
            found.add(child)
            get_all_reachable(child, found)

    return found

if __name__ == '__main__':
    initialize()
    print(get_all_reachable('C'))

# Output:
# {'V', 'C', 'M', 'G', 'F', 'E'}

递归查找 ID 的子项及其基础子项

Recursively finding an ID's child and its underlying children

python

sqlite

tree

recursion