How to not duplicate code for printing tree

user_14430412 0
Viewed 68

I have a function that prints tree nodes from left to right.

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

But now I want to add a function that prints nodes that meet some condition. For example, print only such nodes, strings of which start with a given string. So it would look like

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

But then I have two functions with the same code, with the difference in one line. How would I avoid code duplication here?

UPD: Traverse code:

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();
    }
}
code-duplication binary-tree c++
2 Answers

The C++ ways is to create an iterator for the traversal and use that for printing as well as filtering or other uses. Traversing a tree can probably be done in a bidirectional fashion which would allow plenty of algorithms to become accessible for the tree, too. In fact, the ordered associative containers (e.g., std::map, std::set) are normally implemented as [balanced] binary trees and their iterators do an in-order traversal.

The details of iteration do depend on the tree representation. The associative containers are normally implemented with a parent pointer. If there is no such pointer each iterator will need to maintain suitable space to represent the path back to the root (the standard library containers can't do that because they have requirements for iterator stability which prevents that). The slightly odd thing about traversal using iterators is that doesn't lend itself directly to an implementation using recursion. In return, control over the iteration is given to the user of the iterators.

user_11202730

Given your function, another approach would be to make the TraverseTree function take a function to invoke once a node is discovered:

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

Then Print would simply be:

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

And the final call would be:

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

If you have other information to print, pass a function object (a class that has operator() overloaded), and within the object is everything necessary to do the work intended (usually represented as class members):

For example:

struct MyPrint
{
    std::string some_value;

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

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

Then call it like this:

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