What do nodes do?

Answer 1

In programming a node is a pointer to some data. For instance, if we allocate objects non-contiguously we can treat them as if they were allocated contiguously by storing pointers to those objects in a contiguous array:

foo* a[100];

for (int i=0; i<100; ++i) a[i] = malloc (sizeof(foo));

In the above example we have an array of foo nodes. The foo objects themselves are individually allocated on the heap but they need not be allocated contiguously. But this does not matter because an array is always allocated contiguously so the order of the objects is determined by the order of the nodes in the array. If we change the order of the nodes, we change the order of the objects, but the objects don't actually move. This is useful when the objects are large or complex because it means we can change their order much more efficiently just by moving the nodes.

As well as pointers, a node can also be defined as a structure:

struct node {

foo* data;

node* next;

};

Here, the node still points to an object but also points to another node, the next node in the sequence. In this case we don't need an array, we simply need to keep track of the first node in the sequence. This means we are no longer restricted by the array length; we can have as many or as few nodes as we require. Changing the order of the nodes is simply a matter of changing which data element each node points to. We can also insert and extract elements from the sequence by changing which node each node points to.

More complex data structures require additional node pointers. For instance, a bi-directional list requires two node pointers, one to the next element in the sequence and one to the previous element:

struct node { foo* data;

node* next;

node* prev;

};

A binary tree node also has two node pointers:

struct node {

foo* data;

node* left;

node* right;

};

A binary tree node might also point to its parent node:

struct node {

foo* data;

node* parent;

node* left;

node* right;

};

A tertiary node has at least three node pointers:

struct node {

foo* data;

node* left;

node* middle;

node* right;

};

Nodes make it possible to construct highly-complex data structures regardless of where the data is physically allocated and the order in which it is allocated. The point is that we don't need to move any data around because the nodes themselves define the data structure. The nodes can be thought of as being metadata (data about data).

Any node that allows traversal to any other node in the structure can be used to keep track of the structure, however we typically use the node that provides the most efficient traversal. In a tree structure, that is always the root node. In a list, it is the head node.

Answer 2

A node is typically used to provide the connection between a data sequence and the data itself.

Unlike an array where the data sequence is defined by the order in which elements are allocated (elements with lower addresses come before those with higher addresses), data structures are maintained by interlinking nodes. Each node has at least two pointers; one pointer refers to a data element while the other points to the next node in the sequence. The first node in the sequence is called the head node and we use this to keep track of all the nodes in the structure. We can traverse the data structure by traversing the nodes starting from the head node. The last node, the tail node, has no next node so its next node pointer will be NULL. This is what we call a forward list because it allows us to traverse forwards through the structure. A circular forward list has a tail that points "forwards" to the head.

A (doubly) linked list is implemented with nodes that have two node pointers, one referring to the next node and the other referring to the previous node, thus allowing bi-directional traversal of the data.

Alternatively, we can create binary trees with nodes that have two node pointers, one referring to the root of the left subtree and the other referring to the root of the right subtree. Folder trees can be created by using a node that holds a list of "child" nodes.

To represent a complete file/folder hierarchy, each node represents a folder containing a list of files (the data) and a list of nodes (the sub folders).

Typically, nodes do not store any data, they simply refer to it through a pointer.

Answer 3

A node in binary tree is any element of the tree itself that could be either a root, leaf, or non-leaf.

Answer 4

branching points in tree. They represent speciation events, divergence of lineages, and ancestors.