python - 遍历一个 Spaghetti Stack 并返回到一棵树

Question

我有一个 Spaghetti Stack(一种 N 叉树数据结构，其中子节点具有指向父节点的指针)- 从数据库接收。

从数据库接收到的“堆栈”只是一个包含所有节点的列表，因此可以里面有多个堆栈。

节点是来自数据库的记录，其中 parent.id 是指向相同类型的另一条记录的外键。

class Node_Category:
  def __init__(self, value):
    self.value = value
    parent_id = id

结构是这样的:

Category 1
 -Category 1_1
  --Category 1_1_1
 -Category 1_2
Category_2
Category_3
 -Category 3_1
 -Category 3_2

我需要什么:

现在我知道 child 的 parent 了。从父节点开始，我需要了解他的 child 。

所以我需要遍历“意大利面条堆栈”，在父节点中添加连接到子节点，这样我就可以从父节点遍历到子节点。

parent 可以有 0 个、一个或多个 child 。

因为我不知道堆栈的深度，所以我尝试递归执行它。

此外，我认为一种内存形式是必要的，因为通过数组循环父项的父项可以获得多次访问。

我尝试了什么:

   def _recurse_for_parents(self, category, path=None):

    if path is None:
        path = []
    path.append(category)
    if category.parent:
        return self._recurse_for_parents(category.parent, path)
    return path

 for record in categories:
            self._recurse_for_parents(category)

问题:

在循环中，我可以点击父级、一级子级、二级等:

Child1_L2-Child1_L1->parent; Child1_L1->parent; parent->Null
Child1_L1->parent; parent->Null
Child2_L1->parent; parent->Null

因此，我多次在不同深度上击中同一条路径。此外，对于每条路径，我都需要添加从他的 parent 回到 child 的链接。

Answer 1

这在概念上看起来很简单。我看不出递归实现的具体用途在哪里。迭代解决方案很简单。我将概述基本思想。

我假设给定了一个包含 N 个节点的数组，并且每个节点都有一个 ID。

我要做的第一件事是创建一个字典，以 ID 为键，值是具有以下结构的新节点类型:

NewNode
    Id - the node's id
    Children - a list of some type that contains the ids of the node's children
    Whatever other data the database gives you.

对于列表中的每个节点，在字典中查找父节点，并将该节点添加到父节点的子节点列表中。

当您在上面的步骤中浏览列表时，您应该会遇到一个没有父 ID 的节点。这就是根源。如果没有这样的节点或有多个节点，则您的数据无效。

无论如何，您在字典中查找该节点的 id 并将其保存为根。

例子

假设你有两棵树:

           100                  200
         /     \             /   |   \
      101      120         201  210  220
       |      /   \         |         |
      102   121   122      202       221
     /   \               /  |  \
   103   110           203 204 205
    |
   104

所以你有这些节点:

ID      Parent
104     103
103     102
102     101
101     100
100     NULL
110     102
121     120
120     100
122     120
203     202
202     201
201     200
204     202
205     202
210     200
221     220
220     200
200     NULL

我的建议是根据该列表创建字典，以节点 ID 为键。每个节点都有一个 children 列表。

现在，从列表中的第一项开始，查找父项，并将节点添加到父项的子列表中。因此，对于第一项，您会看到节点 104 具有父节点 103。您将对节点 104 的引用添加到 103 的子列表。

然后您移动到列表中的下一个节点。完成后，您的字典将如下所示:

ID      Parent  Children
104     103     []
103     102     [104]
102     101     [103]
101     100     [102]
100     NULL    [101,110,120]
110     102     []
121     120     []
120     100     [121,122]
122     120     []
203     202     []
202     201     [203,204,205]
201     200     [202]
200     NULL    [201,210,220]
204     202     []
205     202     []
210     200     []
221     220     []
220     200     [221]

您的字典现在包含倒置树。您可以扫描字典，查找 Parent 值为 NULL 的节点。那些是你的树根。每个根都有一个对其子节点的引用数组，这些子节点有对其子节点的引用等。