Can I create a new struct on the heap without defining a constructor?

Even if you don't define a constructor, the compiler will create a default one and so you can use operator 'new':

Node *n = new Node;

AFAIAC, a struct is a class, except that its "publicness" default is reversed.

Malloc works fine:

Node *n = (Node*)malloc(sizeof(*n));

Just remember to free() anything malloc()'d and delete anything new'd.

In this case, however, is it possible to create a new instance of this struct on the heap, or would I need to define a constructor? Is there a way to create things on the heap without the new operator?

As answered before, you can create a new instance on the heap either via new or with malloc.

Or, better yet: is it unnecessary for me to cling so tightly to the notion that I shouldn't define member functions for structs?

This is the more interesting question. The major (only?) difference between struct and class in c++ is the default access specifier. That is, struct defaults to public access and class defaults to private. In my opinion, this is the difference that should determine which of the two you use. Basically, if users should access the members directly, then it should be a struct.

If, for example, you have no member functions, then obviously the intention is for the object's members to be accessed directly and so it would be a struct. In the case of an object that is just a small private helper for the implementation of its outer class, as in your example, then even if it has member functions it is often clearest to allow the outer class access to its members and so it should be a struct. Often with these classes the implementation of the outer class is tightly coupled to the implementation of the inner class and so there is no reason to hide the one from the other.

So, for trivial (e.g. std::pair) objects or those whose use is limited (as in a private inner class) default access to members can be a good thing, and in these cases I would make them structs.