如何避免重复代码以打印树形结构

Question

我有一个函数，按从左到右的顺序打印树节点。

void PrintTree()
{
...
Print(curentNode);
...
}

但是现在我希望添加一个函数，打印出满足某些条件的节点。例如，只打印那些字符串以给定字符串开头的节点。这将会像这样：

void PrintTreeByCondition(string a)
{
...
if(IsPrefix(a,curentNode->stringVar))
      Print(curentNode);
...
}

但是我有两个函数的代码相同，仅有一行不同。如何避免出现代码重复？

更新：遍历代码：

void BinTree::TraverseTree()
{
    std::stack<TreeNode*> s;
    s.push(root);
    TreeNode* curentNode = s.top();
    while (curentNode != nullptr|| s.empty() == false)
    {
        while (curentNode != nullptr)
        {
            s.push(curentNode);
            curentNode = curentNode->GetLeft();
        }

        curentNode = s.top();
        s.pop();

        // do stuff

        curentNode = curentNode->GetRight();
    }
}

- IvanIvan

---

如何避免重复代码以打印树 - 怎么样将树遍历的代码通用化，并在访问节点时调用用户提供的函数呢？这是一个更好、更通用的方法。如果您想对已访问的节点执行其他操作而不是仅仅打印它，该怎么办呢？让我们看看遍历代码。 - PaulMcKenzie

@PaulMcKenzie 我在考虑类似这样的东西，想要使用函数指针，像这样：void TraverseTree(void (*f)(const CTreeNode*))。但是之后我就不知道如何实现第二个行为了。 - IvanIvan

@PaulMcKenzie已添加。从Dietmar Kühl提供的答案来看，我理解我需要向我的树添加类似迭代器的东西。这只能通过在节点类中添加指向父节点的指针来完成，对吗？ - IvanIvan

使用一个重载了 operator() 的对象。 - PaulMcKenzie

@IvanIvan：您提供的函数对象将接受traverse()函数为每个节点传递的参数。例如，如果您的树节点包含一个T对象作为它们的值，则该函数可能会以T const&作为参数。根据traverse()函数是否是函数模板，它将使用带有可调用T const&的[n隐式]概念的模板参数作为其访问者函数。如果它不是一个模板，它可能会以std::function<void(T const&)>作为参数。 - Dietmar Kühl

Answer 1

C++的方法是创建一个迭代器来遍历树，然后将其用于打印和过滤等其他用途。可能可以使用双向方式来遍历树，从而使得许多算法也可以应用于树。实际上，有序关联容器（例如std::map，std::set）通常被实现为[平衡]二叉树，它们的迭代器执行中序遍历。

遍历的细节取决于树的表示方式。关联容器通常使用父指针进行实现。如果没有这样的指针，则每个迭代器都需要维护适当的空间以表示返回到根的路径（标准库容器无法做到这一点，因为它们对迭代器稳定性有要求，这会阻止这样的操作）。使用迭代器遍历的略微奇怪之处在于它不直接适用于递归实现。作为回报，可以将迭代器的控制权交给用户。

- Dietmar Kühl

Answer 2

假设您的函数，另一种方法是使TraverseTree函数接受一个要在发现节点时调用的函数：

template <typename fn>
void BinTree::TraverseTree(fn func)
{
    std::stack<TreeNode*> s;
    s.push(root);
    TreeNode* curentNode = s.top();
    while (curentNode != nullptr|| s.empty() == false)
    {
        while (curentNode != nullptr)
        {
            s.push(curentNode);
            curentNode = curentNode->GetLeft();
        }
        curentNode = s.top();
        s.pop();
        func(currentNode);  // call custom function
        curentNode = curentNode->GetRight();
    }
}

那么 Print 就简单地是这样的：

void Print(Node *n)
{
   std::cout << n->data << "\n"; // assuming there is a "data" member
}

最后调用的将会是：

BinTree b;
//...
b.TraverseTree(&Print);

如果您有其他需要打印的信息，可以传递一个函数对象（一个类，其中包含重载了operator()的函数），在该对象内部包含完成所需工作的所有必要信息（通常表示为类成员）：

例如：

struct MyPrint
{
    std::string some_value;

    MyPrint(std::string s) : some_value(s) {}

    void operator() (Node *n) 
    { 
       std::cout << some_value << " -- " << n->data << "\n"; 
    }
};

然后像这样调用：

BinTree b;
//...
MyPrint m("Testing testing");
b.TraverseTree(m);

- PaulMcKenzie