java - 从上到下遍历具有两个以上子节点的树以获取java中的值，然后自下而上遍历以再次调整值

Question

我有一棵树，它可以有两个以上的子树，所以它不是二叉树。事实上它可以有n个。子级，它也可以有 n 个级别。

如果我从 root(有一个 id)开始，那么子级将 root 的 id 作为父级 id，并且子级也有自己的 id。同样，如果我转到下一级子级，则上级节点 id 将充当该级别的父级 id。我需要怎样穿越？从根节点开始，根据根节点 id，我将找到子节点(将根节点 id 作为父节点 id)，然后我需要从这些子节点检索一些数据并进行一些计算。当我传递这些 child 的 id 并再次进行一些计算时，我会进入下一个级别。该过程一直持续到我找不到任何基于 ID 的记录为止。另外我还需要反向遍历来进行一些推演。

我正在使用 Spring Boot 和 mongodb。使用spring数据mongodb。

实体结构-ID- 家长 ID- 类型- 数量- 供应商 ID。

我需要一个解决方案来遍历这种树并检索数据。这也是一项性能关键任务。

Answer 1

如果我是你，我会将 children 字段添加到结构所以沿着树向下遍历就是 Depth-fisrt search 。递归实现将是:

private static final int NOT_FOUND = -1;
public int findItem(someCondition) {
  if (check(someCondition)) { 
    return id;
  }
  for(Structure child:current.getChildes()) {
    int childResult = child.findItem(someCondition);
    if (childResult != NOT_FOUND) {
      return childResult;
    }
  }
  // this node and its childes are not comply with someCondition
  return NOT_FOUND;
}

深度优先搜索可以用迭代方式编写。

此方法将在 O(N) 内完成，并且每个节点仅访问一次。如果您无法更改结构，那么您必须访问每个级别的每个节点并花费 O(N*n) 时间。

如果你想比 O(N) 更快地搜索，你需要像 K-d tree 这样的排序。添加 O(log N) 时间的成本，您可以在 O(log N) 时间内进行搜索。

构建路径更简单:

Structure current = this;
while (current.getParent() != null) { 
  current = current.getParent();
  path.add(current.id); 
}