number of nodes in tree

This is a discussion on number of nodes in tree within the C++ Programming forums, part of the General Programming Boards category; does anybody know the code for finding the number of nodes in a search tree...

  1. #1
    Unregistered
    Guest

    number of nodes in tree

    does anybody know the code for finding the number of nodes in a search tree

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    The easiest way is to traverse the tree and count them. But if the tree is balanced you might want to try something like 2^n+1 - 1.

    If the height of the tree is 2 then
    2^n+1 - 1 = 2^3 - 1 = 7

    The tree would look like this:
    Code:
         *
      *     *
    *  *   *  *
    So it's good.

    Prelude
    My best code is written with the delete key.

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,793
    Code:
    int NodeCount( Node* pNode )
    {
        if( pNode != NULL )
            return 1 + NodeCount( pNode->pLeftChild ) + NodeCount( pNode->pRightChild );
        else return 0;
    }
    Haven't tested it, looks correct though.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Tree Calculator
    By MercFh in forum C++ Programming
    Replies: 33
    Last Post: 12-03-2007, 08:34 PM
  2. Binary tree not inserting nodes correctly
    By jk1998 in forum C++ Programming
    Replies: 7
    Last Post: 09-22-2007, 12:37 PM
  3. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  4. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21