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

Question

我有一个 Spaghetti Stack（一个 N-ary 树数据结构，其中 child 节点有指向 parent 节点的指针）- 从数据库接收。

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

节点是数据库中的记录，其中 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。从一个parent节点开始我需要知道他的children.

所以我需要遍历 'Spaghetti Stack' 将 parent 节点中的连接添加到 children 以便我可以从 parent 遍历到 children。

一个parent可以有0个，一个或多个children。

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

此外，我认为一种记忆形式是必要的，因为循环遍历 parent 的数组 parent 可以获得多次访问。

我试过的：

   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)

问题：

在循环中，我可以点击 parent、第一级 child、第二级等：

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

所以，我多次在不同的深度上走同一条路。此外，对于每条路径，我需要将他的 parent 中的 link 添加回 children.

Answer 1

一个简单的解决方案可能是以下一个，假设您的节点由整数表示，并且您的数组是 array[2] = 3 表示 'the parent of node 2 is node 3'.. 让我们调用 array所有节点的列表（或任何可迭代的），然后：

adjacencies = []
for node in tree : # iterate on all your nodes
    adjacencies += [(node.parent_id, node)]

然后要获取给定节点的子节点，您只需按如下方式处理：

def get_children (parent :int, adjacencies :list) -> set:
    return {child for (parent, child) in adjacencies}

如果您想要更精确的解决方案，您需要向我提供有关您的实施的更多信息；那我来编辑一下。

Answer 2

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

我假设给定了一个包含 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 的节点。那些是你的树根。每个根都有一个对其子节点的引用数组，这些子节点有对其子节点的引用等

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

Traverse a Spaghetti Stack and reverse to a tree

python

algorithm

recursion

stack

tree-traversal

例子