6
\$\begingroup\$

Please review my code for preorder, inorder and postorder of a tree. I am using C++11 (or wanted to use), so let me know if anything is deviating from the C++11 standard.

#include <iostream>
#include <memory>

using std::cout;
using std::endl;
using std::shared_ptr;

struct node
{
    int data;
    shared_ptr<node> left;
    shared_ptr<node> right;
};

shared_ptr<node> newNode (int i)
{
    shared_ptr<node> n (new node);
    n->data = i;
    n->left = nullptr;
    n->right = nullptr;

    return n;
}

void preOrder(shared_ptr<node> n)
{
    if(n == nullptr)
        return;

    cout<<n->data<<" ";

    preOrder((n->left));
    preOrder((n->right));
}

void inOrder(shared_ptr<node> n)
{
    if(n == nullptr)
        return;

    inOrder((n->left));

    cout<<n->data<<" ";

    inOrder((n->right));
}

void postOrder(shared_ptr<node> n)
{
    if(n == nullptr)
        return;

    postOrder((n->left));
    postOrder((n->right));

    cout<<n->data<<" ";

}

int main(int argc, char* argv[])
{
    shared_ptr<node> r = newNode(1); 
     (r->left) = newNode(2);
     (r->right) = newNode(3);
    (r->left->left) = newNode(4);
    (r->left->right) = newNode(5);

    preOrder(r);
    cout<<endl;

    inOrder(r);
    cout<<endl;

    postOrder(r);
    cout<<endl;

    return 0;
}
\$\endgroup\$
10
\$\begingroup\$

Memory management

Don't think that is the appropriate smart pointer.

shared_ptr<node> newNode (int i)

Do you have plans to actually share ownership of a node? Or is it more likely that ownership will be done by the patent of the node? I would have gone with unique_ptr<node> if I was going to use smart pointers.

make_X

You should not be using new with smart pointers. There are make_XXX commands that combine all the memory allocation required into a single operation (thus making it more efficient).

   std::shared_ptr<node> n  = std::make_shared<node>(val);  // or make_unique

Using

I suppose this is better than using namespace std;

using std::cout;
using std::endl;
using std::shared_ptr;

But its still pretty sloppy and lazy. Pull those declarations into the tightest scope possible (ie inside a function).

Braces

This looks strange

preOrder((n->left));
preOrder((n->right));

Now I am all for using braces to make expression easy to read or to force a particular evaluation order. But this just looks strange and does not help in the evaluation.

Prefer '\n'

Prefer '\n' to std::endl.

The difference between the two is that std::endl forces a flush after placing the new line on the stream. It is very rare that you actually want to force a flush (as the runtime is much better at making that decision than you). Excessive flushing just makes the stream libraries slow.

\$\endgroup\$
  • 2
    \$\begingroup\$ @Hurkyl: You have a misconception of how buffering works. Before input is read from the standard input the standard output is automatically flushed. So you always know the question. So my advice still holds. \$\endgroup\$ – Martin York Jan 12 '15 at 18:22
  • 1
    \$\begingroup\$ @Hurkyl: Diagnostic information should be on std::err (which is not buffered and thus does not need to be flushed). The only thing that will happen when you flush is that you slow the output down dramatically. If your output is already slow then maybe a manual flush could be useful to show progress (but those are by far the exception not the rule). So again my advice stands. \$\endgroup\$ – Martin York Jan 12 '15 at 18:27
  • 1
    \$\begingroup\$ @Hurkyl: PS this has been discussed at length on stack overflow. You should do a search and some reading. stackoverflow.com/q/213907/14065 \$\endgroup\$ – Martin York Jan 12 '15 at 18:30
  • 1
    \$\begingroup\$ @Hurkyl: I am not saying don't use std::endl. I am saying think about when you use it. I don't see how this adds any complexity. Nor do I see it introducing a delay (as the flushing is happening automatically when required). You are just trying to prematurely optimize the flush when you think it is a good idea, rather than allow the runtime to do it when it knows it is a good time. Feel free to apply the downvote. But please take the time and read what the experts are saying on SO. \$\endgroup\$ – Martin York Jan 12 '15 at 18:42
  • 1
    \$\begingroup\$ @Hurkyl: Can you show me how this advice damages the code above or does it improve it? Since the whole use is put a line between each block it improves the application as it makes the intention more explicit (the OP want a new line not a flush). \$\endgroup\$ – Martin York Jan 12 '15 at 18:51
8
\$\begingroup\$

One major problem with this approach (without a class) is that adding new nodes is very tedious. If you were to give this code to another user, but with an empty driver, they would have a hard time figuring out how to get this to work. Even if they do figure it out, it appears that each line will get longer as more and more nodes are inserted.

If you had a class with a root node and interface functions, it would be much easier to do this, both for you and for others. The user would not need to create a root, and you can design the interface to allow similar functionality from main(). This is also important because, ideally, node data structures are supposed to stay hidden from the user within the implementation. If you're concerned with the user not knowing how each of the nodes are situated, you can also display them in a tree-like manner instead or alongside this current display. This would avoid the need to read the manual insertion code and instead look at the console output.

You can even use templates to allow any other data type and not just int values. That would make your program look more like C++11, too. As for the interface, you can also allow certain nodes, or all of the nodes, to be deleted.

Beyond all that, this code looks pretty clean (minus the little inconsistent indentation in main()). But usability-wise, it's very weak. There are a lot of resources around for trees, and you can even find them on this site. You should see that they utilize a class as I've described. You can still keep all of this code for this class. It just needs to be put into the member functions and called with a new class instance.

\$\endgroup\$
5
\$\begingroup\$

Except for educational purposes, one shouldn't re-implement data structures provided by the standard library. The standard template library (STL) provides many generic containers. The STL also provides the <algorithm> header, which contains generic algorithms that operate on the STL containers.

Your code focuses on the algorithmic machinations of tree data structure, this is fine for a learning exercise, but you want to work at a higher abstraction level than this, you want to be able to focus on making your code useful. Re-inventing the wheel is something you should avoid, again except for a learning exercise; it is very instructive to build standard data structures from scratch.

When learning how trees work, it doesn't matter if you manipulate the tree directly instead of creating and using member functions to maintain the tree. You did however specifically ask about C++11; your code is closer to C than C++. You certainly used features of C++11 (smart pointers and nullptr), but it is still basically C code. Improvements to align your code with the spirit of C++11:

  • Your tree should be a class, it should maintain the tree and hide the implementation
  • The node class probably should be an nested class within your tree
  • Your tree class should be templated; don't hardcode the type!
  • Your traversals should be implemented with the Visitor pattern.

Also there are some algorithmic improvements you could make, e.x. balancing your tree so that it doesn't become lopsided or degrade into a linked list.

If this is just a learning exercise, the code is fine for "C" code. If you intend to do anything useful with this code it definitely need improvement. Without knowing what you intend to do it is hard to make a suggestion on what data structure to use. The STL provides many structures for different purposes.

If you need a list, you can use <vector> or <list>
If you just need a collection of objects use a '<'set'>' (backed by a balanced tree) If you need a key-value pair mapping use <map> If you need a queue use a <queue>

All of these data structures can be operated on by the header, for example:

for_each(s.begin(), s.end(), [](int i){cout << i;});

would print all the items in the set assuming s is a set<int>; the third argument is a lambda expression, it defines a function that for_each will call on each member of the set.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.