Write a programme segment to find out the total number of nodes in a tree?

Answer 1

This can be achieved with a recursive-traversal function starting at the root.

Binary tree nodes use the following shorthand form (using tertiary conditional operator):

int Node::GetNodeCount()

{return( 1 +( left ? left.GetNodeCount() : 0 ) +

( right ? right.GetNodeCount() : 0 ));

}

Or in longhand:

int Node::GetNodeCount()

{// Always include self in countint count = 1;

// Is there a left node?if( left )

// Increment the count with a recursive traversal.count += left.GetNodeCount();

// Is there a right node?if( right )

// Increment the count with another recursive traversal.count += right.GetNodeCount();

// Return the total count to the caller.

return( count );

}

Tree nodes with variable child nodes (lists of lists) use the following longhand form:

int Node::GetNodeCount()

{// Always include self in count.

int count = 1;

// Start with this node's head node (the first child node).

Node node = head;

// Iterate through all child nodes.

while( node )

{// Increment the count with a recursive call.count += node.GetNodeCount();

// Traverse to the next child node.node = node.next;}

// Return the total count to the caller.

return( count );

}