0

我有一个二叉树 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. 我将如何在这里合并后序遍历？另一个函子类？
4

2 回答 2

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);
}
于 2010-04-05T16:28:10.320 回答
0
  1. 将访问者子类化并为每个单独的任务提供不同的访问者，并将相似（或相关）的任务合并到同一个访问者中。最好的方法在很大程度上取决于您尝试做什么。
  2. 访问者可以构建不同的树。当它访问节点时，它会构建新的节点副本并以“正确”的顺序链接它们。
  3. 您重写访问节点的顺序。

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

于 2010-04-05T16:24:28.423 回答