C++遍历二叉树的设计问题

Question

我有一个二叉树 T，我想将其复制到另一棵树。

假设我有一个在每个节点上进行评估的访问方法：

struct visit 
{
 virtual void operator() (node* n)=0;

};

并且我有一个访问者算法，

void visitor(node* t, visit& v)
{
//do a preorder traversal using stack or recursion
 if (!t) return;
 v(t);
 visitor(t->left, v);
 visitor(t->right, v);

}

我有两个问题：

1. 我决定使用基于函子的方法，因为我看到提升图可以做到这一点（顶点访问者）。我也倾向于重复相同的代码来遍历树并做不同的事情 在每个节点。这是一个消除重复代码的好设计吗？还有哪些其他替代设计？
2. 如何使用它从现有的二叉树创建一棵新的二叉树？我可以在上面保留一个堆栈 如果我愿意，可以访问函子，但它与访问者中的算法相关联。
3. 我如何在这里合并后序遍历？另一个函子类？

Answer 1

3：为您想要执行的每种类型的遍历创建一个附加方法并重新安排访问者调用：

void preorder_visitor(node* t, visit& v)
{
 if (!t) return;
 v(t);
 visitor(t->left, v);
 visitor(t->right, v);
}

void postorder_visitor(node* t, visit& v)
{
 if (!t) return;
 visitor(t->left, v);
 visitor(t->right, v);
 v(t);
}

Answer 2

1. 对访问者进行子类化并为每个单独的任务提供不同的访问者，并将类似（或相关）的任务合并到同一访问者中。最好的方法在很大程度上取决于您想要做什么。
2. 访客可以构建一棵不同的树。当它访问节点时，它会构建新的节点副本并以“正确”的顺序链接它们。
3. 您重写访问节点的顺序。

访客是一种技术。看起来您已经将该技术与特定解决方案混淆了。使用访问者意味着某些导航服务由数据结构提供，该数据结构将通过回调与外部对象（访问者）进行通信。