在不使用递归的情况下遍历n元树

一尘不染

在不使用递归的情况下遍历n元树

algorithm

如何在n不使用递归的情况下遍历-ary树？

递归方式：

traverse(Node node)
{
    if(node == null)
        return;

    for(Node child : node.getChilds()) {
        traverse(child);
    }
}

阅读 230

2020-07-28

共1个答案

一尘不染

您可以执行此操作而无需递归且没有堆栈。但是您需要向该节点添加两个额外的指针：

父节点。因此，如果您完成了工作，可以回到父母那里。
当前的子节点，因此您知道接下来要使用哪一个。
- 对于每个节点，您将处理所有孩子。
- 如果处理了一个孩子，则检查是否有下一个孩子并进行处理（更新当前孩子）。
- 如果所有孩子都得到处理，请回到父母那里。
- 如果该节点为NULL，请退出。

使用伪代码，它看起来像：

traverse(Node node) {
  while (node) {
    if (node->current <= MAX_CHILD) {
      Node prev = node;
      if (node->child[node->current]) {
        node = node->child[node->current];
      }
      prev->current++;
    } else {
      // Do your thing with the node.
      node->current = 0; // Reset counter for next traversal.
      node = node->parent;
    }
  }
}

2020-07-28