如何不重复打印树的代码

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();
    }
}

Answer 1

C++ 的方法是为遍历创建一个迭代器，并将其用于打印以及过滤或其他用途。遍历树可能以双向方式完成，这将允许树也可以访问大量算法。事实上，有序的关联容器（例如，std::map、std::set）通常被实现为[平衡]二叉树，并且它们的迭代器进行有序遍历。

迭代的细节确实取决于树表示。关联容器通常使用父指针实现。如果没有这样的指针，每个迭代器将需要维护合适的 space 来表示返回根的路径（标准库容器不能这样做，因为它们对迭代器稳定性有要求，这会阻止这种情况）。使用迭代器进行遍历的一个有点奇怪的地方在于，它并不直接适用于使用递归的实现。在 return 中，迭代的控制权交给了迭代器的用户。

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);

如果您有其他信息要打印，请传递一个函数对象（一个 class 已 operator() 重载），并且在该对象中是完成预期工作所需的一切（通常表示为class 位成员）：

例如：

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);

如何不重复打印树的代码

How to not duplicate code for printing tree

c++

binary-tree

code-duplication