1

我有一个由父节点和子节点组成的树数据结构，如下所示：

<Node1>
  <Node2/>

  <Node3>
    <Node4/>
  </Node3>
</Node1>

为了解析结构，我使用了 μ-recursive 函数：

void RecursiveFunction(NodeT node)
{
    if(node.has_child())
        RecursiveFunction(node.child());
}

当我调用作为参数传递的 RecursiveFunction 时，例如，Node2 我希望访问父（Node1）数据而不使用其他数据结构存储这些数据，因为第一个节点的数据在制作之前已存储在调用堆栈中递归调用。所以我需要访问调用堆栈来读取 Node1 的数据，而我正在解析 Node2 无法直接访问父亲，依此类推。

例如，如果我正在解析 Node4：

void RecursiveFunction(NodeT node)
{
    /* Access to Node3 and Node1 data...

    if(Node4.has_child())
        RecursiveFunction(Node4.child()); */
}

可能吗？以什么方式？

谢谢。

4

5 回答 5

1

访问调用堆栈对我来说有点过度工程。将函数从递归转换为迭代并使用您自己的堆栈。堆栈应包含 NodeT 的实例和整数值，通知函数有多少节点的子节点已被处理。如果该值低于节点的子节点计数，循环将增加该值并将下一个子节点添加到堆栈中。否则它将处理该节点，然后将其从堆栈中弹出。

另一个优点是，您不再受程序堆栈大小的限制，如果需要，您可以处理更多嵌套结构。否则你会冒风险，好吧，我们不要害怕说，堆栈溢出。

于 2012-04-23T11:49:23.930 回答
1

即使您能找到一种从调用函数访问数据的方法，任何其他程序员也不容易理解您的工作。

我建议用迭代替换递归，这应该可以让你清楚地表达你想要做什么。有关更多信息，请参阅从递归到迭代的方式。

于 2012-04-23T11:47:22.937 回答
1

It would be possible, but it would be quite dangerous to do so. This is mainly because you want to mess with the process stack. Also I don't think there are any library functions to do so, that being said you would have to do some pointer arithmetics to achieve that.

于 2012-04-23T11:41:42.753 回答
0

如果您想要或必须（例如作业要求？）坚持递归，请将父节点作为第二个参数添加到您的函数中，默认为NULL，表示当前节点是根节点。IE：

void RecursiveFunction(NodeT const& node, NodeT const* parentPtr=NULL)
{
    if(node.has_child())
        RecursiveFunction(node.child(), &node);
}

请注意，我修改了您的函数以通过引用 const 来接受第一个参数，否则您会创建很多树的副本。

于 2012-04-23T11:55:48.327 回答
0

调用堆栈也用于函数参数*，因此使用它来构建链：

struct chain {
  NodeT* node;
  chain const* parent;
}
void RecursiveFunction(chain const& c)
{
    if(c.node->has_child()) {
       chain child = { c.node->child(), &c };
        RecursiveFunction(child);
    }
}

[*] 至少在概念上；实际实现可能会有所不同。在任何情况下，这个 C++ 代码都是可移植的，不像低级黑客。

于 2012-04-23T13:27:16.080 回答