0

我正在用 C++ 实现一个树结构，它有一个像这样的节点类：

class Node {
protected:
    // relations
    Node *_parent;
    std::vector<Node*> _children;

public:
    // some example method 
    void someMethod(Node *node) {

        // do something with *node

        for (int i = 0; i < node->_children; i++) {
            _children[i]->myFunction;
        }
    }
}

现在，要在树中的节点上工作，我正在实现递归函数，就像someMethod我的示例中一样。

它可以工作，但我最终为每个在我的树上工作的新函数一遍又一遍地编写相同的递归代码。

有没有像在普通数组上那样迭代树结构的通用方法？一些返回下一个对象的方法，直到我完成整个分支。

编辑：

感谢迄今为止发表评论的所有人，在您的帮助下，我可以缩小问题的范围。根据我的理解（我是 C++ 新手），我需要一个迭代器类来封装用于遍历我的树的代码。

访问所有树成员应该很简单：

for (Node<Node*>::iterator it = _node.begin(); it != _node.end(); ++it) {
    Node *node = *it;
    // do something with *node
}

现在的问题是：

如何实现这样的迭代器？

4

2 回答 2

1

将函数指针传递给返回您正在寻找的节点的递归函数。

这就是 C/C++ 中函数指针和函数指针数组的强大之处。

于 2013-02-10T14:22:52.290 回答
0

许多函数不会简单地遍历所有节点，如果树（通常）是排序的，那么要找到最大值，您只会在右子树中查找。

如果您搜索最小值，它位于最左边的子树中。

因此，拥有一个迭代整个树的迭代器并不总是有意义的。
但是，如果您需要精确地遍历所有节点，则可以使用函数指针或访问者模式（Erich Gamma，设计模式）。

于 2013-02-10T14:29:22.637 回答