遍历 Spaghetti Stack 并反转到一棵树

Question

我有一个意大利面堆栈（一种 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

我需要的：

现在我知道孩子的父母了。从父节点开始，我需要了解他的孩子。

所以我需要遍历“Spaghetti Stack”，将父节点中的连接添加到子节点，以便我可以从父节点遍历到子节点。

一个父级可以有 0 个、一个或多个子级。

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

此外，我认为某种形式的记忆是必要的，因为通过数组循环父级的父级可以获得多次访问。

我试过的：

   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

所以，我多次在不同的深度上走同一条路。同样对于每条路径，我需要添加从他的父母回到孩子的链接。

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]

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