std ::将自定义树转换为新树

Question

我有一个像数据结构一样的树定义为:

template<typename T>
struct node {
  T val;
  node<T>* parent;
  unique_ptr<node<T>> next_sibling;
  unique_ptr<node<T>> first_child;
};

template<typename T>
struct tree {
    ...
  private:
    unique_ptr<node<T> _head;
};

我还为树类定义了几个迭代器(preorder,inorder ...).

使用std::transform给定的树的作品:

tree<int> t;
...
std::transform(t.begin(), t.end(), t.begin(), [](){});

但是我知道想要有类似于a的东西back_inserter来构建具有相同层次结构的新树:

tree<int> t_n;
std::transform(t.begin(), t.end(), my_inserter(t_n));

如何才能做到这一点？

Answer 1

那么,这一切都取决于你是否可以定义back_inserter.

它可以做到,但不能用value_type = T.问题是普通序列不包含足够的信息来重建树的形状(除了特殊情况,如二进制堆).

因此,您必须迭代组成节点值的不同值类型以及有关树形状的一些信息.我看到两个选择:

• 在T(boost::option<T>)周围使用一个可空的包装器,并在每个节点后序列化next_sybling和first_child,如果不存在则为none,或者
• 使用另一个标志来指定节点是否有子节点以及是否有更多兄弟节点,例如std::tuple<T, bool, bool>.

然后你应该能够使用预先顺序迭代重建插入器中的树,最好是深度优先,但广度优先也可以.无论哪种方式,您都必须像在读取迭代器中那样在插入器中保持相同的迭代状态,因此它将是相当多的代码.