Regarding binary trees - I had seen the following code as part of the solution for a problem:
struct Node
{
int key;
struct Node *left, *right;
};
My question is what does "struct Node *left, *right" mean given it is defined w/in the body of the first struct Node definition. Also if this is C++ why would you use struct instead of just class/object here?
In C++ (and especially C), types are usually always represented by their construct.
For instance,
enum Foo { ... };
void doSomethingWithAFoo(enum Foo f);
struct Bar { ... };
void doSomethingWithABar(struct Bar bar);
While this is required in C, it is not in C++. In C, it is achieved by using a typedef.
typedef struct { ... } Foo; // Can now be referenced with just `Foo`
However, there is a particular part of the spec that states that struct types cannot have instance of themselves inside of them (more specifically it states types cannot refer to themselves before they're fully declared).
Except in pointer form. This is because pointers are known sizes at the beginning of compilation, whereas structures are only known after they are declared.
Since structs pre-date C++ (only by a little) and have been present since ANSI C (C89) and before in most major compilers, they are also present in C++ (since ANSI C can be compiled gracefully in compliant C++ compilers).
However, C++ adds the concept of classes, which don't exist in C. As others have mentioned, classes and structs are similar in that they both holds members. In C++, structs can have methods just like classes - obviously this is not the case in C.
The only difference as far as I'm aware is the visibility; structs default to public and classes default to private. C does not have the notion of visibility.
Node left, right; (without the pointers), then each Node would contain two Nodes. How much memory, then, would a Node require?
Means exactly what it looks like. A recursive declaration just means a Node struct had two fields that are pointers to other Nodes.
I've read that the main difference between structs and classes in C++ is the default permissions (structs are all public by default). Slightly simpler, especially since inheriting is unlikely.
The meaning of struct Node *left, *right; within the definition of struct Node is that each instance of struct Node contains members (left and right) that point to other struct Nodes.
It is the programmer's responsibility to ensure that, whenever a struct Node is created, that those members are initialised appropriately. They may be set to NULL (indicating they don't point at any object) or to the address of another struct Node.
In C++, initialisation of left and right will often be done in a constructor. C doesn't have that feature so, every time some C code creates a struct Node, it will typically have to explicitly initialise the left and right members.
The code you have shown is really C, although it will be accepted by a C++ compiler. C++ allows the declaration struct Node *left, *right; to omit the struct keyword. C does not.
In C++, a struct and a class are the same thing - the difference is accessibility of members: C++ struct members are public and class members are private by default. C++ structs (and classes) are able to do numerous other things that C structs cannot.
structandclassare essentially the same thing in C++. The only difference is thatstructmembers arepublicby default andclassmembers areprivateby default. For that reason it is common to useclassanytime you want encapsulation, andstructwhen you merely want to gather together related public data members e.g.std::pair.