如何访问嵌套 json object 的 parent

Question

我有一个任意嵌套的 JSON object（使用 json.load 解析），由字典、列表、基元等组成。我首先使用递归深度遍历它并跟踪路径以 linux fs 格式添加到节点（对于列表，我将 /element 附加到路径，因此在特定路径上可以有多个 object），如下所示：

def traverse(node, path =''):
   if isinstance(node, dict):
      for key in node:
         traverse(node[key], path+'/'+key)
   elif isinstance(node, list):
      for elem in node:
         traverse(elem,path+'/element')

每个节点可能包含一个字符串，需要使用 objects 的值填充，这些值可以存在于树中的任何位置，在当前节点的相对路径中引用，例如：“{.. /../key} {./child1/child2/key}".
问题：我可以访问当前节点的children节点的值，但我不能直接访问当前节点的parent。
我认为的解决方案：我认为的一个解决方案是有一个元组列表（child，parent）并将当前节点与 child 我准备递归进去，然后在需要上去的时候反向搜索那个列表。这有点危险，因为如果 child 是原始值，那么它将等于任何其他具有相同值和类型的 children，因此我可能会检索到错误的 parent，但我认为反向浏览列表应该可以解决这个问题，对吧？
我认为一个不同的解决方案是有一个字典，键是 child 的路径，值是 parent 节点。我认为这应该更好用，因为唯一一次路径冲突是与列表元素发生冲突，但它们都具有相同的 parent 所以我认为应该没问题。

还有其他建议吗？或者对这两种解决方案有何评论？谢谢

Answer 1

在 Python 中 vanilla 对象（至少那些用于 JSON blob 的 list, dict,等）与集合和包含它们的对象没有关系。

这是有道理的，因为基本上一个列表可以多次包含相同对象。此外，一个对象可以同时存储在字典和集合中。除非你执行某种垃圾收集算法（这在性能方面非常低效，并且会对所有对象“扫描”），否则因此，没有简单的方法来重建引用给定对象的对象列表。即使我们扫描对象，决定我们将看到什么作为“parent”仍然远非微不足道，因为可以有多个父对象。

在Python中，字典甚至可以包含自己。喜欢：

# example of constructing a datastructure containing itself
some_dict = {}
some_dict['a'] = some_dict

现在我们无休止地递归 some_dict，例如 some_dict['a']['a']['a'] is some_dict。

关键在于，由于您以递归方式进行枚举，因此您可以维护一个包含祖先的堆栈。例如：

def traverse(node, path ='', stack=None):
    <b>if stack is None:
        stack = [node]
    else:
        stack.push(self)</b>
    if isinstance(node, dict):
        for key in node:
            traverse(node[key], path+'/'+key, stack)
    elif isinstance(node, list):
        for elem in node:
            traverse(elem,path+'/element', stack)
    <b>stack.pop()</b>

因此，在我们检查节点之前，每个节点都会将自己压入堆栈，最后，它会将自己从堆栈中弹出。我们以递归方式传递堆栈，因此每次递归调用都可以检查堆栈（不仅是父级，还包括直到根的整个路径）。

Answer 2

返回 dict（或任何没有反向指针的递归结构）的父级的唯一方法是在遍历时记住它。

但请注意，您已经这样做了：您的 path 字符串是从顶部到当前节点的路径。

让我们编写一个使用路径的函数：

def follow(head, path):
    if not path:
        return head
    first, _, rest = path.partition('/')
    return follow(head[first], rest)

当然，将 path 构建为键元组而不是字符串可能会更好，这样我们就不必将它们分开（因此我们不必担心关于转义或引用（如果任何键可能包含 / 等）；你总是可以 join 他们最后。

并且将 path 构建为节点元组（或键-节点对）而不仅仅是键可能会更好，因此我们可以在恒定时间内访问父节点，就像 path[-1] 而不是对数时间 follow(head, path)。但这实际上取决于您实际要做什么；您的真实代码大概不只是遍历树，建立到每个节点的路径，然后对它们不做任何事情。

然而，解决这个问题的一个非常好的方法是将遍历由内而外：使 traverse 成为迭代器：

def traverse(node, path =''):
   if isinstance(node, dict):
      for key in node:
         yield from traverse(node[key], path+'/'+key)
   elif isinstance(node, list):
      for elem in node:
         yield from traverse(elem,path+'/element')
   yield (node, path)

现在我们可以遍历 traverse 来做任何我们想做的事情，作为 post 顺序深度优先遍历：

for node, path in traverse(root):
    # do something

现在您可以轻松更改它以生成 node, parent, path（无论 parent 是父节点，还是父键，或者您想要的任何内容）。

Answer 3

如果你想通过属性值搜索一个节点，并知道该节点的父节点是什么，你可以使用以下方法：

def find_node_callback(node, stack, callback, path=''):
    stack.append(node)
    if callback(node,path,stack):
        return True

    if isinstance(node, dict):
        for key in node:
            if find_node_callback(node[key],stack,callback,path+'/'+key):
                return True
    elif isinstance(node, list):
        for elem in node:
            if find_node_callback(elem,stack, callback,path+'/element'):
                return True

    stack.pop()
    return False

这样称呼它：

def isTargetNode(node,path,stack):
    if node == "value Im searching for":
        return True
    return False

# uses a callback to determine if the node is what you want
a = json.loads(jsonString) 
stack=[]          
if find_node_callback(a,stack,isTargetNode):
    # this array will contain all the parent items of your
    # target node, with the target node value being the last
    # thing stored in the array
    print(stack)

如何访问嵌套 json object 的 parent

How to access parent of nested json object

python

json

children

parent

parent-child